On the number of types in sparse graphs

DOI10.1145/3209108.3209178MaRDI QIDQ5145357zbMATH OpenOpenAlexWikidataFDO

Authors Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk

Publication date 20 January 2021

Published in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.09336

zbMATH Keywords

first-order typesnowhere dense graphsstabilityStone spaceuniform quasi-widenessVC-density

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Classification theory, stability, and related concepts in model theory (03C45) Density (toughness, etc.) (05C42)

Abstract: We prove that for every class of graphs $mathcalC$ which is nowhere dense, as defined by Nesetril and Ossona de Mendez, and for every first order formula $$, whenever one draws a graph $GinmathcalC$ and a subset of its nodes $A$, the number of subsets of $$ which are of the form $$ for some valuation $$ of $$ in $G$ is bounded by $$, for every $epsilon>0$. This provides optimal bounds on the VC-density of first-order definable set systems in nowhere dense graph classes. We also give two new proofs of upper bounds on quantities in nowhere dense classes which are relevant for their logical treatment. Firstly, we provide a new proof of the fact that nowhere dense classes are uniformly quasi-wide, implying explicit, polynomial upper bounds on the functions relating the two notions. Secondly, we give a new combinatorial proof of the result of Adler and Adler stating that every nowhere dense class of graphs is stable. In contrast to the previous proofs of the above results, our proofs are completely finitistic and constructive, and yield explicit and computable upper bounds on quantities related to uniform quasi-wideness (margins) and stability (ladder indices).

Recommendations

• On nowhere dense graphs
• First order properties on nowhere dense structures
• Interpreting nowhere dense graph classes as a classical notion of model theory

Cited in

(23)

• Reconfiguration on nowhere dense graph classes
• Regular partitions of gentle graphs
• Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
• On nowhere dense graphs
• Interpreting nowhere dense graph classes as a classical notion of model theory
• Kernelization and approximation of distance-r independent sets on nowhere dense graphs
• Bounds on half graph orders in powers of sparse graphs
• Counting homomorphisms to sparse graphs
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• scientific article; zbMATH DE number 7559449 (Why is no real title available?)
• Progressive algorithms for domination and independence
• Lossy kernels for connected dominating set on sparse graphs
• Erdös-Hajnal properties for powers of sparse graphs
• scientific article; zbMATH DE number 7764115 (Why is no real title available?)
• Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
• How many F's are there in G?
• Discrepancy and sparsity
• Treelike decompositions for transductions of sparse graphs
• Data reduction for directed feedback vertex set on graphs without long induced cycles. Three rules to rule them all
• First-order transductions of graphs (invited talk)
• Kernelization complexity of solution discovery problems
• On the VC dimension of first-order logic with counting and weight aggregation
• On the parameterized complexity of reconfiguration of connected dominating sets

This page was built for publication: On the number of types in sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145357)