Decomposition horizons and a characterization of stable hereditary classes of graphs

arXiv2209.11229MaRDI QIDQ6506641FDOQ6506641

Authors: Samuel Braunfeld, J. Nešetřil, P. Ossona de Mendez, Sebastian Siebertz 

Abstract: Let $mathscrC$ be a hereditary class of graphs. Assume that for every $p$ there is a hereditary NIP class $mathscr{D}_p$ with the property that the vertex set of every graph $GinmathscrC$ can be partitioned into $N_p=N_p(G)$ parts in such a way that the union of any $p$ parts induce a subgraph in $mathscr{D}_p$ and $log{N}_p(G)ino(log|G|)$. We prove that $mathscrC$ is (monadically) NIP. Similarly, if every $mathscr{D}_p$ is stable, then $mathscrC$ is (monadically) stable. Results of this type lead to the definition of decomposition horizons as closure operators. We establish some of their basic properties and provide several further examples of decomposition horizons.

This page was built for publication: Decomposition horizons and a characterization of stable hereditary classes of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6506641)