The LCW Enumeration Conjecture for permutation classes

A permutation class C\mathcal{C} is broadly rational if every finitely based subclass of C\mathcal{C} has a rational generating function, and it is strongly rational if it and all its subclasses have rational generating functions. Let GCG_\mathcal{C} be the graph class associated with C\mathcal{C} by the permutation-graph construction, and let wqo\operatorname{wqo} denote well-quasi-ordering. The LCW Enumeration Conjecture. A permutation class C\mathcal{C} is broadly rational if and only if GCG_\mathcal{C} has bounded linear clique-width. Moreover, C\mathcal{C} is strongly rational if and only if GCG_\mathcal{C} has bounded linear clique-width and is well-quasi-ordered. This conjecture would connect enumeration properties of permutation classes with linear clique-width; the source presents it as an open unifying framework and lists several consequences that are themselves known conjectures.

Sources & referencesView supporting material

Primary source

Robert Brignall, Nicholas Korpelainen and Vincent Vatter, “Linear Clique-Width for Hereditary Classes of Cographs”, arXiv:1305.0636 (2016).

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.