Pith. sign in

REVIEW 2 major objections 4 minor 54 references

Ramsey--Dirac theory for bounded degree hypertrees

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read Every dense r-uniform hypergraph with no large r-partite hole contains every bounded-degree linear hypertree on n vertices.

desk verdict First Ramsey–Dirac theorem for connected hypergraphs, with a substantial main proof; the sketched secondary theorems and an imported lemma are the main gaps. read the letter →

arxiv 2411.17996 v1 pith:LAGSPSOD submitted 2024-11-27 math.CO

Jie Han , Seonghyuk Im , Jaehoon Kim , Donglei Yang This is my paper · ORCID
classification math.CO MSC 05C6505C3505C4505D40
keywords Ramsey–Diractheoryuniformhypergraphslinearhypertreesr-partiteholesminimumvertexdegreeabsorptionmethodlooseHamiltoncyclesrandomlyperturbed
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 a Ramsey–Dirac theorem for uniform hypergraphs. It proves that if an n-vertex r-uniform hypergraph G has minimum vertex degree δ1(G) ≥ ε $n^{{r−1}}$ and contains no r-partite hole of linear size—no r-tuple of vertex sets X1,...,Xr, each of size αn, with zero edges crossing the tuple—then G contains every n-vertex linear hypertree whose maximum degree is bounded by a constant. The same hypotheses also force loose Hamilton cycles and perfect matchings, and a rainbow version holds for systems of hypergraphs. The result matters because it transfers a graph-level phenomenon to hypergraphs: the condition "large bipartite hole is forbidden," already known to force spanning trees in graphs, is enough in r-uniform hypergraphs when paired only with a linear minimum degree bound.

What carries the argument

The central objects are the r-partite hole number α*(G), which measures the largest completely edge-free crossing tuple, and the decomposition of a bounded-degree hypertree into pendant stars or caterpillars. The proof's mechanism is a three-step reduction: (A1) Lemma 4.1 embeds an almost-spanning bounded-degree hyperforest, using Lemma 3.10 to decompose the forest into a small core, matchings, and length-three paths; (A2) Lemma 4.3 builds a spanning collection of pendant stars through an absorption argument based on the bipartite template lemma of [45]; (A3) Lemma 4.5 finds a transversal cycle factor for the caterpillar case, using weak hypergraph regularity to obtain an almost-spanning cycle collection and the lattice-based absorbing method to finish it. The matching lemma 3.1 is the recurring tool that turns the absence of r-partite holes into matchings that cover specified root sets, and the random partition lemma 3.6 supplies the degree concentration that lets each stage exploit the minimum degree condition.

What would settle it

Exhibit an r-uniform hypergraph G, say with r=3 and small ε, satisfying δ1(G) ≥ ε $n^{{2}}$ and α*(G) < α n that nevertheless omits some n-vertex bounded-degree linear hypertree, or omits a loose Hamilton cycle when (r−1)|n; such an example would disprove Theorems 1.1 and 1.2. A more surgical check is to test Lemma 3.24 in the precise setting of Claim 6.2: find a vertex class Vi and c+1 vertices in it with no pair that is (F, $ε^{4}$ n/(100r), 1)-reachable for F = $C^{{(r)}}$_t; then the closed-partition step cannot proceed and the proof of Lemma 4.5 has no justification.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.2: for every uniformity r, degree bound Δ, and ε > 0 there is α > 0 such that every n-vertex r-uniform hypergraph G with δ1(G) ≥ ε $n^{{r−1}}$ and α*(G) < α n contains every n-vertex linear hypertree T with Δ(T) ≤ Δ, whenever r−1 divides n−1. Here α*(G), the r-partite hole number, is the largest t for which one can find X1,...,Xr ⊆ V(G), |Xi| = t, with e_G(X1,...,Xr) = 0, so the hypothesis is exactly that no linearly large completely edge-free crossing tuple exists. The proof is an extension of the graph-case strategy: it decomposes any bounded-degree hypertree into either many disjoint pendant stars or many disjoint caterpillars of equal shape, embeds the remaining forest in a random third of the vertex set, then completes to a spanning copy using a matching lemma that converts hole-freeness into many disjoint edges, and finally uses absorption to make the star- or caterpillar-packing span all leftover vertices. Along the way the same machinery yields a spanning loose Hamilton cycle and a perfect matching under the same two hypotheses, plus a rainbow transversal version.

Load-bearing premise

The proof depends on an imported lemma, stated without proof as Lemma 3.24, which asserts that a part whose small subsets always contain two mutually reachable vertices can be partitioned into closed clusters; if that lemma fails for the partitions arising in the caterpillar step, the absorption argument for Lemma 4.5—and with it the embedding of caterpillars in Theorem 1.2—collapses.

Editorial extensions

If this is right

  • Every n-vertex r-graph satisfying δ1 ≥ ε n^{r−1} and α* < α n is universal for bounded-degree linear hypertrees: it contains all such trees on the same n vertices, not just one prescribed tree.
  • The same conditions force a loose Hamilton cycle when (r−1)|n (Theorem 1.1) and a perfect matching when r|n (Theorem 1.3), extending the graph-level Hamilton-cycle and matching results to hypergraphs.
  • Randomly perturbed hypergraphs inherit the universality: a dense r-graph with δ1 ≥ ε n^{r−1} becomes, after adding C/n^{r−1} random edges, one that contains every bounded-degree linear hypertree with high probability (Corollary 1.4).
  • The proof's bipartite formulation (Theorem 1.6) yields a rainbow version: a system of m r-graphs, each individually dense and hole-free, has every bounded-degree hypertree as a rainbow subgraph (Theorem 1.5).
  • Because the r-partite-hole condition is weaker than the usual (d,μ)-dense quasirandomness assumptions, the paper recovers and strengthens previous quasirandom-hypergraph results on matchings and loose Hamilton cycles.

Reading between the lines

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

  • The r-partite-hole condition is so much weaker than standard pseudorandomness that the paper's method suggests "minimum degree plus no linear empty crossing tuple" may be the natural general hypothesis for spanning bounded-degree structures in hypergraphs; bandwidth-type theorems for hypergraphs could be pursued under the same pair of assumptions.
  • The imported Lemma 3.24 is the place where the proof is most exposed; if its reachability hypothesis fails for the partitions constructed in Claim 6.2, one could likely replace it with a direct closure argument, but as written the caterpillar factor relies on it.
  • A testable extension is to replace linear hypertrees with bounded-degree hyperforests or powers of loose paths under the same degree and hole conditions, using the same decomposition into matchings and short paths.
  • For graphs the optimal hole parameter is known in the Hamilton-cycle case; the hypergraph analogue of determining the best possible α(ε) for loose Hamilton cycles or hypertrees is left open by this paper.
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

2 major / 4 minor

Summary. The paper develops a Ramsey–Dirac theory for r-uniform hypergraphs. The main theorem (Theorem 1.2) asserts that if G is an n-vertex r-graph with minimum vertex degree δ1(G) ≥ ε n^{r−1} and no r-partite hole of size αn (i.e., α*(G) < αn), then G contains every n-vertex linear hypertree T with maximum degree at most Δ. The proof proceeds by decomposing T into either pendant stars or caterpillars, embedding an almost-spanning forest, then completing the embedding via star-packing and a cycle-factor argument built on weak hypergraph regularity and absorption. The paper also states results for loose Hamilton cycles (Theorem 1.1), perfect matchings (Theorem 1.3), a bipartite version (Theorem 1.6), and a rainbow spanning tree theorem (Theorem 1.5). The proofs of Theorems 1.1 and 1.6 are only sketched, with the text saying their proofs are very similar to that of Theorem 1.2 and only differences are mentioned.

