Separability Properties of Monadically Dependent Graph Classes

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F25%3A00639493" target="_blank" >RIV/67985807:_____/25:00639493 - isvavai.cz</a>
Alternative codes found
RIV/00216208:11320/25:10511786
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.ICALP.2025.147" target="_blank" >https://doi.org/10.4230/LIPIcs.ICALP.2025.147</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2025.147" target="_blank" >10.4230/LIPIcs.ICALP.2025.147</a>

Result language
angličtina
Original language name
Separability Properties of Monadically Dependent Graph Classes
Original language description
A graph class C is monadically dependent if one cannot interpret all graphs in colored graphs from C using a fixed first-order interpretation. We prove that monadically dependent classes can be exactly characterized by the following property, which we call flip-separability: for every r in N, epsilon > 0, and every graph G in C equipped with a weight function on vertices, one can apply a bounded (in terms of C, r, epsilon) number of flips (complementations of the adjacency relation on a subset of vertices) to G so that in the resulting graph, every radius-r ball contains at most an epsilon-fraction of the total weight. On the way to this result, we introduce a robust toolbox for working with various notions of local separations in monadically dependent classes.
Czech name
—
Czech description
—

Project
<a href="/en/project/GM24-12591M" target="_blank" >GM24-12591M: Model theory, structural combinatorics, and algorithms</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Proceedings
ISBN
978-3-95977-372-0
ISSN
—
e-ISSN
—
Number of pages
19
Pages from-to
147
Publisher name
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Place of publication
Dagstuhl
Event location
Aarhus
Event date
Jul 8, 2025
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
—

Similar results(10)