Pith. sign in

REVIEW 3 major objections 4 minor 68 references

Erd\H{o}s meets Nash-Williams

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Any sufficiently large $K_3$-divisible graph with minimum degree at least $(\max\{\delta^*_{K_3}, 3/4\} + \varepsilon)n$ admits a triangle decomposition of girth at least any prescribed $g$.

desk verdict Real reduction of the Erdős–Nash-Williams conjecture to the fractional threshold, but the proof's load-bearing girth-booster lemma is imported unproved from an unpublished preprint. read the letter →

arxiv 2507.23624 v1 pith:PVH73TJE submitted 2025-07-31 math.CO

Michelle Delcourt , Cicely (Cece) Henderson , Thomas Lesgourgues , Luke Postle This is my paper
classification math.CO MSC 05C7005B3005C35
keywords triangledecompositionSteinertriplesystemsgirthrefinedabsorptionfractionalthresholdminimumdegreeK3-divisiblegraphsextremaldesigntheory
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

This paper establishes that high girth is a free extra condition in the dense regime of triangle decompositions. Theorem 1.2 states that for every prescribed integer $g \geq 3$ and every $\varepsilon > 0$, any sufficiently large graph on $n$ vertices that is $K_3$-divisible (its edge count is divisible by 3 and every vertex degree is even) and has minimum degree at least $(\max\{\delta^*_{K_3}, 3/4\} + \varepsilon)n$ admits a decomposition of its edges into triangles with girth at least $g$ — meaning no $g' \leq g$ triangles span fewer than $g' + 2$ vertices. The only unknown in the bound is $\delta^*_{K_3}$, the fractional triangle-decomposition threshold, so the combined 2021 conjecture reduces to the fractional relaxation of the 1970 minimum-degree conjecture; substituting the best known bound $\delta^*_{K_3} \leq \frac{7+\sqrt{21}}{14} \approx 0.82733$ yields the explicit corollary that minimum degree $0.82733n + \varepsilon n$ suffices. The paper matters because it ties two classical directions — decompositions of dense graphs and locally sparse Steiner triple systems — to a single threshold, and because it is the first adaptation of refined absorption to a minimum-degree problem, supplying new proofs of both earlier headline results.

What carries the argument

The load-bearing object is the $C$-refined $K_3$-omni-absorber: a graph $A$ for a reserved random edge set $X$ such that for every $K_3$-divisible subgraph $L$ of $X$, a designated family of triangles decomposes $A \cup L$, with every edge of $A \cup X$ occurring in at most $C$ triangles of the family. The proof proceeds in four movements: (1) a sparse random reserve $X \subseteq G$ is chosen by Chernoff bounds; (2) an omni-absorber for $X$ is embedded inside $G$ via 'fake edges' and absorbers of rooted degeneracy at most $2q-2$, adapting the refined efficient omni-absorber theorem to the minimum-degree setting; (3) girth is imposed by attaching $g$-spheres — rooted boosters with two disjoint high-girth triangle decompositions and rooted degeneracy 4 — to every triangle of the absorber, using a quantum-booster extraction (Theorem A.7, resting on Lemma A.8) that supplies many disjoint boosters per root; and (4) regularity is boosted to polynomial error $n^{-1/3}$ through a seeded, balanced fractional decomposition (Theorem 2.12) in which every clique carries weight at least $\sigma / \binom{n-2}{q-2}$, so the General Boosting Lemma yields a regular triangle family avoiding all 'dangerous' low-girth cliques, and the Forbidden Submatchings with Reserves theorem completes the packing.

What would settle it

