Pith. sign in

REVIEW 1 major objections 3 minor 1 cited by

The hypergraph removal process

T0 review · 1 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The F-removal process terminates at n^{k−1/ρ±o(1)} edges for strictly k-balanced F.

desk verdict Major advance: resolves the folklore conjecture for the F-removal process for all strictly k-balanced hypergraphs; the complete-graph case is fine despite a missing explicit verification. read the letter →

arxiv 2412.15039 v2 pith:PFSWS3J6 submitted 2024-12-19 math.CO math.PR

Felix Joos , Marcus Kühn This is my paper · ORCID
classification math.COmath.PR MSC 05C6505C8060C05
keywords hypergraphremovalprocessrandomgreedymatchingstrictlyk-balancedpseudorandomhypergraphssupermartingaleconcentrationcriticalintervalmethodtemplateembeddingsF-free
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies the random process that starts with a k-uniform hypergraph H and repeatedly deletes the edges of a copy of a fixed k-uniform hypergraph F chosen uniformly at random among the remaining copies, stopping when no copy of F is left. Its main theorem states that if F is strictly k-balanced with k-density ρ and H is a sufficiently dense pseudorandom hypergraph satisfying precise template-counting estimates, then the number of edges R(H,F) left at termination is $n^{{k−1/ρ±o(1)}}$ with high probability. Since complete k-uniform hypergraphs are strictly k-balanced, this confirms the folklore conjecture for the F-removal process in a strong form. The result is the first to determine the order of magnitude for any F beyond the triangle, and it holds for every pseudorandom starting hypergraph, not just complete ones.

What carries the argument

The load-bearing construction is a family of k-templates, called chains, built from overlapping copies of F and implicitly defined as a minimal collection closed under extension, truncation, and reduction; the paper groups them into branching families to handle possible lack of symmetry in F. For each chain and each partial embedding of its distinguished vertex set, the paper tracks the number of full embeddings into the running hypergraph. A supermartingale concentration argument shows these counts stay close to deterministic trajectories, and the self-correcting drift of the error terms is what allows the process to be followed all the way to the predicted stopping time; a second, isolation-based argument then handles the sparse endgame.

What would settle it

Start the removal process for F=K4 in a binomial random graph with p=$n^{{-1/ρ+δ}}$ (where ρ=5/2) and measure the number of edges at termination; the theorem predicts $n^{{8/5±o(1)}}$ with probability 1−exp(−(log n)^{5/4}), so observing a terminal edge count whose exponent differs from 8/5 by a fixed positive amount would falsify the central claim.

Watch

Extended reading notes

Core claim

An author would state the central claim as Theorem 1.3: for k≥2 and a strictly k-balanced k-uniform hypergraph F with k-density ρ, for every ε>0 there is δ0>0 such that if H is an (ε20, δ, ρ)-pseudorandom k-graph on n vertices with e(H) ≥ $n^{{k−1/ρ+ε5}}$, then with probability at least 1−exp(−(log n)^{5/4}) we have $n^{{k−1/ρ−ε}}$ ≤ R(H,F) ≤ $n^{{k−1/ρ+ε}}$. Since ε is arbitrary, this is R(H,F)=$n^{{k−1/ρ±o(1)}}$. The paper also proves the upper bound under the weaker hypothesis that F is merely k-balanced (Theorem 1.4), and complementary sparse-setting results (Theorems 1.5 and 1.7) guarantee that once the running hypergraph is near the predicted density, the process terminates quickly without losing too many edges.

Load-bearing premise

The proof is conditional on the starting hypergraph H satisfying the full (ε20, δ, ρ)-pseudorandomness condition, which requires every small strictly balanced template to have embedding counts within the precise error bounds (P1)–(P4); without those initial template estimates, none of the trajectory or self-correction arguments get off the ground.

Editorial extensions

