Discrepancy and sparsity

DOI10.1016/J.JCTB.2024.06.001MaRDI QIDQ6615750zbMATH OpenFDO

Authors Yiting Jiang, P. Ossona de Mendez, Sebastian Siebertz, Alexandre Vigny

Publication date 8 October 2024

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCTB.2024.06.001

zbMATH Keywords

clique coloringdefinable set systemsdiscrepancyepsilon-approximationfirst-order logicgraph sparsitypointer structuresquantifier eliminationVC-densityweak coloring numbers

Mathematics Subject Classification ID

Classical first-order logic (03B10) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Recommendations

• Sparsity. Graphs, structures, and algorithms
• Structural sparsity
• On the number of types in sparse graphs
• Discrepancy in graphs and hypergraphs
• Nowhere dense graph classes and dimension

Cites work

• ``Integer-making theorems
• A combinatorial problem; stability and order for models and theories in infinitary languages
• A note on the Beck-Fiala theorem
• Algorithmic aspects of combinatorial discrepancy
• An improvement of the Beck-Fiala theorem
• Classification theory and the number of non-isomorphic models.
• Clustering powers of sparse graphs
• Coloring and covering nowhere dense graphs
• Colouring graphs with bounded generalized colouring number
• Constant-factor approximation of the domination number in sparse graphs
• Deterministic discrepancy minimization via the multiplicative weight update method
• Discrepancy and approximations for bounded VC-dimension
• Elements of finite model theory.
• Elements of Information Theory
• First-order interpretations of bounded expansion classes
• Geometric discrepancy. An illustrated guide
• Geometric discrepancy. An illustrated guide
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Graph theory
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• Interpreting nowhere dense graph classes as a classical notion of model theory
• Norm-graphs: Variations and applications
• Nowhere dense classes of graphs
• On the density of families of sets
• On the number of types in sparse graphs
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Orderings on graphs and game coloring number
• Perfect graphs of arbitrarily large clique-chromatic number
• Quasi-optimal range searching in spaces of finite VC-dimension
• Regular partitions of gentle graphs
• Sequences, discrepancies and applications
• Six Standard Deviations Suffice
• Sparsity. Graphs, structures, and algorithms
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• Structural Properties of the First-Order Transduction Quasiorder
• Testing first-order properties for subclasses of sparse graphs
• Tight hardness results for minimizing discrepancy
• Tight upper bounds for the discrepancy of half-spaces
• Tree-depth, subgraph coloring and homomorphism bounds
• Two-colouring all two-element maximal antichains

Cited in

(1)

• Advances in algorithmic meta theorems (invited paper)

This page was built for publication: Discrepancy and sparsity

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