The maximal-antichain conjecture for paths and tree classes

Let P\mathcal{P} denote the class of paths, let Tn\mathcal{T}_n denote the class of rooted trees of height at most nn, and let FO\sqsupseteq_\mathrm{FO} denote the first-order transduction quasiorder. A collection of graph classes is a maximal antichain when its members are pairwise incomparable under this quasiorder and no further class can be added while preserving incomparability. The maximal-antichain conjecture for paths and tree classes. The pairs

{Tn,P}with n>1\{\mathcal{T}_n,\mathcal{P}\}\quad\text{with }n>1

are all the maximal antichains containing P\mathcal{P}. This is presented as an equivalent formulation of the preceding shrubdepth characterization and concerns the structure of antichains in the first-order transduction quasiorder. The source does not specify whether it has been resolved.

Sources & referencesView supporting material

Primary source

Jaroslav Nesetril, Patrice Ossona de Mendez and Sebastian Siebertz, “Structural properties of the first-order transduction quasiorder”, arXiv:2010.02607 (2021).

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.