Significance. If the proofs are completed, this is a substantial advance: it extends the graph Ramsey–Dirac results of Han, Hu, Ping, Wang, Wang and Yang to bounded-degree hypertrees, generalizes universality results for randomly perturbed graphs to hypergraphs, and strengthens quasirandom hypergraph results of Lenz–Mubayi–Mycroft and Lenz–Mubayi under a much weaker pseudorandomness condition. The paper introduces a natural parameter α* for r-partite holes and gives a long, structured proof of the main hypertree theorem, with several reusable lemmas on hypertree decomposition, absorption, and cycle factors. However, the manuscript currently does not contain complete proofs of all stated theorems, and one imported lemma used in a load-bearing step is stated without proof and appears to have a constant mismatch with its application.

major comments (2)
  1. [§3.5 and §6, Lemma 3.24 and Claim 6.2] Lemma 3.24 is imported from [22] with the sentence "we omit the proof here", and its stated conclusion gives closed parts of size at least δn/(2c). Claim 6.2 in Section 6, however, asserts that each V_i can be partitioned into pairwise disjoint sets U_i^1,...,U_i^{k_i} of size at least δn each, with leftover at most δn. The proof of Claim 6.2 says only "By Lemma 3.24, it suffices to show..." and does not reconcile the size difference. The subsequent estimates in Claim 6.3 rely on sets of size at least δn, for example in the pigeonhole lower bound δ^{2r} n^{2r−2} for the auxiliary (2r−2)-graph. Because Claim 6.2 is the only mechanism that produces the closed vertex sets needed for the absorbing argument in Lemma 4.5, the caterpillar case of Theorem 1.2 is not fully supported as written. Please provide a proof of the stronger form of Lemma 3.24 (or of the version actually used), or adjust the constants and the estimates in Claims 6.2 and 6.3 accordingly.
  2. [§4, final paragraph before §5] The paper states: "The proofs of Theorem 1.1 and Theorem 1.6 are very similar to the proof of Theorem 1.2, so we just briefly mention differences without providing a formal proof." Theorem 1.1 is a headline result in the abstract, and Theorem 1.6 is the basis for the rainbow theorem (Theorem 1.5). As written, these theorems are not proven; the one-paragraph sketch does not constitute a proof. The authors should provide full proofs, or explicitly reformulate these as corollaries whose proofs are deferred to a companion paper, or remove them from the statements of results. This is load-bearing because the abstract and introduction advertise these results as contributions.
minor comments (4)
  1. [§3.5, Lemma 3.24] In the statement of Lemma 3.24, the phrase "for each j ∈ [r]" should read "for each j ∈ [ℓ]", since the sets V_i^1,...,V_i^ℓ are indexed by ℓ, not r.
  2. [§3.1, Lemma 3.1] The condition B3 is written as "d_G(v, U) ≥ (r−1)^2 m^{r−2} m*", which is ambiguous. It would be clearer as "d_G(v, U) ≥ (r−1)^2 m_* m^{r−2}".
  3. [Throughout] There are numerous typographical errors, including "Suppoes", "r-partitite r-garph", "vertext-disjoint", "caterplillars", "strightforward", "pupose", "prefect", and inconsistent spacing in names such as "M cdiarmid". A careful proofreading pass is needed.
  4. [§4.1, Case 2 reduction to Lemma 4.5] The construction of the modified vertex sets V'' and the graph G' by identifying x_i and y_i into z_i is only summarized. In particular, the assertion that the modified partition satisfies the α* condition required by Lemma 4.5 is not verified in detail; the text says only that "This degree condition together with the fact α*(G) < αn ≤ α^{1/2}m implies that we can apply Lemma 4.5." Please expand this verification, since the application of Lemma 4.5 is essential in this case.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the main theorem is proved from the stated minimum-degree and hole conditions using independent imported lemmas; the only flagged item is an omitted proof of a load-bearing self-cited lemma, which is a completeness risk, not circularity.

full rationale