If this is right

  • The folklore Conjecture 1.1 is true: for every complete k-uniform hypergraph $K_\ell^{(k)}$, the removal process leaves $n^{k-(\ell-k)/(\binom{\ell}{k}-1)\pm o(1)}$ edges with high probability.
  • The upper bound in Theorem 1.3 holds under the weaker hypothesis that F is merely k-balanced, not strictly k-balanced, as stated in Theorem 1.4.
  • The same exponent $n^{k-1/\rho\pm o(1)}$ holds for every starting hypergraph satisfying the paper's pseudorandomness condition and density bound, so the prediction is not tied to complete hypergraphs.
  • Once the process reaches a sparse hypergraph with $e(H)=n^{k-1/\rho\pm \varepsilon^4}$ and bounded template counts, Theorems 1.5 and 1.7 show it terminates quickly while still leaving at least $n^{k-1/\rho-\varepsilon}$ edges.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Extension: the implicit chain machinery likely transfers to other monotone random deletion processes, such as the F-free process, where the paper's own heuristic still leaves the logarithmic factor and constant open.
  • Extension: because the host hypergraph need only be pseudorandom rather than complete, the removal process can serve as a randomized packing algorithm on quasi-random hosts, potentially useful for approximate F-decomposition problems.
  • Extension: the universality of the exponent $k-1/\rho$ across all strictly k-balanced F suggests the terminal size is controlled by the density parameter alone, and one could test whether this extends to non-balanced F, where the paper predicts a different logarithmic behavior.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 3 minor

Summary. The paper analyzes the random F-removal process: starting from a k-uniform hypergraph H, repeatedly delete the edge set of a uniformly random copy of F until no copy remains; let R(H,F) be the number of remaining edges. The authors prove that for every strictly k-balanced k-graph F with k-density rho, and every sufficiently pseudorandom dense H, R(H,F) = n^{k-1/rho ± o(1)} with very high probability (Theorem 1.3), with a matching upper bound under only k-balancedness (Theorem 1.4) and a lower bound in a sparse regime (Theorem 1.5). They state that taking H = K_n^{(k)} gives Theorem 1.2, confirming the folklore conjecture on the size of the final hypergraph in the removal process. The proof introduces an implicit collection of 'chains' and 'branching families' to track the relevant substructure counts without explicit descriptions, then uses critical-interval supermartingale arguments; the final lower bound is obtained by an isolation argument in the sparse phase.

Significance. If the proof is correct, this is a landmark result: it resolves the folklore conjecture on the order of magnitude of the removal process for all strictly k-balanced hypergraphs, not just triangles or complete graphs. The main technical achievement is replacing the explicit, triangle-specific 'ladders' of Bohman--Frieze--Lubetzky by an implicit, minimal, transformation-closed chain collection, allowing the analysis to be carried out for general strictly balanced templates. The paper is also careful to state all error terms, stopping times, and concentration arguments, and the exponent rho is not fitted after the fact: it enters through the definitions of k-density and pseudorandomness, so the central derivation is not circular. The conditional nature of the main theorem on pseudorandomness is clear, and the random-graph example is discussed, but the key special case of complete starting hypergraphs is left unverified (see major comment).

major comments (1)
  1. [Theorems 1.2 and 1.3; Section 15] Theorem 1.2 is announced as an immediate consequence of Theorem 1.3, but Theorem 1.3 is conditional on H being (ε20,δ,ρ)-pseudorandom, and the paper never verifies that the complete k-graph K_n^{(k)} has this property. For H = K_n^{(k)} one has ϑ = 1, so ζ = n^{δ-1/2} and the exact embedding count is Φ = (n-|I|)_{|V(A)|-|I|}, giving Φ/φhat = 1 + O(1/n). The comparison of this O(1/n) error with the tolerances in (P1)–(P4) is plausible and likely routine, but it is load-bearing: Theorem 1.2 is the headline folklore conjecture, and without an explicit verification that K_n^{(k)} satisfies (P1)–(P4) the statement does not follow from the pseudorandom theorem. The proof of Theorem 1.2 should include a short lemma checking this, or state it as an explicit hypothesis.
minor comments (3)
  1. [Section 6] The displayed list of stopping times reads 'τH∗, τB, τB′, τC, τB', with τB appearing twice; presumably one occurrence is intended to be the later branching-family stopping time or another symbol should be used.
  2. [Sections 7 and 9.2] The symbol τB is used for two distinct stopping times: the balanced-template stopping time in Section 7 and the branching-family stopping time in Section 9.2. This is confusing and should be fixed by renaming one of them.
  3. [Proof of Lemma 8.32] The sentence 'We show that this bound is a consequence of We show that this bound is a consequence of Freedman's inequality for supermartingales' contains a duplicated phrase and should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the claimed R(H,F)=n^{k-1/rho±o(1)} is derived from the pseudorandomness hypothesis and independent concentration arguments, not from a fitted parameter or a self-citation chain.

full rationale

The paper's central assertion is Theorem 1.3, which is conditional on an explicit pseudorandomness hypothesis: H is (epsilon^20, delta, rho)-pseudorandom and e(H) >= n^{k-1/rho+epsilon^5}. The exponent rho enters through the prior definitions of k-density and through the pseudorandomness parameters, but it is not fitted from the target quantity R(H,F). Lemma 7.4 derives the initial estimates for all relevant embedding counts directly from the pseudorandomness conditions (P1)-(P4); those estimates are inputs, not renamed outputs of the theorem. The proof then uses supermartingale concentration (Freedman's inequality and Azuma's inequality) to show that key quantities follow deterministic trajectories that are computed from expected one-step changes of the removal process, so the bounds on R(H,F) are conclusions of an independent probabilistic derivation. No parameter appearing in the final bound is calibrated against R(H,F) or against the folklore conjecture; no equation in the paper reduces the theorem to its own conclusion by construction. The heavy reliance on [6] (Bohman, Frieze and Lubetzky) is a citation to independent prior work, not a self-citation by the present authors, and it is used for technique rather than as the source of the main theorem. The skeptic's concern that Theorem 1.2 requires K_n^{(k)} to satisfy the pseudorandomness properties P1-P4, which the paper does not explicitly verify, is a potential completeness or correctness issue rather than a circularity: a conditional theorem is not circular merely because one proposed corollary instance is not fully checked. The derivation chain for the stated conditional result is self-contained given its hypotheses, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim is a theorem under explicit pseudorandomness and balancedness assumptions. No parameters are fitted to data; epsilon and delta are asymptotic constants fixed by the statements. The proof relies on standard concentration inequalities and on known pseudorandomness of binomial random hypergraphs, which are cited and used as lemmas.

assumptions (4)
  • domain assumption The initial hypergraph H satisfies (epsilon20, delta, rho)-pseudorandomness as defined by properties (P1)-(P4).
    Assumption in Theorem 1.3; all template embedding estimates for the process start from these bounds.
  • domain assumption The hypergraph F is strictly k-balanced, equivalently (F,f) is strictly balanced for every edge f.
    Central hypothesis of Theorems 1.2 and 1.3; used in density lemmas for unions and cyclic walks of copies.
  • standard math Standard concentration inequalities: Chernoff, Janson, Freedman's supermartingale inequality, Azuma's inequality.
    Used throughout Sections 7-9, 13 and appendices to prove concentration of key quantities around deterministic trajectories.
  • standard math The binomial random k-graph with edge probability p >= n^{-1/rho+delta^{1/2}} is (epsilon,delta,rho)-pseudorandom, relying on Chernoff, Janson and known upper-tail results.
    Bridges the abstract pseudorandomness condition to concrete random hypergraph models.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The hypergraph removal process." pith.science (2026). https://pith.science/paper/PFSWS3J6

@misc{pith2026241215039,
  author       = {Pith},
  title        = {Pith review of: The hypergraph removal process},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PFSWS3J6}},
  note         = {Machine review of arXiv:2412.15039}
}
abstract

Let $k\geq 2$ and fix a $k$-uniform hypergraph $\mathcal{F}$. Consider the random process that, starting from a $k$-uniform hypergraph $\mathcal{H}$ on $n$ vertices, repeatedly deletes the edges of a copy of $\mathcal{F}$ chosen uniformly at random and terminates when no copies of $\mathcal{F}$ remain. Let $R(\mathcal{H},\mathcal{F})$ denote the number of edges that are left after termination. We show that $R(\mathcal{H},\mathcal{F})=n^{k-1/\rho\pm o(1)}$, where $\rho:=(\lvert E(\mathcal{F})\rvert-1)/(\lvert V(\mathcal{F})\rvert -k)$, holds with high probability provided that $\mathcal{F}$ is strictly $k$-balanced and $\mathcal{H}$ is sufficiently dense with pseudorandom properties. Since we may in particular choose $\mathcal{F}$ and $\mathcal{H}$ to be complete graphs, this confirms the major folklore conjecture in the area in a very strong form.

Figures

Figures reproduced from arXiv: 2412.15039 by the authors.

Figure 1
Figure 1. A 3-uniform chain template (C, I) for the special case where F = K (3) 4 . The chain template is given by a chain c = (F, V, I) where I = {1, 2} and where F = F1, . . . , F50 is a sequence of 50 copies of F whose vertices are elements of {1, . . . , 54}. The vertex sets of these copies are listed below the visualization of the chain template and for each copy Fi with 1 ≤ i ≤ 49, the unique vertex of Fi that is not a… view at source ↗
Figure 2
Figure 2. Examples for choices of the copies GU and G ′ U for the special case where F is a 3-uniform 1-cherry. Each example shows the situation of the edges containing U = {u} as a subset at step iU . R(i ⋆ ) ⊆ U where we collect k ′ -sets at which almost isolation occurs. We inductively define R(i) with 1 ≤ i ≤ i ⋆ as described by the following procedure. Algorithm D.5: Construction of R(i). 1 R(i) ← R(i − 1) 2 consider an … view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A new lower bound for the Ramsey numbers $R(3,k)$

    math.CO 2025-05 conditional novelty 9.0 of 10

    For every large k there exists a triangle-free graph on roughly k^2/(3 log k) vertices with no independent set of size k.

Reference graph

Works this paper leans on

31 extracted references · 30 canonical work pages · cited by 1 Pith paper

  1. [1]

    Alon, J.-H

    N. Alon, J.-H. Kim, and J. Spencer, Nearly perfect matchings in regular simple hypergraphs , Israel J. Math. 100 (1997), 171–187

    work page 1997

  2. [2]

    Bennett and T

    P. Bennett and T. Bohman, A note on the random greedy independent set algorithm , Random Structures Algorithms 49 (2016), 479–502

    work page 2016

  3. [3]

    , A natural barrier in random greedy hypergraph matching , Combin. Probab. Comput. 28 (2019), 816–825

    work page 2019

  4. [4]

    Bohman, The triangle-free process, Adv

    T. Bohman, The triangle-free process, Adv. Math. 221 (2009), 1653–1677

    2009

  5. [5]

    Bohman, A

    T. Bohman, A. Frieze, and E. Lubetzky, A note on the random greedy triangle-packing algorithm , J. Comb. 1 (2010), 477–488

    work page 2010

  6. [6]

    , Random triangle removal , Adv. Math. 280 (2015), 379–438

    work page 2015

  7. [7]

    Bohman and P

    T. Bohman and P. Keevash, The early evolution of the H-free process, Invent. Math. 181 (2010), 291–336

    work page 2010

  8. [8]

    , Dynamic concentration of the triangle-free process, Random Structures Algorithms 58 (2021), 221–293

    work page 2021

