The geometric griddability and finite-letter-graph conjecture

About 8 years old · traced to

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.

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

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.