Simplified dense model theorem for random discrete structures
math.CO
Submitted: 2026-10-29
Updated: 2026-10-29
Comments: 19 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
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 papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality