Discrepancy and sparsity
From MaRDI portal
Publication:6615750
DOI10.1016/j.jctb.2024.06.001zbMath1548.05191MaRDI QIDQ6615750
Sebastian Siebertz, Unnamed Author, Yiting Jiang, Patrice Ossona de Mendez, Alexandre Vigny
Publication date: 8 October 2024
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
first-order logicquantifier eliminationdiscrepancyclique coloringVC-densitypointer structuresgraph sparsityepsilon-approximationweak coloring numbersdefinable set systems
Classical first-order logic (03B10) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- Sequences, discrepancies and applications
- Elements of finite model theory.
- Perfect graphs of arbitrarily large clique-chromatic number
- Colouring graphs with bounded generalized colouring number
- ``Integer-making theorems
- Two-colouring all two-element maximal antichains
- Classification theory and the number of non-isomorphic models.
- Norm-graphs: Variations and applications
- Discrepancy and approximations for bounded VC-dimension
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- A note on the Beck-Fiala theorem
- Quasi-optimal range searching in spaces of finite VC-dimension
- Orderings on graphs and game coloring number
- Tight upper bounds for the discrepancy of half-spaces
- Constant-factor approximation of the domination number in sparse graphs
- Clustering powers of sparse graphs
- Regular partitions of gentle graphs
- Deterministic discrepancy minimization via the multiplicative weight update method
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Interpreting nowhere dense graph classes as a classical notion of model theory
- Tree-depth, subgraph coloring and homomorphism bounds
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- Graph Theory
- Six Standard Deviations Suffice
- Coloring and Covering Nowhere Dense Graphs
- Deciding First-Order Properties of Nowhere Dense Graphs
- First-Order Interpretations of Bounded Expansion Classes
- On the number of types in sparse graphs
- Algorithmic Aspects of Combinatorial Discrepancy
- An Improvement of the Beck–Fiala Theorem
- Testing first-order properties for subclasses of sparse graphs
- Elements of Information Theory
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Geometric discrepancy. An illustrated guide
- Geometric discrepancy. An illustrated guide
- Structural Properties of the First-Order Transduction Quasiorder
- Nowhere dense classes of graphs
This page was built for publication: Discrepancy and sparsity
