
arXiv: 2308.11950
Abstract We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension as a subposet. This applies in particular to posets whose cover graphs have bounded treewidth, as the cliquewidth of a poset is bounded in terms of the treewidth of the cover graph. For the latter posets, we prove a stronger statement: Every such poset with sufficiently large dimension contains the Kelly example of dimension as a subposet. Using this result, we obtain a full characterization of the minor‐closed graph classes such that posets with cover graphs in have bounded dimension: They are exactly the classes excluding the cover graph of some Kelly example. Finally, we consider a variant of poset dimension called Boolean dimension, and we prove that posets with bounded cliquewidth have bounded Boolean dimension. The proofs rely on Colcombet's deterministic version of Simon's factorization theorem, which is a fundamental tool in formal language and automata theory, and which we believe deserves a wider recognition in structural and algorithmic graph theory.
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Combinatorics, Discrete Mathematics, Informatique mathématique, FOS: Mathematics, Combinatorics (math.CO)
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Combinatorics, Discrete Mathematics, Informatique mathématique, FOS: Mathematics, Combinatorics (math.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