The derivation chain of Theorem 1.2 does not reduce its conclusion to its own hypotheses. The proof uses two imported results with overlapping authorship: Lemma 3.10 from [26] (Im, Kim, Lee, Methuku; current authors Im and Kim) for decomposing hypertrees into matchings and paths, and Lemma 3.24 from [22] (Han, Shu, Wang; current author Han) for partitioning vertex classes into closed sets. Neither lemma states or assumes the target theorem; each is a moderately technical tool whose statement is independent of Theorem 1.2. In particular, Lemma 3.24 is quoted verbatim as 'a slight variation of Lemma 5.4 in [22]' and the paper says 'we omit the proof here'. This is an explicit omitted proof and a genuine verification gap, since Claim 6.2 relies on Lemma 3.24 to obtain the (F, βn, 2^10 ε^-4)-closed sets used in Claim 6.3 and hence in the absorption argument for Lemma 4.5. However, an omitted or compressed proof of an imported lemma is not a circular step: the lemma is not derived from the main result, and the surrounding proof independently verifies the hypotheses needed to apply it. There is no fitted input relabeled as a prediction, no self-definitional identification of the target with an assumption, and no uniqueness claim imported solely from the authors. The proof also explicitly flags other omitted proofs ('The proofs of Theorem 1.1 and Theorem 1.6 are very similar ... we just briefly mention differences'), which again affects self-containedness rather than circularity. Accordingly, the central claim has independent content and the appropriate circularity score is low.

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

The central claim rests on standard probabilistic and regularity tools, plus several imported lemmas from prior papers, some by the same authors. No new entities or free parameters are introduced; the hierarchy constants (α, β, γ, etc.) are chosen to satisfy clean inequalities and are not fitted to data.

assumptions (5)
  • domain assumption Lemma 3.10 (hypertree decomposition into matchings and short paths, from [26])
    Imported from Im, Kim, Lee and Methuku; used to decompose the target hypertree T into a bounded sequence of subforests. Not proved in this paper.
  • domain assumption Lemma 3.16 (bipartite template lemma, from Montgomery [45])
    Used in the absorption setup to build absorbing sets. Cited but not proved here.
  • domain assumption Lemma 3.24 (closedness/reachability of vertex classes, from Han, Shu and Wang [22])
    Stated without proof and used in Claim 6.2 to partition each vertex class into closed sets, essential for the cycle factor proof.
  • standard math Weak hypergraph regularity lemma (Lemma 3.12)
    Standard regularity lemma; stated and used without proof.
  • standard math Kim-Vu polynomial concentration (Lemma A.2)
    Used in the appendix to prove concentration of random partitions; standard tool.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Ramsey--Dirac theory for bounded degree hypertrees." pith.science (2026). https://pith.science/paper/LAGSPSOD

@misc{pith2026241117996,
  author       = {Pith},
  title        = {Pith review of: Ramsey--Dirac theory for bounded degree hypertrees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LAGSPSOD}},
  note         = {Machine review of arXiv:2411.17996}
}
abstract

