Discrepancy and sparsity

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Discrepancy and sparsity

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

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

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2024

Confidentiality

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

Name of the periodical

Journal of Combinatorial Theory. Series B

ISSN

0095-8956

e-ISSN

1096-0902

Volume of the periodical

169

Issue of the periodical within the volume

November 2024

Country of publishing house

US - UNITED STATES

Number of pages

38

Pages from-to

96-133

UT code for WoS article

001362291600001

EID of the result in the Scopus database

2-s2.0-85196257941