The geometric griddability and finite-letter-graph conjecture
Let be a class of permutations, and let be the corresponding class of permutation graphs. A permutation class is geometrically griddable when it can be represented by a geometric grid class.
Geometric griddability and finite-letter-graph conjecture. is geometrically griddable if and only if is a class of -letter graphs for some finite value of .
This conjecture proposes that geometric grid classes of permutations and finite-letter graphs describe the same underlying structure through permutation graphs. The paper establishes constructive polynomial-time recognition for -letter graphs, but the conjectured equivalence is not stated as resolved here.
References
Primary source
Bogdan Alecu, Vadim Lozin, Dominique de Werra and Viktor Zamaraev, “Letter graphs and geometric grid classes of permutations: characterization and recognition”, arXiv:1804.11217 (2018).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.