Ramsey--Tur\'an theory considers Tur\'an type questions in Ramsey-context, asking for the existence of a small subgraph in a graph $G$ where the complement $\overline{G}$ lacks an appropriate subgraph $F$, such as a clique of linear size. Similarly, one can consider Dirac-type questions in Ramsey context, asking for the existence of a spanning subgraph $H$ in a graph $G$ where the complement $\overline{G}$ lacks an appropriate subgraph $F$, which we call a Ramsey--Dirac theory question. When $H$ is a connected spanning subgraph, the disjoint union $K_{n/2}\cup K_{n/2}$ of two large cliques shows that it is natural to consider complete bipartite graphs $F$. Indeed, Han, Hu, Ping, Wang, Wang and Yang in 2024 proved that if $G$ is an $n$-vertex graph with $\delta(G)=\Omega(n)$ where the complement $\overline{G}$ does not contain any complete bipartite graph $K_{m,m}$ with $m=\Omega(n)$, then $G$ contains every $n$-vertex bounded degree tree $T$ as a subgraph. Extending this result to the Ramsey--Dirac theory for hypertrees, we prove that if $G$ is an $n$-vertex $r$-uniform hypergraph with $\delta(G)=\Omega(n^{r-1})$ where the complement $\overline{G}$ does not contain any complete $r$-partite hypergraph $K_{m,m,\dots, m}$ with $m=\Omega(n)$, then $G$ contains every $n$-vertex bounded degree hypertree $T$ as a subgraph. We also prove the existence of matchings and loose Hamilton cycles in the same setting, which extends the result of Mcdiarmid and Yolov into hypergraphs. This result generalizes the universality result on randomly perturbed graphs by B\"ottcher, Han, Kohayakawa, Montgomery, Parczyk and Person in 2019 into hypergraphs and also strengthen the results on quasirandom hypergraphs by Lenz, Mubayi and Mycroft in 2016 and Lenz and Mubayi in 2016 into hypergraphs satisfying a much weaker pseudorandomness condition.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 50 canonical work pages

  1. [22]

    Non-linear Hamilton cyc les in linear quasi-random hy- pergraphs

    Jie Han, Xichao Shu, and Guanghui Wang. Non-linear Hamilton cyc les in linear quasi-random hy- pergraphs. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algo rithms (SODA) , pages 74–88. [Society for Industrial and Applied Mathematics (SIAM)], Ph iladelphia, PA, 2021

    work page 2021

  2. [1]

    Noga Alon and Joel H. Spencer. The probabilistic method . Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, fourth edition, 2 016

    work page

  3. [2]

    Trian gle factors of graphs without large independent sets and of weighted graphs

    J´ ozsef Balogh, Theodore Molla, and Maryam Sharifzadeh. Trian gle factors of graphs without large independent sets and of weighted graphs. Random Structures Algorithms , 49(4):669–693, 2016

    work page 2016

  4. [3]

    A generalization of Carath´ eodory’s theorem.Discrete Math., 40(2-3):141–152, 1982

    Imre B´ ar´ any. A generalization of Carath´ eodory’s theorem.Discrete Math., 40(2-3):141–152, 1982

    work page 1982

  5. [4]

    Wiebke Bedenknecht, Jie Han, Yoshiharu Kohayakawa, and Guilhe rme O. Mota. Powers of tight Hamilton cycles in randomly perturbed hypergraphs. Random Structures Algorithms , 55(4):795–807, 2019

    work page 2019

  6. [5]

    Ad ding random edges to dense graphs

    Tom Bohman, Alan Frieze, Michael Krivelevich, and Ryan Martin. Ad ding random edges to dense graphs. Random Structures Algorithms , 24(2):105–117, 2004

    work page 2004

  7. [6]

    How many random edge s make a dense graph Hamiltonian? Random Structures Algorithms , 22(1):33–42, 2003

    Tom Bohman, Alan Frieze, and Ryan Martin. How many random edge s make a dense graph Hamiltonian? Random Structures Algorithms , 22(1):33–42, 2003

    work page 2003

  8. [7]

    Universality for bounded degree spanning trees in randomly pertur bed graphs

    Julia B¨ ottcher, Jie Han, Yoshiharu Kohayakawa, Richard Montgomery, Olaf Parczyk, and Yury Person. Universality for bounded degree spanning trees in randomly pertur bed graphs. Random Structures Algorithms, 55:854–864, 2019

    work page 2019

