Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 34 min ago
PreprintCC BY 4.0arXiv

Linear-length cycles in the supercritical percolated hypercube

  • Michael Anastos
Open at sourcePDFDOICite

Abstract

Let Qpd be the random subgraph of the d-dimensional binary hypercube obtained by retaining each edge independently with probability p. A long-standing folklore conjecture states that the emergence of the giant component in Qpd, at p≈ 1/d, is accompanied by the emergence of cycles of linear length. We confirm this conjecture and determine the order of the longest cycle near the phase transition. Specifically, for every sufficiently small constant ε>0, we show that if p=(1+ε)/d, then with high probability the longest cycle of Qpd has length Θ(ε2 2d). The dependence on ε is optimal up to constant factors.

Related

  1. Counting hypergraphs without linear cycles of fixed length
    József Balogh, Ramon I. Garcia, Abhishek Methuku
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Polynomial Length Cycles In Tough Graphs
    Levi Segal, Jacques Verstraete
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Limit theorems for supercritical branching processes in Markovian environment with linear fractional offspring distributions
    Yinna Ye, Quansheng Liu
    arXivPreprintCC BY-NC-ND 4.0Full textProbabilityarXiv
  4. Extremal graphs without cycles of length 0 modulo 4
    Yanan Hu, Leilei Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. On graphs without cycles of length $0$ modulo $3$ or $4$ modulo $6$
    Takahiro Ueoro
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{anastos2026linearlength,
  title = {{Linear-length cycles in the supercritical percolated hypercube}},
  author = {Michael Anastos},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05634},
  eprint = {2611.05634},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05634},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Linear-length cycles in the supercritical percolated hypercube
AU  - Michael Anastos
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.05634
UR  - https://arxiv.org/abs/2611.05634
AB  - Let Q_p^d be the random subgraph of the d-dimensional binary hypercube obtained by retaining each edge independently with probability p. A long-standing folklore conjecture states that the emergence of the giant component in Q_p^d, at p≈ 1/d, is accompanied by the emergence of cycles of linear length. We confirm this conjecture and determine the order of the longest cycle near the phase transition. Specifically, for every sufficiently small constant ε>0, we show that if p=(1+ε)/d, then with high probability the longest cycle of Q_p^d has length Θ(ε^2 2^d). The dependence on ε is optimal up to constant factors.
ER  -