Construct a $K_3$-divisible graph on $n$ vertices with minimum degree at least $(\frac{7+\sqrt{21}}{14} + \varepsilon)n$ that provably admits no triangle decomposition of girth $g$ for some fixed $g \geq 3$; that would refute Corollary 1.3 and Theorem 1.2 directly. Short of that, the concrete place to test the proof is whether Lemmas 4.12 and 4.13 of the companion preprint [16] really imply Lemma A.8 as stated, including the constant-proportion booster condition — a gap there invalidates Theorem A.7 and the high-girth absorber step even if the fractional threshold is eventually settled.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.2: for every integer $g \geq 3$ and real $\varepsilon > 0$, any sufficiently large $K_3$-divisible graph $G$ on $n$ vertices with $\delta(G) \geq (\max\{\delta^*_{K_3}, 3/4\} + \varepsilon)n$ admits a $K_3$-decomposition with girth at least $g$. Here $K_3$-divisible means $3 \mid e(G)$ and every vertex has even degree, and $\delta^*_{K_3}$ is the fractional $K_3$-decomposition threshold: the infimum of $c$ such that every graph with minimum degree $cn$ has a fractional triangle decomposition (non-negative weights on triangles with total weight 1 on each edge). Since $\delta^*_{K_3} \leq \frac{7+\sqrt{21}}{14} \approx 0.82733$ is known, Corollary 1.3 follows: minimum degree $0.82733n + \varepsilon n$ suffices for arbitrarily prescribed girth. The authors present the theorem as a reduction: the combined conjecture, that every large $K_3$-divisible graph of minimum degree $3n/4$ has a triangle decomposition of arbitrarily large girth, now holds up to a proof that $\delta^*_{K_3} = 3/4$. The same framework extends to $K_q$-decompositions (Theorem 1.9) at minimum degree $(\max\{\delta^*_{K_q}, 1 - \frac{1}{2q-2}\} + \varepsilon)n$, and the refined-absorption route gives new independent proofs of the earlier reduction and of the 1973 high-girth conjecture.

Load-bearing premise

Everything hangs on an unproved-in-this-paper extraction lemma (Lemma A.8), summarized from two lemmas in the authors' companion preprint [16], which guarantees that sufficiently many high-girth boosters can be harvested simultaneously in the roughly $3n/4$ minimum-degree regime; if that lemma fails, the high-girth omni-absorber construction collapses and Theorem 1.2 does not follow, whatever value the fractional threshold takes.

Editorial extensions

If this is right

  • If $\delta^*_{K_3}$ is proved to equal $3/4$, Theorem 1.2 immediately yields the full combined conjecture at minimum degree $3n/4$, matching the known tight blow-up constructions.
  • The fractional threshold becomes the sole barrier: no separate high-girth obstruction remains beyond fractional triangle-decomposability.
  • At today's bound, every sufficiently large $K_3$-divisible graph with minimum degree at least $0.82733n + \varepsilon n$ admits a triangle decomposition of any prescribed girth.
  • The same machinery gives $K_q$-decompositions of prescribed girth at minimum degree $(\max\{\delta^*_{K_q}, 1 - \frac{1}{2q-2}\} + \varepsilon)n$ (Theorem 1.9).
  • The refined-absorption proof supplies new independent proofs of the earlier reduction of the 1970 conjecture and of the resolution of the 1973 high-girth conjecture, whose original proofs both used iterative absorption.

Reading between the lines

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

  • My reading: the 'seeding' step — forcing every clique of a fractional decomposition to carry weight at least $\sigma/\binom{n-2}{q-2}$ — is the most reusable idea here; it should transfer to any decomposition problem where one must avoid a sparse family of dangerous cliques, not only low-girth configurations.
  • My reading: the main theorem is conditional on the companion preprint [16] until Lemma A.8 is proved in the minimum-degree setting; a self-contained proof of that lemma is the single most valuable follow-up the paper suggests.
  • My reading: the result sets up a natural counting question — how many high-girth triangle decompositions does a dense graph admit — mirroring the counting results that accompanied the resolution of the high-girth conjecture.
  • My reading: for larger cliques the obstacle to the conjectured $1 - \frac{1}{q+1}$ bound is the tight rooted degeneracy ($2q-2$) of absorbers and girth boosters; better booster constructions would lift Theorem 1.9 toward that bound.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper proves a reduction for the combined 'Erdős meets Nash-Williams' conjecture. Theorem 1.2 asserts that, for any g ≥ 3 and ε > 0, every sufficiently large K3-divisible graph G on n vertices with δ(G) ≥ (max{δ*_{K3}, 3/4} + ε)n admits a K3-decomposition of girth at least g. Together with the Delcourt–Postle bound δ*_{K3} ≤ (7+√21)/14, this yields Corollary 1.3 at minimum degree 0.82733n + εn. The proof adapts the refined absorption method: a random reserve X is chosen, a high-girth omni-absorber A for X is embedded in G, the remaining graph is regularly boosted via a new balanced fractional decomposition theorem, and a Forbidden Submatchings with Reserves argument completes the decomposition. The paper also states a generalization Theorem 1.9 for Kq-decompositions.

Significance. If the proof is completed, Theorem 1.2 is a substantial result: it reduces a combined extremal/structural decomposition conjecture to the fractional K3-decomposition threshold, and it gives new refined-absorption proofs of the Nash–Williams and Erdős high-girth theorems. The paper contains several independently useful contributions, especially the balanced fractional decomposition theorem (Theorem 2.12), the polynomially small irregularity boosting lemma (Lemma 2.10), and the general embedding lemma (Appendix B). The proof is lengthy and mostly structured, and many parts are checked in detail. However, the central girth-booster extraction is imported from an unpublished preprint and is not re-derived, so the main theorem is not yet independently verifiable from this manuscript alone.

major comments (3)
  1. [Appendix A, Lemma A.8] Lemma A.8 is load-bearing for the entire high-girth absorption argument, but it is not proved in this manuscript. It is stated only as a summary of [16, Lemmas 4.12 and 4.13], with the sentence that the stronger version 'can be trivially extracted from their proof.' This is not a proof. In particular, property (5) of Lemma A.8, the regularity of the projected treasury after p-sparsification, is exactly what later allows the subtreasury T'' to satisfy the hypotheses of the Forbidden Submatchings with Reserves theorem (Theorem 5.5) in Section 6, while properties (2) and (4) guarantee that a common high-girth booster exists for every root. A failure of any of these properties invalidates Theorem 5.1 and hence Theorem 1.2. The authors should either prove Lemma A.8 in the appendix or provide a fully detailed derivation from [16].
  2. [Appendix A, Theorem A.7] Theorem A.7 is described as 'almost immediate' from Lemma A.8 and a Chernoff argument, but the derivation is not written out. Theorem A.7 is the bridge between the random p-sparsified quantum booster and the deterministic omni-booster required for Lemma 5.20. The probabilistic intersection argument involving Disjoint(B_F), HighGirth_g(B_F), and S needs a formal proof, because it is here that the constants c and ε are balanced. Since Lemma 5.20 and Theorem 5.1 depend on Theorem A.7, this gap is not merely expository.
  3. [Section 6, proof of Theorem 1.2] The final matching step uses Theorem 5.5 (Forbidden Submatchings with Reserves) from [14] and Theorem 2.3 (Refined Efficient Omni-Absorber) from [17] as black boxes. If these remain unpublished preprints, the manuscript should state their status or include their proofs; otherwise the reduction in Theorem 1.2 rests on three layers of external preprints ([14], [16], and [17]). This is especially relevant because Theorem 5.5 supplies the perfect matching that completes the decomposition, and the paper does not reproduce any part of its proof.
minor comments (4)
  1. [Remark 5.17] There is a typo in 'it zfrom [47, Lemmas 4.7 and 4.8]'; it should read 'it follows from'.
  2. [Proof of Lemma 5.20] The text refers to 'Theorem A.7(4)' but Theorem A.7 has only properties (1)–(3). The intended reference should be corrected, for example to property (3) or to a newly labeled property.
  3. [Section 6, proof of Theorem 1.2] The condition '4α < cg · α′' is ambiguous: later in the same paragraph the factor c^{-g} appears, so the intended condition is presumably '4α < c^g · α′'. Please clarify the notation and ensure the displayed condition matches the later estimate.
  4. [Section 2.5] In the discussion of seeded fractional decompositions, the expression 'G − S S' contains a typo (likely 'G − ⋃ S'); this should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1.2 is a genuine reduction to the fractional decomposition threshold, and its heavy reliance on the authors' prior refined-absorption machinery is a verification burden, not a circular derivation.

full rationale

The paper's central theorem, Theorem 1.2, asserts an implication: if a graph has minimum degree above max{δ*_K3, 3/4}+ε, then it has a high-girth K3-decomposition. Here δ*_K3 is the fractional K3-decomposition threshold, which is a strictly weaker and externally defined quantity. The proof uses the assumed fractional decomposition threshold as an input to produce regularity-boosted families of cliques, not as a disguised version of the high-girth decomposition conclusion. Corollary 1.3 combines this reduction with the independently published fractional bound of Delcourt and Postle [13]; the bound is not derived from the target conjecture. The main verification concern is Appendix A: Lemma A.8 is stated as a summary of Lemmas 4.12 and 4.13 of the unpublished preprint [16], and the paper says the needed stronger version 'can be trivially extracted from their proof' without re-deriving it. This lemma is load-bearing for the girth-booster extraction (Theorem A.7), and hence for the high-girth omni-absorber Theorem 5.1 and ultimately Theorem 1.2. However, this is an omitted proof and a reliance on prior work by overlapping authors, not a circularity: Lemma A.8's stated assumptions do not include the target theorem, and there is no exhibited equation in which a defined quantity is equivalent by construction to the claimed output. Under the hard rule requiring a specific reduction or a fitted parameter renamed as a prediction, no circular step can be identified. The appropriate finding is no significant circularity, with the caveat that the paper's correctness depends on the validity of the cited [16] extraction.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

No new unaccounted entities are introduced. The objects built in the proof (omni-absorbers, treasuries, girth boosters, g-spheres) are defined within standard graph and hypergraph theory; their existence is claimed through proofs or cited theorems, not postulated ad hoc. In particular there is no fitted constant or new physical/mathematical primitive whose evidence is missing.

free parameters (1)
  • δ*_K3 (fractional K3-decomposition threshold) = unknown; upper bound (7+√21)/14 ≈ 0.82733
    The central theorem is parameterized by this external threshold. Corollary 1.3 substitutes the best known upper bound from Delcourt and Postle [13], a prior paper by two of the authors. The exact value remains open, and the theorem's strength scales with it.
assumptions (3)
  • domain assumption Prior refined absorption theorems are valid: Theorem 2.3 (refined efficient omni-absorber) from [17], Theorem 5.5 (forbidden submatchings with reserves) from [14], and Lemma A.8 (girth booster extraction) from [16].
    These are invoked directly in the proof of Theorems 5.1 and 1.2; the present paper does not prove the first two and only summarizes the third.
  • domain assumption The fractional threshold δ*_K3 is well-defined and the upper bound δ*_K3 ≤ (7+√21)/14 of Delcourt and Postle [13] is correct.
    Theorem 1.2 is a reduction, so correctness of the fractional threshold bound is an input. [13] is a separate published derivation and is not derived here.
  • standard math Standard probabilistic inequalities (Chernoff, Lovász Local Lemma, Janson's inequality) and the hypergraph matching lemma (Lemma 4.2) are applicable.
    Used throughout for the reserves lemma, boosting lemma, and embedding arguments; these are standard tools in combinatorics.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Erd\H{o}s meets Nash-Williams." pith.science (2026). https://pith.science/paper/PVH73TJE

@misc{pith2026250723624,
  author       = {Pith},
  title        = {Pith review of: Erd\Hos meets Nash-Williams},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PVH73TJE}},
  note         = {Machine review of arXiv:2507.23624}
}
abstract

In 1847, Kirkman proved that there exists a Steiner triple system on $n$ vertices (equivalently a triangle decomposition of the edges of $K_n$) whenever $n$ satisfies the necessary divisibility conditions (namely $n\equiv 1,3 \mod 6$). In 1970, Nash-Williams conjectured that every graph $G$ on $n$ vertices with minimum degree at least $3n/4$ (for $n$ large enough and satisfying the necessary divisibility conditions) has a triangle decomposition. In 1973, Erd\H{o}s conjectured that for each integer $g$, there exists a Steiner triple system on $n$ vertices with girth at least $g$ (provided that $n\equiv 1,3 \mod 6$ is large enough compared to the fixed $g$). In 2021, Glock, K\"uhn, and Osthus conjectured the common generalization of these two conjectures, dubbing it the ``Erd\H{o}s meets Nash-Williams' Conjecture''. In this paper, we reduce the combined conjecture to the fractional relaxation of the Nash-Williams' Conjecture. Combined with the best known fractional bound of Delcourt and Postle, this proves the combined conjecture above when $G$ has minimum degree at least $0.82733n$. We note that our result generalizes the seminal work of Barber, K\"uhn, Lo, and Osthus on Nash-Williams' Conjecture and the resolution of Erd\H{o}s' Conjecture by Kwan, Sah, Sawhney, and Simkin. Both previous proofs of those results used the method of iterative absorption. Our proof instead proceeds via the newly developed method of refined absorption (and hence provides new independent proofs of both results).

Figures

Figures reproduced from arXiv: 2507.23624 by the authors.

Figure 1
Figure 1. A 3-sphere rooted at R = (vb1b6) It follows from this definition that Bon and Boff ∪ {R} are two Kq-decompositions of B ∪ R. If P is a Kq-packing of a graph G that uses a copy R of Kq, we can replace R by Bon to obtain a Kq-packing of B ∪ P; alternatively, if R is not in the packing P, we simply use Boff to decompose the edges of B. Our goal is then to build boosters whose decomposition families have high girth. To … view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

