The LCW Enumeration Conjecture for permutation classes
The LCW Enumeration Conjecture for permutation classes
A permutation class is broadly rational if every finitely based subclass of has a rational generating function, and it is strongly rational if it and all its subclasses have rational generating functions. Let be the graph class associated with by the permutation-graph construction, and let denote well-quasi-ordering. The LCW Enumeration Conjecture. A permutation class is broadly rational if and only if has bounded linear clique-width. Moreover, is strongly rational if and only if 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
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.