Abstract
Nowhere dense classes of graphs are classes of sparse graphs with rich structural and algorithmic properties, however, they fail to capture even simple classes of dense graphs. Monadically stable classes, originating from model theory, generalize nowhere dense classes and close them under transductions, i.e. transformations defined by colorings and simple firstorder interpretations. In this work we aim to extend some combinatorial and algorithmic properties of nowhere dense classes to monadically stable classes of finite graphs. We prove the following results.
 For every monadically stable class C and fixed integer s ≥ 3, the Ramsey numbers R_C(s,t) are bounded from above by 𝒪(t^{s1δ}) for some δ > 0, improving the bound R(s,t) ∈ 𝒪(t^{s1}/(log t)^{s1}) known for the class of all graphs and the bounds known for kstable graphs when s ≤ k.
 For every monadically stable class C and every integer r, there exists δ > 0 such that every graph G ∈ C that contains an rsubdivision of the biclique K_{t,t} as a subgraph also contains K_{t^δ,t^δ} as a subgraph. This generalizes earlier results for nowhere dense graph classes.
 We obtain a stronger regularity lemma for monadically stable classes of graphs.
 Finally, we show that we can compute polynomial kernels for the independent set and dominating set problems in powers of nowhere dense classes. Formerly, only fixedparameter tractable algorithms were known for these problems on powers of nowhere dense classes.
BibTeX  Entry
@InProceedings{dreier_et_al:LIPIcs.ISAAC.2022.11,
author = {Dreier, Jan and M\"{a}hlmann, Nikolas and Mouawad, Amer E. and Siebertz, Sebastian and Vigny, Alexandre},
title = {{Combinatorial and Algorithmic Aspects of Monadic Stability}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {11:111:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772587},
ISSN = {18688969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17296},
URN = {urn:nbn:de:0030drops172961},
doi = {10.4230/LIPIcs.ISAAC.2022.11},
annote = {Keywords: Monadic Stability, Structural Graph Theory, Ramsey Numbers, Regularity, Kernels}
}
Keywords: 

Monadic Stability, Structural Graph Theory, Ramsey Numbers, Regularity, Kernels 
Collection: 

33rd International Symposium on Algorithms and Computation (ISAAC 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 