Show all 54 references
  1. [8]

    Proof of the bandwidth conjecture of Bollob´ as and Koml´ os.Math

    Julia B¨ ottcher, Mathias Schacht, and Anusch Taraz. Proof of the bandwidth conjecture of Bollob´ as and Koml´ os.Math. Ann. , 343(1):175–205, 2009

    2009

  2. [9]

    A bandwidth theorem for graph transversals

    Debsoumya Chakraborti, Seonghyuk Im, Jaehoon Kim, and Hong Liu. A bandwidth theorem for graph transversals. arXiv:2302.09637, 2023

    2023 arXiv

  3. [10]

    On powers of tight Hamilto n cycles in randomly perturbed hypergraphs

    Yulin Chang, Jie Han, and Lubos Thoma. On powers of tight Hamilto n cycles in randomly perturbed hypergraphs. Random Structures Algorithms , 63(3):591–609, 2023

    2023

  4. [11]

    On powers o f Hamilton cycles in Ramsey-Tur´ an Theory

    Ming Chen, Jie Han, Yantao Tang, and Donglei Yang. On powers o f Hamilton cycles in Ramsey-Tur´ an Theory. arXiv:2305.17360, 2023

    2023 arXiv

  5. [12]

    Transversal Hamilton cycle in hypergraph systems

    Yangyang Cheng, Jie Han, Bin Wang, Guanghui Wang, and Dongle i Yang. Transversal Hamilton cycle in hypergraph systems. arXiv:2111.07079, 2023

    2023 arXiv

  6. [13]

    Fan R. K. Chung. Regularity lemmas for hypergraphs and quasi- randomness. Random Structures Algorithms, 2(2):241–252, 1991

    1991

  7. [14]

    Some theorems on abstract graphs

    Gabriel Andrew Dirac. Some theorems on abstract graphs. Proc. London Math. Soc. (3) , 2:69–81, 1952

    1952

  8. [15]

    A generalization of Bondy’s pancyclicity theorem

    Nemanja Dragani´ c, David Munh´ a Correia, and Benny Sudakov. A generalization of Bondy’s pancyclicity theorem. Combin. Probab. Comput. , 33(5):554–563, 2024

    2024

  9. [16]

    The uniformity lemma for hype rgraphs

    Peter Frankl and Vojtech R¨ odl. The uniformity lemma for hype rgraphs. Graphs Combin., 8(4):309–312, 1992

    1992

  10. [17]

    A general approach to transversal versions of Dirac-type theorems

    Pranshu Gupta, Fabian Hamann, Alp M¨ uyesser, Olaf Parczyk,and Amedeo Sgueglia. A general approach to transversal versions of Dirac-type theorems. Bull. Lond. Math. Soc. , 55(6):2817–2839, 2023

    2023

  11. [18]

    Proof of a conjectur e of P

    Andr´ as Hajnal and Endre Szemer´ edi. Proof of a conjectur e of P. Erd˝ os. In Combinatorial theory and its applications, I-III (Proc. Colloq., Balatonf¨ ured, 1969), volume 4 of Colloq. Math. Soc. J´ anos Bolyai, pages 601–623. North-Holland, Amsterdam-London, 1970

    1969

  12. [19]

    Decision problem for perfect matchings in dense k-uniform hypergraphs

    Jie Han. Decision problem for perfect matchings in dense k-uniform hypergraphs. Trans. Amer. Math. Soc., 369(7):5197–5218, 2017. 23

    2017

  13. [20]

    On perfect matchings and tilings in uniform hypergraphs

    Jie Han. On perfect matchings and tilings in uniform hypergraphs . SIAM J. Discrete Math. , 32(2):919– 932, 2018

    2018

  14. [21]

    Spanning trees in graphs without large bipartite holes

    Jie Han, Jie Hu, Lidan Ping, Guanghui Wang, Yi Wang, and Donglei Yang. Spanning trees in graphs without large bipartite holes. Combinatorics, Probability and Computing , 33(3):270–285, 2024

    2024

  15. [23]

    The complexity of perfect matchin gs and packings in dense hypergraphs

    Jie Han and Andrew Treglown. The complexity of perfect matchin gs and packings in dense hypergraphs. J. Combin. Theory Ser. B , 141:72–104, 2020

    2020

  16. [24]

    Hamiltonicity in randomly perturbed hypergr aphs

    Jie Han and Yi Zhao. Hamiltonicity in randomly perturbed hypergr aphs. J. Combin. Theory Ser. B , 144:14–31, 2020

    2020

  17. [25]

    Holmsen, J´ anos Pach, and Helge Tverberg

    Andreas F. Holmsen, J´ anos Pach, and Helge Tverberg. Points surrounding the origin. Combinatorica, 28(6):633–644, 2008

    2008

  18. [26]

    A proof of the Elliott-R¨ odl conjecture on hypertrees in Steiner triple systems

    Seonghyuk Im, Jaehoon Kim, Joonkyung Lee, and Abhishek Met huku. A proof of the Elliott-R¨ odl conjecture on hypertrees in Steiner triple systems. arXiv:2208.10 370, 2022

    2022

  19. [27]

    On a rainbow version of Dirac’s theore m

    Felix Joos and Jaehoon Kim. On a rainbow version of Dirac’s theore m. Bull. Lond. Math. Soc. , 52(3):498– 504, 2020

    2020

  20. [28]

    Spanning trees in randomly perturbe d graphs

    Felix Joos and Jaehoon Kim. Spanning trees in randomly perturbe d graphs. Random Structures Al- gorithms, 56(1):169–219, 2020

    2020

  21. [29]

    A topological colorful Helly theorem

    Gil Kalai and Roy Meshulam. A topological colorful Helly theorem. Adv. Math., 191(2):305–311, 2005

    2005

  22. [30]

    Perfect matchings in random sparsifications of Dirac hypergraphs

    Dong Yeap Kang, Tom Kelly, Daniela K¨ uhn, Deryk Osthus, and Vin cent Pfenninger. Perfect matchings in random sparsifications of Dirac hypergraphs. arXiv:2211.01325, 2024

    2024 arXiv

  23. [31]

    Jeong Han Kim and Van H. Vu. Concentration of multivariate polyn omials and its applications. Com- binatorica, 20(3):417–434, 2000

    2000

  24. [32]

    Kr-factors in graphs with low independence number

    Charlotte Knierim and Pascal Su. Kr-factors in graphs with low independence number. J. Combin. Theory Ser. B , 148:60–83, 2021

    2021

  25. [33]

    S´ ark¨ ozy, and Endre Szemer´ edi

    J´ anos Koml´ os, G´ abor N. S´ ark¨ ozy, and Endre Szemer´ edi. Proof of a packing conjecture of Bollob´ as. Combin. Probab. Comput. , 4(3):241–255, 1995

    1995

  26. [34]

    S´ ark¨ ozy, and Endre Szemer´ edi

    J´ anos Koml´ os, G´ abor N. S´ ark¨ ozy, and Endre Szemer´ edi. Spanning trees in dense graphs. Combin. Probab. Comput., 10(5):397–416, 2001

    2001

  27. [35]

    Embedding spanning trees in random graphs

    Michael Krivelevich. Embedding spanning trees in random graphs . SIAM J. Discrete Math. , 24(4):1495– 1500, 2010

    2010

  28. [36]

    Bound ed-degree spanning trees in randomly perturbed graphs

    Michael Krivelevich, Matthew Kwan, and Benny Sudakov. Bound ed-degree spanning trees in randomly perturbed graphs. SIAM J. Discrete Math. , 31(1):155–171, 2017

    2017

  29. [37]

    Pseudo-random graph s

    Michael Krivelevich and Benny Sudakov. Pseudo-random graph s. In More Sets, Graphs and Numbers, Bolyai Society Mathematical Studies , volume 15, pages 199–262. Springer, 2006

    2006

  30. [38]

    Embedding large subgraphs int o dense graphs

    Daniela K¨ uhn and Deryk Osthus. Embedding large subgraphs int o dense graphs. In Surveys in com- binatorics 2009 , volume 365 of London Math. Soc. Lecture Note Ser. , pages 137–167. Cambridge Univ. Press, Cambridge, 2009

    2009

  31. [39]

    Hamilton cycles in graphs and hy pergraphs: an extremal perspective

    Daniela K¨ uhn and Deryk Osthus. Hamilton cycles in graphs and hy pergraphs: an extremal perspective. In Proceedings of the International Congress of Mathematicia ns—Seoul 2014. Vol. IV , pages 381–406. Kyung Moon Sa, Seoul, 2014. 24

    2014

  32. [40]

    Towards a high-dimensional Dirac’s theorem

    Hyunwoo Lee. Towards a high-dimensional Dirac’s theorem. arX iv:2310.15909, 2023

    2023 arXiv

  33. [41]

    Perfect packings in quasirandom h ypergraphs I

    John Lenz and Dhruv Mubayi. Perfect packings in quasirandom h ypergraphs I. J. Combin. Theory Ser. B, 119:155–177, 2016

    2016

  34. [42]

    Hamilton cycles in quasirandom hypergraphs

    John Lenz, Dhruv Mubayi, and Richard Mycroft. Hamilton cycles in quasirandom hypergraphs. Random Structures Algorithms, 49(2):363–378, 2016

    2016

  35. [43]

    Hamilton cycles, minimum degree, an d bipartite holes

    Colin McDiarmid and Nikola Yolov. Hamilton cycles, minimum degree, an d bipartite holes. J. Graph Theory, 86(3):277–285, 2017

    2017

  36. [44]

    Hamilton ℓ-cycles in randomly perturbed hypergraphs

    Andrew McDowell and Richard Mycroft. Hamilton ℓ-cycles in randomly perturbed hypergraphs. Elec- tron. J. Combin. , 25(4):Paper No. 4.36, 30, 2018

    2018

  37. [45]

    Spanning trees in random graphs

    Richard Montgomery. Spanning trees in random graphs. Adv. Math. , 356:106793, 92, 2019

    2019

  38. [46]

    Trans versal factors and spanning trees

    Richard Montgomery, Alp M¨ uyesser, and Yani Pehova. Trans versal factors and spanning trees. Adv. Comb., pages Paper No. 3, 25, 2022

    2022

  39. [47]

    Embedding rainbow trees with applica- tions to graph labelling and decomposition

    Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov. Embedding rainbow trees with applica- tions to graph labelling and decomposition. J. Eur. Math. Soc. (JEMS) , 22(10):3101–3132, 2020

    2020

  40. [48]

    Perfect matchings in large uniform hypergraphs with large minimum collective degree

    Vojtech R¨ odl, Andrzej Ruci´ nski, and Endre Szemer´ edi. Perfect matchings in large uniform hypergraphs with large minimum collective degree. J. Combin. Theory Ser. A , 116(3):613–636, 2009

    2009

  41. [49]

    Spielman and Shang-Hua Teng

    Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of alg orithms: why the simplex algorithm usually takes polynomial time. J. ACM , 51(3):385–463, 2004

    2004

  42. [50]

    Die Kleitman-Rothschild Methode

    Angelika Steger. Die Kleitman-Rothschild Methode . PhD thesis, Rheinische Friedrich-Wilhelms- Universit¨ at Bonn. Forschungsinstitut f¨ ur Diskrete Mathematik, 1990

    1990

  43. [51]

    Regular partitions of graphs

    Endre Szemer´ edi. Regular partitions of graphs. In Probl` emes combinatoires et th´ eorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) , volume 260 of Colloq. Internat. CNRS , pages 399–401. CNRS, Paris, 1978

    1976

  44. [52]

    Rainbo w Hamilton cycle in hypergraph system

    Yucong Tang, Bin Wang, Guanghui Wang, and Guiying Yan. Rainbo w Hamilton cycle in hypergraph system. arXiv:2302.00080, 2023

    2023 arXiv

  45. [53]

    σ-algebras for quasirandom hypergraphs

    Henry Towsner. σ-algebras for quasirandom hypergraphs. Random Structures Algorithms , 50:114–139, 2017

    2017

  46. [54]

    Recent advances on Dirac-type problems for hyperg raphs

    Yi Zhao. Recent advances on Dirac-type problems for hyperg raphs. In Recent trends in combinatorics , volume 159 of IMA Vol. Math. Appl. , pages 145–165. Springer, [Cham], 2016. A Proof of Lemma 3.6 In this section, we consider weighted graphs. A weighted r-graph G is an r-uni...

    2016

Pith tools

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