Show all 31 references
  1. [9]

    Bohman and M

    T. Bohman and M. E. Picollelli, SIR epidemics on random graphs with a fixed degree sequence , Random Structures Algorithms 41 (2012), 179–214

    2012

  2. [10]

    Bollob´ as and O

    B. Bollob´ as and O. Riordan,Constrained graph processes, Electron. J. Combin. 7 (2000), Research Paper 18, 20

    2000

  3. [11]

    Random Graphs ’93

    P. Erd˝ os, S. Suen, and P. Winkler, On the size of a random maximal graph , Proceedings of the Sixth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science, “Random Graphs ’93” (Pozna´ n, 1993), vol. 6, 1995, pp. 309–318

    1993

  4. [12]

    Fiz Pontiveros, S

    G. Fiz Pontiveros, S. Griffiths, and R. Morris, The triangle-free process and the Ramsey number R(3, k), Mem. Amer. Math. Soc. 263 (2020), v+125

    2020

  5. [13]

    D. A. Freedman, On tail probabilities for martingales , Ann. Probab. 3 (1975), 100–118

    1975

  6. [14]

    Glock, F

    S. Glock, F. Joos, J. Kim, M. K¨ uhn, and L. Lichev, Conflict-free hypergraph matchings, J. Lond. Math. Soc. (2) 109 (2024), Paper No. e12899, 78

    2024

  7. [15]

    D. A. Grable, On random greedy triangle packing , Electron. J. Combin. 4 (1997), Research Paper 11, 19

    1997

  8. [16]

    Hofstad, Behaviour of the minimum degree throughout the d-process, Combin

    J. Hofstad, Behaviour of the minimum degree throughout the d-process, Combin. Probab. Comput. 33 (2024), 564–582

    2024

  9. [17]

    Janson, Poisson approximation for large deviations , Random Structures Algorithms 1 (1990), 221–229

    S. Janson, Poisson approximation for large deviations , Random Structures Algorithms 1 (1990), 221–229

    1990

  10. [18]

    Janson and A

    S. Janson and A. Ruci´ nski,The deletion method for upper tail estimates , Combinatorica 24 (2004), 615–640

    2004

  11. [19]

    K¨ uhn, D

    D. K¨ uhn, D. Osthus, and A. Taylor,On the random greedy F -free hypergraph process, SIAM J. Discrete Math. 30 (2016), 1343–1350

    2016

  12. [20]

    Osthus and A

    D. Osthus and A. Taraz, Random maximal H-free graphs, Random Structures Algorithms 18 (2001), 61–82

    2001

  13. [21]

    M. E. Picollelli, The final size of the C4-free process, Combin. Probab. Comput. 20 (2011), 939–955

    2011

  14. [22]

    , The diamond-free process, Random Structures Algorithms 45 (2014), 513–551

    2014

  15. [23]

    Discrete Math

    , The final size of the Cℓ-free process, SIAM J. Discrete Math. 28 (2014), 1276–1305

    2014

  16. [24]

    R¨ odl and L

    V. R¨ odl and L. Thoma,Asymptotic packing and the random greedy algorithm , Random Structures Algorithms 8 (1996), 161–177

    1996

  17. [25]

    Ruci´ nski and N

    A. Ruci´ nski and N. C. Wormald,Random graph processes with degree restrictions, Combin. Probab. Comput. 1 (1992), 169–180

    1992

  18. [26]

    Spencer, Asymptotic packing via a branching process , Random Structures Algorithms 7 (1995), 167–172

    J. Spencer, Asymptotic packing via a branching process , Random Structures Algorithms 7 (1995), 167–172

    1995

  19. [27]

    , Maximal trianglefree graphs and Ramsey R(3, k), unpublished manuscript, 1995

    1995

  20. [28]

    Telcs, N

    A. Telcs, N. Wormald, and S. Zhou, Hamiltonicity of random graphs produced by 2-processes , Random Structures Algorithms 31 (2007), 450–481

    2007

  21. [29]

    Warnke, The Cℓ-free process, Random Structures Algorithms 44 (2014), 490–526

    L. Warnke, The Cℓ-free process, Random Structures Algorithms 44 (2014), 490–526

    2014

  22. [30]

    , When does the K4-free process stop?, Random Structures Algorithms 44 (2014), 355–397

    2014

  23. [31]

    N. C. Wormald, The differential equation method for random graph processes and greedy algorithms , In M. Karo´ nski and H. Pr¨ omel, Eds., Lectures on Approximation and Randomized Algorithms (1999), 73–155. THE HYPERGRAPH REMOV AL PROCESS 67 Appendix A. Counting copies ofF In ...

    1999

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.