PreprintCC BY 4.0arXiv
A Direct Proof of the Locally Dense Graphon Inequality
Abstract
Bradač, Sudakov, and Wigderson characterized p-locally dense graphons by a quadratic inequality for all bounded nonnegative functions. Their proof uses Reiher's finite lemma and graphon approximation, and they asked for a direct proof. We give one by rounding simple functions. Divide each level set into m equal-measure pieces and retain each piece independently with probability equal to its level. Off-diagonal terms agree in expectation; the diagonal error is at most norminfW−p/(4m). Letting m→∞ and then approximating in L1 proves the inequality. A three-atom example shows that atomlessness is necessary if arbitrary probability spaces are allowed.
Related
- Counting cographs in locally dense graphs
- A proof of Alexander’s Conjecture on an Inequality of Cassels
- The sharp σk-curvature inequality on locally conformally flat manifolds in quantitative form
- A short proof of the complete Crouzeix inequality in dimension three
- A new proof of equality cases of the Brunn-Minkowski inequality on manifolds
BibTeX
@misc{menezes2026direct,
title = {{A Direct Proof of the Locally Dense Graphon Inequality}},
author = {Dean Menezes},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19014},
eprint = {2609.19014},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19014},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Direct Proof of the Locally Dense Graphon Inequality
AU - Dean Menezes
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.19014
UR - https://arxiv.org/abs/2609.19014
AB - Bradač, Sudakov, and Wigderson characterized p-locally dense graphons by a quadratic inequality for all bounded nonnegative functions. Their proof uses Reiher's finite lemma and graphon approximation, and they asked for a direct proof. We give one by rounding simple functions. Divide each level set into m equal-measure pieces and retain each piece independently with probability equal to its level. Off-diagonal terms agree in expectation; the diagonal error is at most norminfW−p/(4m). Letting m→∞ and then approximating in L^1 proves the inequality. A three-atom example shows that atomlessness is necessary if arbitrary probability spaces are allowed.
ER -