The stable hereditary graph class characterization conjecture

About 4 years old · traced to

Let C\mathscr C be a hereditary class of graphs, meaning that every induced subgraph of every graph in C\mathscr C also belongs to C\mathscr C. A low shrubdepth decomposition with no(1)n^{o(1)} parts is a decomposition of an nn-vertex graph into a subpolynomial number of parts such that every fixed-size collection of parts induces a graph from a class of bounded shrubdepth. The properties under consideration are first-order transducibility from nowhere dense classes, admitting such decompositions, monadic stability, and stability.

Stable hereditary graph class characterization conjecture. The following properties are equivalent:

  1. C\mathscr C is a first-order transduction of a nowhere dense class;
  2. C\mathscr C admits low shrubdepth decompositions with no(1)n^{o(1)} parts;
  3. C\mathscr C is monadically stable;
  4. C\mathscr C is stable.

This is proposed as a strengthening of the monadic stability characterization conjecture. The source gives no resolution evidence, so the equivalence remains open.

References

Primary source

Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez and Sebastian Siebertz, “Decomposition horizons and a characterization of stable hereditary classes of graphs”, arXiv:2209.11229 (2024).

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.