Simplified dense model theorem for random discrete structures
Abstract
Dense model theorems of Conlon and Gowers associate to each subset of a sparse random structure a dense set with approximately the same size and configuration counts after rescaling. This allows dense extremal results to be transferred to the random setting. Allen, Böttcher, Lada, and Mergoni Cecchelli recently generalised this approach and established a dense model theorem in an abstract hypergraph framework, with hypotheses that are readily verified in many applications. Both proofs use the separating hyperplane theorem to reduce the existence of dense models to an anti-correlation estimate. We give a simplified proof of a version of this theorem, inspired by the method of hypergraph containers. Our proof constructs dense models from small fingerprints, combining sampling with the Rödl-Ruciński deletion method.
Related
- The singularity probability of dense random regular graphs
- Large corank of dense random regular digraphs
- A Uniform Product-Difference Theorem for Dense Subsets of ℤ2
- Rank and Invertibility of Dense Signed Random Regular Matrices
- Michell-Prager type truss structures constructed from integrable discrete power function and discrete logarithmic function
BibTeX
@misc{nenadov2026simplified,
title = {{Simplified dense model theorem for random discrete structures}},
author = {Rajko Nenadov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39176},
eprint = {2610.39176},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39176},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Simplified dense model theorem for random discrete structures
AU - Rajko Nenadov
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39176
UR - https://arxiv.org/abs/2610.39176
AB - Dense model theorems of Conlon and Gowers associate to each subset of a sparse random structure a dense set with approximately the same size and configuration counts after rescaling. This allows dense extremal results to be transferred to the random setting. Allen, Böttcher, Lada, and Mergoni Cecchelli recently generalised this approach and established a dense model theorem in an abstract hypergraph framework, with hypotheses that are readily verified in many applications. Both proofs use the separating hyperplane theorem to reduce the existence of dense models to an anti-correlation estimate. We give a simplified proof of a version of this theorem, inspired by the method of hypergraph containers. Our proof constructs dense models from small fingerprints, combining sampling with the Rödl-Ruciński deletion method.
ER -