Skip to content
DraconiticResearch
Search Sources API
197,788 studies31 sourcesUpdated 40 min ago
PreprintarXiv licencearXiv

Induced-Count Discrepancy in Uniform Hypergraphs

  • Chenglong Yu
Open at sourcePDFDOICite

Abstract

Let uk(r)(H,p) be the maximum, over all k-vertex r-uniform hypergraphs F, of the absolute difference between the number of induced copies of F in H and its expectation in the binomial random r-graph with the same number of vertices as H and edge probability p. Let uk(r)(n,p) be the minimum of uk(r)(H,p) over all n-vertex r-uniform hypergraphs, and let Dr(n,p) be the distance from pbinom nr to the nearest integer. For fixed r≥3, k≥2r and ε>0, the quantity uk(r)(n,p) has order max {Dr(n,p),p(1−p)}nk−r whenever p(1−p)n⌊ r/2⌋/(binom2r−2r−1)≥ε. Using local moment estimates and switchings in a sparse reservoir, we construct one hypergraph with the nearest-integer edge count that controls all induced orders simultaneously.

Related

  1. Low discrepancy and spectral gap for directed hypergraphs via spectral regularity lemma for tensors
    Hiep Han
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Phase transition of random non-uniform hypergraphs
    Élie de Panafieu
    Journal of Discrete AlgorithmsPeer-reviewedLicence not statedFull text17 citedCombinatorics & discrete mathematicsHAL
  3. Irregular Triads in 3-Uniform Hypergraphs
    C. Terry, J. Wolf
    Memoirs of the American Mathematical SocietyPeer-reviewedLicence not statedFull text30 citedCombinatorics & discrete mathematicsOpenAlex
  4. Towards the Erdős matching conjecture for 4‐uniform hypergraphs: Stability and applications
    Péter Frankl, Hongliang Lu, Jie Ma +1
    MathematikaPeer-reviewedLicence not statedFull text11 citedCombinatorics & discrete mathematicsOpenAlex
  5. On the growth of weak regular partitions in k-uniform hypergraphs
    H. Sheats, C. Terry
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsLogic & foundationsarXiv

Cite

BibTeXRIS
BibTeX
@misc{yu2026inducedcount,
  title = {{Induced-Count Discrepancy in Uniform Hypergraphs}},
  author = {Chenglong Yu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.14712},
  eprint = {2610.14712},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.14712},
}
RIS
TY  - UNPB
TI  - Induced-Count Discrepancy in Uniform Hypergraphs
AU  - Chenglong Yu
PY  - 2026
DA  - 2026/10/10
PB  - arXiv
DO  - 10.48550/arxiv.2610.14712
UR  - https://arxiv.org/abs/2610.14712
AB  - Let u_k^(r)(H,p) be the maximum, over all k-vertex r-uniform hypergraphs F, of the absolute difference between the number of induced copies of F in H and its expectation in the binomial random r-graph with the same number of vertices as H and edge probability p. Let u_k^(r)(n,p) be the minimum of u_k^(r)(H,p) over all n-vertex r-uniform hypergraphs, and let D_r(n,p) be the distance from pbinom nr to the nearest integer. For fixed r≥3, k≥2r and ε>0, the quantity u_k^(r)(n,p) has order max {D_r(n,p),p(1−p)}n^k−r whenever p(1−p)n^⌊ r/2⌋/(binom2r−2r−1)≥ε. Using local moment estimates and switchings in a sparse reservoir, we construct one hypergraph with the nearest-integer edge count that controls all induced orders simultaneously.
ER  -