Discrepancy and sparsity

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10515249" target="_blank" >RIV/00216208:11320/24:10515249 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=j_bM1eroLu" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=j_bM1eroLu</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jctb.2024.06.001" target="_blank" >10.1016/j.jctb.2024.06.001</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Discrepancy and sparsity

Popis výsledku v původním jazyce

We study the connections between the notions of combinatorial discrepancy and graph degeneracy. In particular, we prove that the maximum discrepancy over all subgraphs H of a graph G of the neighborhood set system of H is sandwiched between Ω(logdeg(G)) and O(deg(G)), where deg(G) denotes the degeneracy of G. We extend this result to inequalities relating weak coloring numbers and discrepancy of graph powers and deduce a new characterization of bounded expansion classes. Then we switch to a model theoretical point of view, introduce pointer structures, and study their relations to graph classes with bounded expansion. We deduce that a monotone class of graphs has bounded expansion if and only if all the set systems definable in this class have bounded hereditary discrepancy. Using known bounds on the VC-density of set systems definable in nowhere dense classes we also give a characterization of nowhere dense classes in terms of discrepancy. As consequences of our results, we obtain a corollary on the discrepancy of neighborhood set systems of edge colored graphs, a polynomial-time algorithm to compute ε-approximations of size O(1/ε) for set systems definable in bounded expansion classes, an application to clique coloring, and even the non-existence of a quantifier elimination scheme for nowhere dense classes.

Název v anglickém jazyce

Discrepancy and sparsity

Popis výsledku anglicky

We study the connections between the notions of combinatorial discrepancy and graph degeneracy. In particular, we prove that the maximum discrepancy over all subgraphs H of a graph G of the neighborhood set system of H is sandwiched between Ω(logdeg(G)) and O(deg(G)), where deg(G) denotes the degeneracy of G. We extend this result to inequalities relating weak coloring numbers and discrepancy of graph powers and deduce a new characterization of bounded expansion classes. Then we switch to a model theoretical point of view, introduce pointer structures, and study their relations to graph classes with bounded expansion. We deduce that a monotone class of graphs has bounded expansion if and only if all the set systems definable in this class have bounded hereditary discrepancy. Using known bounds on the VC-density of set systems definable in nowhere dense classes we also give a characterization of nowhere dense classes in terms of discrepancy. As consequences of our results, we obtain a corollary on the discrepancy of neighborhood set systems of edge colored graphs, a polynomial-time algorithm to compute ε-approximations of size O(1/ε) for set systems definable in bounded expansion classes, an application to clique coloring, and even the non-existence of a quantifier elimination scheme for nowhere dense classes.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název periodika

Journal of Combinatorial Theory. Series B

ISSN

0095-8956

e-ISSN

1096-0902

Svazek periodika

169

Číslo periodika v rámci svazku

November 2024

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

38

Strana od-do

96-133

Kód UT WoS článku

001362291600001

EID výsledku v databázi Scopus

2-s2.0-85196257941