The geometric griddability and finite-letter-graph conjecture

Let XX be a class of permutations, and let GX{\cal G}_X 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. XX is geometrically griddable if and only if GX{\cal G}_X is a class of kk-letter graphs for some finite value of kk.

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 33-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

Never refreshed

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.