Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 2266

Preprint Number 2266

Previous Next Preprint server

2266. Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez, Sebastian Siebertz
Decomposition horizons: from graph sparsity to model-theoretic dividing lines

Submission date: 15 September 2022


Let C be a hereditary class of graphs. Assume that for every p there is a hereditary NIP class D_p with the property that the vertex set of every graph G ∈ C 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 D_p and log N_p(G) ∈ o(log |G|). We prove that C is (monadically) NIP. Similarly, if every D_p is stable, then C 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.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2209.11229: pdf, ps.

Last updated: October 15 2022 00:13 Please send your corrections to: