Pith. sign in

REVIEW 2 major objections 3 minor 44 references

Perfect Matchings in Random Sparsifications of Dense Hypergraphs

T0 review · 2 major / 3 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 Perfect matchings in dense hypergraphs survive random sparsification

desk verdict The paper's central proof has a load-bearing gap: it applies an asymptotic structural theorem to constant-size clusters, and the main results rest on that step. read the letter →

arxiv 2507.11359 v4 pith:PGI5CY6Q submitted 2025-07-15 math.CO

Jie Han , Jingwen Zhao This is my paper
classification math.CO MSC 05C6505C7005D4068Q2505C85
keywords perfectmatchingshypergraphsrandomsparsificationspreaddistributionslattice-basedabsorptiondecisionproblemF-factorsprobabilisticmethod
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 claims that the polynomial-time tractable regime for perfect matchings in dense $k$-uniform hypergraphs is stable under random sparsification. For $k\ge 3$ and $\gamma>0$, if $H$ has minimum $(k-1)$-degree at least $n/k+\gamma n$ and every edge is kept independently with probability $p\ge C\log n/n^{k-1}$, the authors give a deterministic algorithm with running time $O(n^{2k^2-2k+1})$ that asymptotically almost surely decides whether the random subhypergraph $H_p$ contains a perfect matching. The same robustness is proved for $F$-factors in graphs meeting the critical-chromatic-number degree threshold, and a counting dichotomy follows: such hypergraphs have either no perfect matching or at least $(\varepsilon n)^{(k-1)n/k}$ perfect matchings. The significance is that the edge-keeping probability at which the decision problem remains tractable matches the natural threshold for the mere existence of perfect matchings in random subgraphs.

What carries the argument

The carrier of the argument is the spread method combined with lattice-based absorption. The paper builds a probability distribution over the perfect matchings (or $F$-factors) of $H$ whose $q$-spread is at most $C''/n^{1/m_1(F)}$, so that a spread-threshold theorem converts the distribution into an a.a.s. guarantee that the structure survives in $H_p$. To build the spread distribution, a random clustering lemma splits the vertex set into constantly many clusters that inherit the degree, reachability, robust-copy, and lattice properties of $H$; a lattice-preparation step then moves a few vertices (the sets $T_i$ and $L_i$) from neighbouring clusters so that each adjusted cluster satisfies the divisibility condition required by the structural theorem from [19], and finally the cluster-by-cluster packing results are glued into a full factor. A strengthened partition lemma (with the new property that every vertex lies in many $\mu$-robust copies) is what allows the partial-exposure algorithm to reveal only non-robust edges without destroying the conditions needed for the spread argument.

What would settle it

Find a $k$-graph $H$ with $\delta_{k-1}(H)\ge n/k+\gamma n$ and a probability $p\ge C\log n/n^{k-1}$ for which the algorithm in Theorem 1.2 accepts but $H_p$ has no perfect matching with non-vanishing probability; alternatively, exhibit a balanced bipartite graph on $2n$ vertices with minimum degree at least $3n/4$ whose perfect matchings admit no $(C/n)$-spread distribution, which would invalidate the redistribution step of Lemma 5.1.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the lattice-based absorption theory that makes perfect matching decidable in dense hypergraphs is robust: it survives random edge deletion. Theorem 1.2 states that any $n$-vertex $k$-graph $H$ with $\delta_{k-1}(H)\ge n/k+\gamma n$ admits a deterministic $O(n^{2k^2-2k+1})$-time algorithm such that, for $p\ge C\log n/n^{k-1}$, acceptance of the algorithm implies that $H_p$ contains a perfect matching with probability tending to one, while rejection implies $H_p$ has none. The algorithm works by exposing only non-robust edges, leaving the many $\mu$-robust edges untouched so that they can be used to complete a matching. The main technical engine, Theorem 1.10, constructs a $(C''/n^{1/m_1(F)})$-spread distribution on the family of $F$-factors of a host hypergraph satisfying mild degree, reachability, and robust-copy conditions; from it the authors derive the $F$-factor robustness theorem for graphs and the enumeration dichotomies. The paper thereby identifies the minimum codegree regime $>n/k$ as one where the decision problem is not only tractable but also resilient to random perturbation.

Load-bearing premise

The proof assumes that the structural theorem for perfect packings under minimum degree conditions remains valid after the vertex set is randomly partitioned into constant-sized clusters and a few vertices are relocated to correct divisibility; if the reachability, robustness, or lattice conditions are destroyed by these constant-size adjustments, the whole spread construction collapses.

Editorial extensions

If this is right

  • If Theorem 1.2 is correct, the perfect-matching decision problem for $k$-graphs with minimum codegree at least $n/k+\gamma n$ is solvable by a deterministic polynomial-time algorithm with high probability after sparsifying down to $p\approx \log n/n^{k-1}$.
  • The probability threshold is best possible up to a constant: when $p=o(\log n/n^{k-1})$, even the complete $k$-graph a.a.s. loses all perfect matchings.
  • Corollary 1.11 gives a sharp dichotomy: such a hypergraph either has no perfect matching or has at least $(\varepsilon n)^{(k-1)n/k}$ perfect matchings, for a constant $\varepsilon>0$ depending only on $k$ and $\gamma$.
  • For graphs, Theorem 1.8 yields the analogous random-sparsification robustness of $F$-factors under the critical chromatic number degree threshold, with an optimal threshold for strictly 1-balanced $F$.
  • Corollary 1.12 gives the $F$-factor counting dichotomy: either no $F$-factor or at least $(\varepsilon n)^{e_F n/(r m_1(F))}$ $F$-factors.

Reading between the lines

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

  • The acceptance probability of the algorithm is tied to whether a constant-sized matching of $\eta$-robust edges with the right index vector exists in $H$; one could test this numerically, giving an easily checkable heuristic certificate for acceptance or rejection before sampling $H_p$.
  • The lattice-preparation step that separates the two classes of robust index vectors is likely transferable to other contexts where divisibility barriers interact with random perturbation, such as Hamilton cycles in hypergraphs or existence of designs.
  • The authors note they cannot upgrade the $F$-factor result to a full decision algorithm because verifying divisibility may reveal too many non-robust copies; a route would be to find a way to check divisibility conditions obliviously to the random subgraph.
  • Since the proof constructs an explicit spread distribution, the counting dichotomy for $H$ plausibly extends to $H_p$ itself: the random sparsification should either have no perfect matching or have many, with the same exponential lower bound, though this is not stated.
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 / 3 minor

Summary. The paper studies random p-sparsification of dense hypergraphs in the polynomial-time tractable regime of the perfect matching decision problem. For k-uniform hypergraphs with minimum (k-1)-degree at least n/k + γn, Theorem 1.2 gives a deterministic algorithm that, for p ≥ C log n / n^{k-1}, a.a.s. decides whether H_p contains a perfect matching. Theorem 1.8 provides an analogous robustness result for F-factors in graphs with minimum degree above the critical chromatic threshold. The main technical result, Theorem 1.10, constructs a spread distribution on the family of F-factors under structural assumptions, using a new random clustering lemma (Lemma 5.1), the lattice-based absorption method, and the random redistribution framework of Kelly, Müyesser, and Pokrovskiy. Corollaries 1.11 and 1.12 give a dichotomy: either no perfect matching/F-factor exists, or there are exponentially many.

Significance. If the technical gap identified below is closed, these are significant results. They appear to be the first robust random-sparsification versions of polynomial-time tractable perfect matching decision results in hypergraphs, and the counting corollaries give optimal-order lower bounds on the number of perfect matchings under a much weaker degree condition than previous results. The paper is well structured, with full proofs and explicit algorithms, and the strengthened partition lemma (condition (F3)/(P3)) as well as the lattice-preparation step are genuine new ingredients. The proof strategy is coherent and builds on substantial published structural theorems, and the paper is honest about the limitations of the F-factor algorithmic result.

major comments (2)
  1. The clusters produced by Lemma 5.1 have constant size: by (R1), |U_i| = C for i ≥ 2 and |U_1| = O(C^2). In Step 3 the proof applies Theorem 6.1 to H_i = H[U'_i \ V(M_1)], which has |V(H_i)| ≤ C + O(r^2 q) vertices. Theorem 6.1 requires n ≥ n0, and the hierarchy fixed at the start of the proof of Theorem 1.10 (1/n0 ≪ ... ≪ 1/C) gives n0 ≫ C. Thus the hypotheses of Theorem 6.1 are not satisfied for these constant-size subgraphs. This is not a matter of degree or reachability; it is a size obstruction. Since the F-factors inside the clusters are exactly what defines the embedding ψ and yields the vertex-spread bound, the main construction of Theorem 1.10 is unsupported as written. The authors should either reorder the constants so that C is chosen larger than n0 (which appears compatible with Lemma 5.1) or replace this step with a proof that works at constant size.
  2. [§5, Lemma 5.1 proof, lower bound on d_{Gπ}(U'_i)] The displayed inequality d_{Gπ}(U'_i) ≥ m' - exp(γ^2 C/50)n is false as written: the exponent has the wrong sign and the wrong parameter. It should read m' - exp(-ε^2 C/50)n, as follows from the negation of (A3). This bound is used to show δ(Gπ) ≥ 3m'/4 and hence to apply Lemma 3.7, so the correction is needed for the proof of the spread distribution on the auxiliary bipartite graph.
minor comments (3)
  1. [§5, Lemma 5.1 proof, verification of (R1)] In the verification of (R1), the text says |U_i| = |U'_i| + 1 = C+1 for i ≥ 2, but |U'_i| = C-1 for i ≥ 2, so this should be C, matching the statement of (R1).
  2. [§5, Lemma 5.1 proof, probability estimate] In the probability estimate for the event E_6, the notation 'C2^{|S|}' is undefined; it presumably means C^{2|S|}. Please clarify.
  3. [Abstract and §1.1] The abstract uses the notation PM(k,ℓ,0) while the body mostly uses PM(k,δ); unify the notation for readability.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the central results are derived from published external structural theorems and in-paper lemmas; heavy reliance on the first author's prior work is load-bearing but independent, and no fitted parameter is renamed as a prediction.

full rationale

The derivation chain is: Lemma 5.1 (random clustering, proved in-paper from McDiarmid-type estimates and the external redistribution method of Kelly–Müyesser–Pokrovskiy [28]) supplies properties (R1)–(R5); Theorem 1.10 uses these to build a vertex-spread embedding, converts it via Proposition 2.5 [28] to a spread distribution on F-factors, and then invokes Theorem 2.3 [11] to pass to the random sparsification. The only load-bearing structural input from outside the paper is Theorem 6.1, quoted from Han–Treglown [19]. Although the present first author is also an author of [19], that theorem is published, peer-reviewed, parameter-free, and its assumptions (degree, reachability, lattice solubility) do not include the target robustness or spread conclusions. It is therefore independent evidence, not a self-referential premise. Lemma 3.7 [37] and Proposition 2.5 [28] are likewise external and do not assume the paper's results. No quantity in the paper is fitted to a subset of data and then reported as a prediction; the constants C, C', C'' are chosen generically from the hierarchy and do not encode the matching count or the decision. The enumeration corollaries (1.11, 1.12) follow from Fact 7.5, which is a direct measure argument: a (C/n^{1/m1(F)})-spread distribution forces many F-factors without any circular definition. The one genuinely concerning point in the proof is the application of Theorem 6.1 to clusters of constant size C when Theorem 6.1 requires n ≥ n0 with 1/n0 ≪ 1/C (so n0 ≫ C); that is a possible hypothesis-verification gap, not a circularity, because the cited theorem is not being used to define or assume the conclusion. Overall, no circular step was found.

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

No data or fitted constants appear. The hierarchy constants (α, β, γ, ε, η, C) are existential proof parameters, chosen by standard inequalities; they are not tuned to observations. No new physical or mathematical entities are postulated; sets T_i and robust-index notions are defined from existing theory.

assumptions (7)
  • domain assumption Theorem 6.1 of Han and Treglown [19]: under a minimum ℓ-degree condition and a good partition, an F-factor exists iff the lattice L is q-soluble.
    Main structural input; applied in Section 6 Step 3 to each adjusted cluster and in Theorem 1.8 to G'.
  • domain assumption Theorem 2.3 (Frankston, Kahn, Narayanan, Park [11]): if a hypergraph is q-spread, a random subset of size K q log ℓ a.a.s. contains an edge.
    Used in Theorem 1.10 (moreover part) and Theorem 1.8 to pass from a spread distribution to a.a.s. containment in a random sparsification.
  • domain assumption Lemma 3.7 from Pham, Sah, Sawhney, Simkin [37]: balanced bipartite graphs with minimum degree 3n/4 admit a (C/n)-spread distribution on perfect matchings.
    Used in Lemma 5.1 to distribute vertices of bad clusters; the 3/4 degree threshold is essential for the redistribution.
  • domain assumption Theorem 7.4 of Riordan [38]: for strictly 1-balanced F and p below log^2 n / n^{1/m1(F)}, the F-complex of G(n,p) can be coupled with a binomial random multi-hypergraph.
    Used in Theorem 1.8 to move from a spread distribution on the F-complex to a.a.s. containment at the JKV threshold.
  • domain assumption Theorem 1.13 from Shokoufandeh-Zhao [42] and Han [16]: δ(F,1,5v_F^2)=1-1/χ_cr(F) and δ(k,k-1,k)=1/k.
    Supplies the degree constants used in Theorems 1.2 and 1.8; the robustness inherits these thresholds.
  • standard math Lemma 3.5 from Ferber-Kwan [10]: a uniformly random induced subgraph inherits the approximate minimum ℓ-degree with high probability.
    Used in Lemma 5.5 to verify clusters retain the degree condition.
  • standard math Lemma 3.6 (McDiarmid's inequality for random permutations) from Molloy-Reed [36].
    Used in Lemmas 5.3 and 5.7 to bound deviations in the numbers of good clusters and in the auxiliary digraph degrees.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Perfect Matchings in Random Sparsifications of Dense Hypergraphs." pith.science (2026). https://pith.science/paper/PGI5CY6Q

@misc{pith2026250711359,
  author       = {Pith},
  title        = {Pith review of: Perfect Matchings in Random Sparsifications of Dense Hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PGI5CY6Q}},
  note         = {Machine review of arXiv:2507.11359}
}
abstract

Given \(1\le\ell <k \) and \(\delta\geq 0\), let \(\mathbf{PM}(k,\ell,\delta)\) be the decision problem for the existence of perfect matchings in \(n\)-vertex \(k\)-uniform hypergraphs with minimum \(\ell\)-degree at least \(\delta\binom{n-\ell}{k-\ell}\). For \(k\geq 3\), \(\mathbf{PM}(k,\ell,0)\) was one of the first NP-complete problems identified by Karp. Keevash, Knox and Mycroft conjectured that \(\mathbf{PM}(k,\ell,\delta)\) is in P for every \(\delta>1-(1-1/k)^{k-\ell}\) and this was recently verified by the work of Gan--Han, together with a very recent work of Fu et al. In this paper we study the existence of perfect matchings in the random $p$-sparsification of such $k$-uniform hypergraphs, that is, for $p=p(n)\in [0,1]$, each edge is selected independently with probability \(p\). Building on the structural theory of Gan and Han, we show that the corresponding dense perfect matching results are robust under random sparsification. As consequences, we obtain deterministic polynomial-time algorithms that asymptotically almost surely solve the associated decision problems, as well as lower bounds on the number of perfect matchings in such hypergraphs -- interestingly, such hypergraphs either have no perfect matching, or have $(\Omega(n))^{(1-1/k)n}$ perfect matchings. Moreover, we also establish analogous results for the \(F\)-factor problem in graphs. Our proofs combine a partial exposure algorithm, the lattice-based absorption method, and a random redistribution method of Kelly, M\"uyesser and Pokrovskiy, via the framework of spread distributions. A key new ingredient is a lattice-preparation step that separates the contributions of the two classes of robust index vectors arising in the Gan--Han structural theory. Together with the random redistribution method, this allows us to establish the desired spread property in the family of perfect matchings.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

44 extracted references · 40 canonical work pages

  1. [1]

    Allen, J

    P. Allen, J. Böttcher, J. Corsten, E. Davies, M. Jenssen, P. Morris, B. Roberts, and J. Skokan. A robust Corrádi–Hajnal theorem.Random Structures & Algorithms, 65(1):61–130, 2024

    work page 2024

  2. [2]

    Alman and V

    J. Alman and V. V. Williams. A refined laser method and faster matrix multiplication.TheoretiCS, 3, 2024

    work page 2024

  3. [3]

    Alon and R

    N. Alon and R. Yuster.H-factors in dense graphs.Journal of Combinatorial Theory, Series B, 66(2):269–282, 1996

    work page 1996

  4. [4]

    Asadpour, U

    A. Asadpour, U. Feige, and A. Saberi. Santa Claus meets hypergraph matchings. InApproximation, random- ization and combinatorial optimization, volume 5171 ofLecture Notes in Comput. Sci., pages 10–20. Springer, Berlin, 2008

    work page 2008

  5. [5]

    Cooley, D

    O. Cooley, D. Kühn, and D. Osthus. Perfect packings with complete graphs minus an edge.European Journal of Combinatorics, 28(8):2143–2155, 2007

    work page 2007

  6. [6]

    Cuckler and J

    B. Cuckler and J. Kahn. Hamiltonian cycles in Dirac graphs.Combinatorica, 29:299–326, 2009

    work page 2009

  7. [7]

    J. Edmonds. Paths, trees, and flowers.Canadian Journal of mathematics, 17:449–467, 1965

    work page 1965

  8. [8]

    P. Erdős. On extremal problems of graphs and generalized graphs.Israel Journal of Mathematics, 2(3):183–190, 1964

    work page 1964

Show all 44 references
  1. [9]

    Ferber, L

    A. Ferber, L. Hardiman, and A. Mond. Counting Hamilton cycles in Dirac hypergraphs.Combinatorica, 43(4):665–680, 2023

    2023

  2. [10]

    Ferber and M

    A. Ferber and M. Kwan. Dirac-type theorems in random hypergraphs.Journal of Combinatorial Theory, Series B, 155:318–357, 2022

    2022

  3. [11]

    Frankston, J

    K. Frankston, J. Kahn, B. Narayanan, and J. Park. Thresholds versus fractional expectation-thresholds.Annals of Mathematics, 194(2):475–495, 2021

    2021

  4. [12]

    Gan and J

    L. Gan and J. Han. On the Keevash-Knox-Mycroft conjecture.Journal of Combinatorial Theory, Series B, 174:214–242, 2025

    2025

  5. [13]

    Ghouila-Houri

    A. Ghouila-Houri. Une condition suffisante d’existence d’un circuit hamiltonien.Comptes Rendus de l’Académie des Sciences Paris, 251:495–497, 1960

    1960

  6. [14]

    Glock, S

    S. Glock, S. Gould, F. Joos, D. Kühn, and D. Osthus. Counting Hamilton cycles in Dirac hypergraphs.Combi- natorics, Probability and Computing, 30(4):631–653, 2021

    2021

  7. [15]

    Glock, D

    S. Glock, D. Kühn, A. Lo, and D. Osthus. The existence of designs via iterative absorption: hypergraphF-designs for arbitraryF.Mem. Amer. Math. Soc., to appear, 2022

    2022

  8. [16]

    J. Han. Near perfect matchings ink-uniform hypergraphs.Combinatorics, Probability and Computing, 24(5):723– 732, 2015

    2015

  9. [17]

    J. Han. Decision problem for perfect matchings in densek-uniform hypergraphs.Transactions of the American Mathematical Society, 369(7):5197–5218, 2017

    2017

  10. [18]

    Han and P

    J. Han and P. Keevash. Finding perfect matchings in dense hypergraphs. InProceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2366–2377, 2020

    2020

  11. [19]

    Han and A

    J. Han and A. Treglown. The complexity of perfect matchings and packings in dense hypergraphs.Journal of Combinatorial Theory, Series B, 141:72–104, 2020

    2020

  12. [20]

    Johansson, J

    A. Johansson, J. Kahn, and V. Vu. Factors in random graphs.Random Structures & Algorithms, 33(1):1–28, 2008

    2008

  13. [21]

    F. Joos, R. Lang, and N. Sanhueza-Matamala. Robust Hamiltonicity.arXiv preprint arXiv:2312.15262, 2023

    2023 arXiv

  14. [22]

    D. Y. Kang, T. Kelly, D. Kühn, D. Osthus, and V. Pfenninger. Perfect matchings in random sparsifications of Dirac hypergraphs.Combinatorica, pages 1–34, 2024. 26

    2024

  15. [23]

    R. M. Karp. Reducibility among combinatorial problems. In50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art, pages 219–241. Springer, 2009

    1958

  16. [24]

    Karpiński, A

    M. Karpiński, A. Ruciński, and E. Szymańska. Computational complexity of the perfect matching problem in hypergraphs with subcritical density.International Journal of Foundations of Computer Science, 21(06):905–924, 2010

    2010

  17. [25]

    P. Keevash. The existence of designs.arXiv e-prints, page arXiv:1401.3665, Jan. 2014

    2014 arXiv

  18. [26]

    Keevash, F

    P. Keevash, F. Knox, and R. Mycroft. Polynomial-time perfect matchings in dense hypergraphs. InProceedings of the forty-fifth annual ACM symposium on Theory of Computing, pages 311–320, 2013

    2013

  19. [27]

    P.KeevashandR.Mycroft.Ageometrictheoryforhypergraphmatching.Memoirs of the American Mathematical Society, 233(1098), 2015

    2015

  20. [28]

    Kelly, A

    T. Kelly, A. Müyesser, and A. Pokrovskiy. Optimal spread for spanning subgraphs of Dirac hypergraphs.Journal of Combinatorial Theory, Series B, 169:507–541, 2024

    2024

  21. [29]

    D. G. Kirkpatrick and P. Hell. On the complexity of general graph factor problems.SIAM Journal on Computing, 12(3):601–609, 1983

    1983

  22. [30]

    Komlós, G

    J. Komlós, G. Sárközy, and E. Szemerédi. Proof of the Alon–Yuster conjecture.Discrete Mathematics, 235(1- 3):255–269, 2001

    2001

  23. [31]

    Krivelevich, C

    M. Krivelevich, C. Lee, and B. Sudakov. Robust Hamiltonicity of Dirac graphs.Transactions of the American Mathematical Society, 366(6):3095–3130, 2014

    2014

  24. [32]

    Kühn and D

    D. Kühn and D. Osthus. Critical chromatic number and complexity of perfect packings in graphs. InProceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 851–859, 2006

    2006

  25. [33]

    Liebenau and N

    A. Liebenau and N. Wormald. Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph.Journal of the European Mathematical Society, 26(1):1–40, 2023

    2023

  26. [34]

    Lo and K

    A. Lo and K. Markström.F-factors in hypergraphs via absorption.Graphs and Combinatorics, 31:679–712, 2015

    2015

  27. [35]

    McDiarmid et al

    C. McDiarmid et al. On the method of bounded differences.Surveys in combinatorics, 141(1):148–188, 1989

    1989

  28. [36]

    Molloy and B

    M. Molloy and B. Reed.Graph colouring and the probabilistic method, volume 23. Springer Science & Business Media, 2002

    2002

  29. [37]

    H. T. Pham, A. Sah, M. Sawhney, and M. Simkin. A toolkit for robust thresholds.arXiv preprint arXiv:2210.03064, 2022

    2022 arXiv

  30. [38]

    O. Riordan. Random cliques in random graphs and sharp thresholds forF-factors.Random Structures & Algo- rithms, 61(4):619–637, 2022

    2022

  31. [39]

    V. Rödl, A. Ruciński, and E. Szemerédi. Perfect matchings in large uniform hypergraphs with large minimum collective degree.Journal of Combinatorial Theory, Series A, 116(3):613–636, 2009

    2009

  32. [40]

    H. Ryser. Neuere probleme in der kombinatorik.Vortrage über Kombinatorik, Oberwolfach, pages 69–91, 1967

    1967

  33. [41]

    G. N. Sárközy, S. M. Selkow, and E. Szemerédi. On the number of Hamiltonian cycles in Dirac graphs.Discrete Mathematics, 265(1-3):237–250, 2003

    2003

  34. [42]

    Shokoufandeh and Y

    A. Shokoufandeh and Y. Zhao. Proof of a tiling conjecture of Komlós.Random Structures & Algorithms, 23(2):180–205, 2003

    2003

  35. [43]

    Szymańska

    E. Szymańska. The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree.European Journal of Combinatorics, 34(3):632–646, 2013

    2013

  36. [44]

    W. T. Tutte. The factorization of linear graphs.Journal of the London Mathematical Society, 1(2):107–111, 1947. AppendixA.Proof of Lemma 7.1 Here we provide the full proof of Lemma 7.1. We first state a lemma analogous to Lemma 6.1 from [26]. For a vectorv, we writev(i)to deno...

    1947

Pith tools

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