68 extracted references · 60 canonical work pages

  1. [16]

    Proof of the High Girth Existence Conjecture via Refined Absorption

    Michelle Delcourt and Luke Postle. Proof of the High Girth Existence Conjecture via Refined Absorp- tion. arXiv:2402.17856, 2024

    work page Pith review arXiv 2024

  2. [14]

    Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings

    Michelle Delcourt and Luke Postle. Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings. arXiv:2204.08981, 2022

    arXiv 2022

  3. [17]

    Refined Absorption: A New Proof of the Existence Conjecture

    Michelle Delcourt and Luke Postle. Refined Absorption: A New Proof of the Existence Conjecture. arXiv:2402.17855, 2024

    arXiv 2024

  4. [1]

    Jack Allsop and Ian M. Wanless. Latin squares without proper subsquares. arXiv preprint arXiv:2310.01923, 2023

    work page Pith review arXiv 2023

  5. [2]

    Probabilistic methods in coloring and decomposition problems

    Noga Alon. Probabilistic methods in coloring and decomposition problems. Discrete Mathematics, 127(1-3):31–46, 1994

    work page 1994

  6. [3]

    Spencer.The Probabilistic Method

    Noga Alon and Joel H. Spencer.The Probabilistic Method. John Wiley & Sons, 2016

    work page 2016

  7. [4]

    On a hypergraph matching problem

    Noga Alon and Raphael Yuster. On a hypergraph matching problem. Graphs and Combinatorics, 21(4):377–384, 2005

    work page 2005

  8. [5]

    Fractional clique decompositions of dense graphs and hypergraphs.Journal of Combinatorial Theory, Series B, 127:148– 186, 2017

    Ben Barber, Daniela Kühn, Allan Lo, Richard Montgomery, and Deryk Osthus. Fractional clique decompositions of dense graphs and hypergraphs.Journal of Combinatorial Theory, Series B, 127:148– 186, 2017

    work page 2017

