The geometric griddability and finite-letter-graph conjecture
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.