English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Nowhere dense classes of graphs are classes of sparse graphs with richstructural and algorithmic properties, however, they fail to capture evensimple classes of dense graphs. Monadically stable classes, originating frommodel theory, generalize nowhere dense classes and close them undertransductions, i.e. transformations defined by colorings and simple first-orderinterpretations. In this work we aim to extend some combinatorial andalgorithmic properties of nowhere dense classes to monadically stable classesof finite graphs. We prove the following results.  - In monadically stable classes the Ramsey numbers $R(s,t)$ are bounded fromabove by $\mathcal{O}(t^{s-1-\delta})$ for some $\delta>0$, improving the bound$R(s,t)\in \mathcal{O}(t^{s-1}/(\log t)^{s-1})$ known for general graphs andthe bounds known for $k$-stable graphs when $s\leq k$.  - For every monadically stable class $\mathcal{C}$ and every integer $r$,there exists $\delta > 0$ such that every graph $G \in \mathcal{C}$ thatcontains an $r$-subdivision of the biclique $K_{t,t}$ as a subgraph alsocontains $K_{t^\delta,t^\delta}$ as a subgraph. This generalizes earlierresults for nowhere dense graph classes.  - We obtain a stronger regularity lemma for monadically stable classes ofgraphs.  - Finally, we show that we can compute polynomial kernels for the independentset and dominating set problems in powers of nowhere dense classes. Formerly,only fixed-parameter tractable algorithms were known for these problems onpowers of nowhere dense classes.

Combinatorial and Algorithmic Aspects of Monadic Stability