Skip to content
DraconiticResearch
Search Sources API
190,851 studies31 sourcesUpdated 48 min ago
PreprintCC BY 4.0arXiv

The terminal leave in random greedy hypergraph matching

  • Peter Keevash
Open at sourcePDFDOICite

Abstract

Let G be the terminal graph of the random triangle-removal process started from Kn. We prove that e(G)/n3/2→1/(2√2) in L2. More generally, we obtain the analogous result for any fixed strictly k-balanced k-graph. Our main tool is a more general theorem on random greedy matchings in nearly regular uniform hypergraphs with few short cycles under a stability assumption on the survival equations.

Related

  1. Degree Stability of Parallel Greedy Matching in Random Graphs
    Vishvajeet N, Shrinidhi Teganahally Sridhara
    arXivPreprintCC BY-SA 4.0Full textProbabilityarXiv
  2. Hypergraph Turán Problem of the Generalized Triangle with Bounded Matching Number
    Jian Wang, Wenbin Wang, Weihua Yang
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref
  3. Stability in stochastic hypergraph matching I: necessary and sufficient criteria
    Doan Dai Nguyen, Ana Bušić
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  4. Fluid Limits and Upper Bounds for Randomized Greedy Matching
    Sayan Mukherjee
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Stability in stochastic hypergraph matching II: weights, batch arrivals, and continuous time
    Doan Dai Nguyen, Ana Bušić
    arXivPreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{keevash2026terminal,
  title = {{The terminal leave in random greedy hypergraph matching}},
  author = {Peter Keevash},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.20414},
  eprint = {2610.20414},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.20414},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The terminal leave in random greedy hypergraph matching
AU  - Peter Keevash
PY  - 2026
DA  - 2026/10/14
PB  - arXiv
DO  - 10.48550/arxiv.2610.20414
UR  - https://arxiv.org/abs/2610.20414
AB  - Let G be the terminal graph of the random triangle-removal process started from K_n. We prove that e(G)/n^3/2→1/(2√2) in L^2. More generally, we obtain the analogous result for any fixed strictly k-balanced k-graph. Our main tool is a more general theorem on random greedy matchings in nearly regular uniform hypergraphs with few short cycles under a stability assumption on the survival equations.
ER  -