Show all 68 references
  1. [6]

    Edge-decompositions of graphs with high minimum degree.Advances in Mathematics, 288:337–385, 2016

    Ben Barber, Daniela Kühn, Allan Lo, and Deryk Osthus. Edge-decompositions of graphs with high minimum degree.Advances in Mathematics, 288:337–385, 2016

    2016

  2. [7]

    Large girth approximate Steiner triple systems.Journal of the London Mathematical Society, 100(3):895–913, 2019

    Tom Bohman and Lutz Warnke. Large girth approximate Steiner triple systems.Journal of the London Mathematical Society, 100(3):895–913, 2019

    2019

  3. [8]

    Steiner Triple Systems without forbidden subconfigurations.Mathematisch Centrum Amsterdam, ZW 104/77, 1977

    Andries Evert Brouwer. Steiner Triple Systems without forbidden subconfigurations.Mathematisch Centrum Amsterdam, ZW 104/77, 1977

    1977

  4. [9]

    Some extremal problems onr-graphs

    William Brown, Paul Erdős, and Vera Sós. Some extremal problems onr-graphs. New directions in the theory of graphs (Proceedings of the Third Ann Arbor Conference, Univ. Michigan, Ann Arbor, Mich., 1971), pages 53–63, 1973

    1971

  5. [10]

    On the maximal number of independent circuits in a graph

    Keresztély Corradi and András Hajnal. On the maximal number of independent circuits in a graph. Acta Mathematica Hungarica, 14(3-4):423–439, 1963. 31

    1963

  6. [11]

    Clique Decompositions in Random Graphs via Refined Absorption

    Michelle Delcourt, Tom Kelly, and Luke Postle. Clique Decompositions in Random Graphs via Refined Absorption. arXiv:2402.17857, 2024

    2024 arXiv

  7. [12]

    Thresholds for(n, q,2)-Steiner Systems via Refined Absorption

    Michelle Delcourt, Tom Kelly, and Luke Postle. Thresholds for(n, q,2)-Steiner Systems via Refined Absorption. arXiv:2402.17858, 2024

    2024 arXiv

  8. [13]

    Progress towards Nash-Williams’ Conjecture on triangle decom- positions

    Michelle Delcourt and Luke Postle. Progress towards Nash-Williams’ Conjecture on triangle decom- positions. Journal of Combinatorial Theory, Series B, 146:382–416, 2021

    2021

  9. [15]

    The limit in the(k + 2, k)-Problem of Brown, Erdős and Sós exists for all k ≥ 2

    Michelle Delcourt and Luke Postle. The limit in the(k + 2, k)-Problem of Brown, Erdős and Sós exists for all k ≥ 2. Proceedings of the American Mathematical Society, 152(05):1881–1891, 2024

    2024

  10. [18]

    József Dénes and A. D. Keedwell. Latin squares and their applications.Academic Press, New York- London, page 547, 1974

    1974

  11. [19]

    Some theorems on abstract graphs.Proceedings of the London Mathematical Society, 3(1):69–81, 1952

    Gabriel Andrew Dirac. Some theorems on abstract graphs.Proceedings of the London Mathematical Society, 3(1):69–81, 1952

    1952

  12. [20]

    Fractional triangle decompositions in graphs with large minimum degree

    François Dross. Fractional triangle decompositions in graphs with large minimum degree. SIAM Journal on Discrete Mathematics, 30(1):36–42, 2016

    2016

  13. [21]

    Dukes and Daniel Horsley

    Peter J. Dukes and Daniel Horsley. On the minimumm degree required for a triangle decomposition. SIAM Journal on Discrete Mathematics, 34(1):597–610, January 2020

    2020

  14. [22]

    A limit theorem in graph theory

    Paul Erdős and Miklós Simonovits. A limit theorem in graph theory. Studies Scientiarum Mat- tiematiearum Hungariea, 1(51-57):51, 1966

    1966

  15. [23]

    Paul Erdős and Arthur H. Stone. On the structure of linear graphs.Bulletin of the American Mathe- matical Society, 52(12):1087–1091, 1946

    1946

  16. [24]

    Problems and results in combinatorial analysis

    Paul Erdős. Problems and results in combinatorial analysis. InColloq. Internat. Theor. Combin. Rome, pages 3–17, 1973

    1973

  17. [25]

    On a limit theorem in combinatorial analysis.Publ

    Paul Erdős and Haim Hanani. On a limit theorem in combinatorial analysis.Publ. Math. Debrecen, 10:10–13, 1963

    1963

  18. [26]

    Dirac-type theorems in random hypergraphs.Journal of Combina- torial Theory, Series B, 155:318–357, 2022

    Asaf Ferber and Matthew Kwan. Dirac-type theorems in random hypergraphs.Journal of Combina- torial Theory, Series B, 155:318–357, 2022

    2022

  19. [27]

    Uniform hypergraphs containing no grids.Advances in Mathe- matics, 240:302–324, 2013

    Zoltán Füredi and Miklós Ruszinkó. Uniform hypergraphs containing no grids.Advances in Mathe- matics, 240:302–324, 2013

    2013

  20. [28]

    Linear methods for rational triangle decompositions

    Kseniya Garaschuk. Linear methods for rational triangle decompositions. PhD thesis, University of Victoria, 2014

    2014

  21. [29]

    Conflict-free hypergraph matchings

    Stefan Glock, Felix Joos, Jaehoon Kim, Marcus Kühn, and Lyuben Lichev. Conflict-free hypergraph matchings. Journal of the London Mathematical Society, 109(5):e12899, 2024. 32

    2024

  22. [30]

    On the decomposition threshold of a given graph.Journal of Combinatorial Theory, Series B, 139:47–127, 2019

    Stefan Glock, Daniela Kühn, Allan Lo, Richard Montgomery, and Deryk Osthus. On the decomposition threshold of a given graph.Journal of Combinatorial Theory, Series B, 139:47–127, 2019

    2019

  23. [31]

    On a conjecture of Erdős on locally sparse Steiner triple systems.Combinatorica, 40(3):363–403, 2020

    Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Osthus. On a conjecture of Erdős on locally sparse Steiner triple systems.Combinatorica, 40(3):363–403, 2020

    2020

  24. [32]

    The existence of designs via iterative absorption: Hypergraph F-designs for arbitrary F

    Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Osthus. The existence of designs via iterative absorption: Hypergraph F-designs for arbitrary F. Memoirs of the American Mathematical Society, 284(1406), 2023

    2023

  25. [33]

    London Mathematical Society Lecture Note Series

    Stefan Glock, Daniela Kühn, and Deryk Osthus.Extremal aspects of graph and hypergraph decomposi- tion problems, page 235–266. London Mathematical Society Lecture Note Series. Cambridge University Press, 2021

    2021

  26. [34]

    M. J. Grannell, T. S. Griggs, and C. A. Whitehead. The resolution of the anti-Pasch conjecture. Journal of Combinatorial Designs, 8(4):300–309, 2000

    2000

  27. [35]

    Proof of a conjecture of P

    András Hajnal and Endre Szemerédi. Proof of a conjecture of P. Erdős.Combinatorial Theory and its Applications, II:601–603, 1970

    1970

  28. [36]

    Penny E. Haxell. A condition for matchability in hypergraphs.Graphs and Combinatorics, 11(3):245– 248, 1995

    1995

  29. [37]

    Haxell and Vojtech Rödl

    Penny E. Haxell and Vojtech Rödl. Integer and fractional packings in dense graphs.Combinatorica, 21(1):13–38, 2001

    2001

  30. [38]

    Poissonapproximationforlargedeviations

    SvanteJanson. Poissonapproximationforlargedeviations. Random Structures & Algorithms, 1(2):221– 229, 1990

    1990

  31. [39]

    Conflict-free hypergraph matchings and coverings.arXiv preprint arXiv:2407.18144, 2024

    Felix Joos, Dhruv Mubayi, and Zak Smith. Conflict-free hypergraph matchings and coverings.arXiv preprint arXiv:2407.18144, 2024

    2024 arXiv

  32. [40]

    The existence of designs.arXiv preprint arXiv:1401.3665, 2014

    Peter Keevash. The existence of designs.arXiv preprint arXiv:1401.3665, 2014

    2014 arXiv

  33. [41]

    Hypergraph matchings and designs.Proc

    Peter Keevash. Hypergraph matchings and designs.Proc. Int. Cong. Math., 3:3099–3122, 2018

    2018

  34. [42]

    A short proof of the existence of designs.arXiv preprint arXiv:2411.18291, 2024

    Peter Keevash. A short proof of the existence of designs.arXiv preprint arXiv:2411.18291, 2024

    2024 arXiv

  35. [43]

    The Brown-Erdős-Sós conjecture for hypergraphs of large uniformity

    Peter Keevash and Jason Long. The Brown-Erdős-Sós conjecture for hypergraphs of large uniformity. arXiv:2007.14824, 2020

    2007 arXiv

  36. [44]

    Thomas P. Kirkman. On a problem in combinatorics.Cambridge Dublin Math. J, 2:191–204, 1847

  37. [45]

    PhD thesis, Heidelberg University, 2025

    Marcus Kühn.The Random Greedy Hypergraph Matching Process. PhD thesis, Heidelberg University, 2025

    2025

  38. [46]

    Substructures in Latin squares

    Matthew Kwan, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. Substructures in Latin squares. Israel Journal of Mathematics, 256(2):363–416, 2023

    2023

  39. [47]

    High-girthSteinertriplesystems

    MatthewKwan, AshwinSah, MehtaabSawhney, andMichaelSimkin. High-girthSteinertriplesystems. Annals of Mathematics, 200(3):1059–1156, 2024

    2024

  40. [48]

    Tiling dense hypergraphs.arXiv preprint arXiv:2308.12281, 2023

    Richard Lang. Tiling dense hypergraphs.arXiv preprint arXiv:2308.12281, 2023

    2023 arXiv

  41. [49]

    Phelps, and Vojtěch Rödl

    Hanno Lefmann, Kevin T. Phelps, and Vojtěch Rödl. Extremal problems for triple systems.Journal of Combinatorial Designs, 1(5):379–394, 1993. 33

    1993

  42. [50]

    A. C. H. Ling, C. J. Colbourn, M. J. Grannell, and T. S. Griggs. Construction techniques for anti-Pasch Steiner triple systems.Journal of the London Mathematical Society, 61(3):641–657, 2000

    2000

  43. [51]

    Challenges of high-dimensional combinatorics

    Nati Linial. Challenges of high-dimensional combinatorics. InLovász’s Seventieth Birthday Conference, volume 2, 2018

    2018

  44. [52]

    Problem 28 (solution by Gouwentak, Mantel, Teixeira de Mattes, Schuh and Wythoff)

    Willem Mantel. Problem 28 (solution by Gouwentak, Mantel, Teixeira de Mattes, Schuh and Wythoff). Wiskundige Opgaven, 10:60–61, 1907

    1907

  45. [53]

    Fractional clique decompositions of dense graphs.Random Structures & Algo- rithms, 54(4):779–796, 2019

    Richard Montgomery. Fractional clique decompositions of dense graphs.Random Structures & Algo- rithms, 54(4):779–796, 2019

    2019

  46. [54]

    Spanning trees in random graphs.Advances in Mathematics, 356:106793, 2019

    Richard Montgomery. Spanning trees in random graphs.Advances in Mathematics, 356:106793, 2019

    2019

  47. [55]

    Crispin St J. A. Nash-Williams. An unsolved problem concerning decomposition of graphs into trian- gles. Combinatorial Theory and its Applications, 3(1070):1179–1183, 1970

    1970

  48. [56]

    On a packing and covering problem.European Journal of Combinatorics, 6(1):69–78, 1985

    Vojtěch Rödl. On a packing and covering problem.European Journal of Combinatorics, 6(1):69–78, 1985

    1985

  49. [57]

    A Dirac-type theorem for 3-uniform hyper- graphs

    Vojtěch Rödl, Andrzej Ruciński, and Endre Szemerédi. A Dirac-type theorem for 3-uniform hyper- graphs. Combinatorics, Probability and Computing, 15(1-2):229–251, 2006

    2006

  50. [58]

    Integer and fractional packings of hypergraphs.Journal of Combinatorial Theory, Series B, 97(2):245–268, 2007

    Vojtech Rödl, Mathias Schacht, Mark H Siggers, and Norihide Tokushige. Integer and fractional packings of hypergraphs.Journal of Combinatorial Theory, Series B, 97(2):245–268, 2007

    2007

  51. [59]

    Eine Extremalaufgabe aus der Graphentheorie.Matematikai és

    Pál Turán. Eine Extremalaufgabe aus der Graphentheorie.Matematikai és. Fizikai Lapok, 48:436–452, 1941

    1941

  52. [60]

    Richard M. Wilson. An existence theory for pairwise balanced designs I. Composition theorems and morphisms. Journal of Combinatorial Theory, Series A, 13(2):220–245, 1972

    1972

  53. [61]

    Richard M. Wilson. An existence theory for pairwise balanced designs II. The structure of PBD-closed sets and the existence conjectures.Journal of Combinatorial Theory, Series A, 13(2):246–273, 1972

    1972

  54. [62]

    Richard M. Wilson. An existence theory for pairwise balanced designs, III: Proof of the existence conjecture. Journal of Combinatorial Theory, Series A, 18(1):71–79, 1975

    1975

  55. [63]

    Richard M. Wilson. Decomposition of complete graphs into subgraphs isomorphic to a given graph. Congressus Numerantium XV, pages 647–659, 1975

    1975

  56. [64]

    Models of random regular graphs.London mathematical society lecture note series, pages 239–298, 1999

    Nicholas C Wormald et al. Models of random regular graphs.London mathematical society lecture note series, pages 239–298, 1999

    1999

  57. [65]

    Asymptotically optimal Kk-packings of dense graphs via fractional Kk- decompositions

    Raphael Yuster. Asymptotically optimal Kk-packings of dense graphs via fractional Kk- decompositions. Journal of Combinatorial Theory, Series B, 95(1):1–11, 2005

    2005

  58. [66]

    Integer and fractional packing of families of graphs.Random Structures & Algorithms, 26(1-2):110–118, 2005

    Raphael Yuster. Integer and fractional packing of families of graphs.Random Structures & Algorithms, 26(1-2):110–118, 2005

    2005

  59. [67]

    on and off

    Raphael Yuster. H-packing ofk-chromatic graphs.Mosc. J. Comb. Number Theory, 2(1):73–88, 2012. 34 A Omni-Boosters To prove Theorem 5.1, we add a rootedK3-booster for each triangle in the decomposition family of a refined omni-absorber; we do this simultaneously and randomly su...

    2012

  60. [68]

    Hence T is a subtreasury ofProjg(B′, A0, K3, X)

    ∪ E(G′′ 2)] ⊆ H. Hence T is a subtreasury ofProjg(B′, A0, K3, X). We now show thatT is (n, 3αn, 1 4g , 2α)-regular. By Theorem A.7(3), we have thatProjg(B, A0, K3, X) is (n, 2αn, 1 4g , 2α)-regular. To conclude, it suffices to show thatdG1(v) − dG′′ 1 (v) ≤ αn for all v ∈ V (G...

Pith tools

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