The stable hereditary graph class characterization conjecture

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.

Sources & referencesView supporting material

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.