On the number of factorable induced subgraphs

Bin Wang; Jie Han; Jingwen Zhao

The paper proves that, for any r-vertex graph F and any host graph H above the critical chromatic degree threshold, a random induced subgraph H[p] contains an F-factor with asymptotic probability at least 1/(rq), where q is the order of the

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-07-31 23:57 UTC pith:V3VUK5IU

load-bearing objection Generalizes recent random-induced-subgraph factor results from Hamilton cycles and cliques to all F-factors, with a genuinely new lattice-coset mechanism; the proof holds up, though one exponent is garbled.

arxiv 2607.27870 v1 pith:V3VUK5IU submitted 2026-07-30 math.CO

On the number of factorable induced subgraphs

Jie Han , Bin Wang , Jingwen Zhao This is my paper

classification math.CO MSC 05C7005C8005C6505C35

keywords F-factorrandom induced subgraphcritical chromatic numberlattice methodcoset groupdense hypergraphsperfect matchingindex vector

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper asks a simple question: if you randomly delete vertices of a dense graph H, how likely is the remaining induced subgraph to contain a perfect F-factor? It answers that the probability is controlled not only by the sampled vertex count being divisible by r, but by a finer divisibility parameter q built from the host graph. Specifically, for any r-vertex graph F and any host H with minimum degree slightly above the critical chromatic threshold, H[p] contains an F-factor with probability at least 1/(rq) - o(1), where q is the order of a certain coset group defined from the lattice of 'index vectors' of copies of F in H. The same mechanism gives analogous probability bounds for perfect matchings in dense hypergraphs. A striking corollary is that a 1/(rq)-proportion of all subsets of H induce F-factors, even when H itself admits no F-factor. The proof combines concentration inequalities, lattice-point counting, and a deterministic lattice-based criterion for factors.

Core claim

The central assertion is Theorem 1.5: for every r-vertex k-chromatic graph F and every gamma > 0, if H is an n-vertex graph with minimum degree at least (1 - 1/chi_cr(F) + gamma)n, then for each fixed p in (0,1), the random induced subgraph H[p] contains an F-factor with probability at least 1/(rq) - o_n(1). Here q is the order of the coset group Q(P, L^mu_{P,F}(H)) for a suitable partition P, and q is bounded by (2r-1)^r. The factor 1/r reflects the necessary divisibility of the sampled vertex count; the new factor 1/q reflects deeper divisibility constraints of the lattice generated by the index vectors of robustly many copies of F in H. The probability is asymptotically best possible for

What carries the argument

The central object is the robust index-vector lattice. Given a partition P = {V0, V1, ..., Vd} of the host graph H, the index vector of a copy of F records how many of its vertices lie in each non-exceptional part. The lattice L^mu_{P,F}(H) is the additive subgroup of Z^d generated by all r-vectors that occur as index vectors of at least mu n^r copies of F. Its coset group Q(P, L) = L^d_max / L has order q and encodes the divisibility obstructions to packing F. The proof shows that this lattice is inherited by the random induced subgraph at a rescaled threshold (Lemma 4.1), and that the sampled index vector lands in the correct coset with probability asymptotically 1/(rq) via a lattice-point

Load-bearing premise

The proof relies on the assumption that the collection of copy index vectors of F that occur with more than a fixed density in H is essentially unchanged after random vertex deletion, once the density threshold is rescaled; if random sampling deletes too many copies of a borderline index-vector type, the lattice and the 1/(rq) probability can fail.

What would settle it

Take F = K_{2,4} and H = K_{n/2 - t, n/2 + t} with the natural bipartition; the paper's Example 2.2 gives q = 2, so the theorem predicts that a p-random induced subgraph is factorable with probability tending to 1/12 for every fixed p. A direct count of subsets inducing a K_{2,4}-factor for large n, or a simulation for moderately large n, should produce a limit of 1/12. Finding any host H satisfying the degree condition for which this fraction does not approach the predicted 1/(rq), or for which the robust index-vector set changes after sampling, would falsify the central claim.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

At least a 1/(rq) - o(1) fraction of all vertex subsets of H induce F-factors, regardless of whether H itself has an F-factor.
For fixed p, the probability 1/(rq) is asymptotically best possible for infinitely many host graphs, so no universal improvement beyond this value is possible without extra assumptions.
In hypergraphs, the same lattice mechanism gives asymptotic probabilities 1/(kq) for perfect matchings under minimum degree conditions, improving to 1/(k(s-1)) under minimum codegree conditions; these are again asymptotically tight.
When every possible copy index vector of F in H is mu0-robust, the probability is exactly 1/(rq) ± epsilon, not merely a lower bound.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Because the authors note their bound on p is likely not optimal, one natural extension is to find the true threshold on p below which the robust index-vector lattice is not faithfully inherited; if such a threshold exists, the 1/(rq) probability would hold for much sparser induced subgraphs.
The coset-membership view suggests a randomized algorithmic corollary: sample a vertex subset, test whether its index vector lies in the correct coset, and only then run the deterministic factor algorithm; the success probability would be exactly the stated 1/(rq).
The authors conjecture that q decreases to 1 when the minimum degree is raised to the ordinary chromatic threshold; a concrete test would be to compute q for balanced blow-ups of F and check monotonicity as the host graph becomes denser.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

Generalizes recent random-induced-subgraph factor results from Hamilton cycles and cliques to all F-factors, with a genuinely new lattice-coset mechanism; the proof holds up, though one exponent is garbled.

read the letter

This is a strong paper. The main result — that for any r-vertex F, if H has minimum degree at least (1−1/χ_cr(F)+γ)n, then H[p] contains an F-factor with probability at least 1/(rq)−o(1), where q is the order of a coset group defined from H — is a real step beyond the previous Hamiltonian-cycle result of Draganić–Keevash–Müyesser and the K_r-factor result of Sun–Wei–Yang. The 1/(rq) probability is not just a bound; the paper gives examples showing it is asymptotically tight for infinitely many H, and the hypergraph perfect-matching analogues are natural extensions. This is genuinely new and worth knowing.

The proof is honest and mostly careful. The key structural theorem, Theorem 3.2, combines the Han–Treglown lattice criterion with two ingredients: Lemma 4.1 (inheritance under random vertex sampling) and Lemma 4.2 (Gauss lattice-point counting for the index-vector distribution). The stress-test note is right: Lemma 4.1(V4) is not an unproven assumption. Claim 4.4 provides a plateau μ* with I^{μ*}=I^{μ*/4}, and then Lemma 4.3 supplies the concentration needed to transfer the identity to H′ at threshold μ*/2. The margins are strict: 3/4μ*m^r vs 1/2μ*m^r, so the equality holds. I checked the step in Theorem 3.2 where the coset event B is conditioned on V_p∩V_0; the independence of i_P(V_p) from that event is legitimate, and the law of total probability is applied correctly. The lattice-counting lemma is also sound: full rank follows from Proposition 2.7, covol(L)=rq, and the box partition into m^d small boxes works.

The soft spots are real but not load-bearing. First, the exponent h in the printed Theorem 1.5 is garbled — it should be something like 2(2r^{k−1}−2) or max{2(tr−1),2r} with t=2r^{k−1}−1; the displayed formula is not even syntactically clear. Same for the h in Theorem 1.6. This is typographical, but in a theorem statement it matters. Second, the proof leans heavily on the Han–Treglown structural results, which the authors themselves co-authored. That reliance is legitimate — those are published, independently proved theorems — but a reader should know that the paper inherits all of that machinery. Third, the p-range is admitted by the authors to be suboptimal; that is a limitation of the approach, not a flaw in the probability estimate.

Who is this for? Extremal and probabilistic combinatorialists working on factors, lattice-based methods, and random induced subgraphs. It deserves a serious referee. My recommendation: send it to a good journal, ask the authors to fix the garbled exponents and to add a sentence explaining the monotone decrease conjecture for q, and accept after those revisions.

Referee Report

0 major / 4 minor

Summary. The paper studies F-factors in random induced subgraphs of dense graphs and hypergraphs. Its main structural result (Theorem 3.2) asserts that, under a minimum-degree condition and a lattice condition coming from robust index vectors, the probability that H[p] contains an F-factor is at least 1/(rq) - o(1), where q is the order of a coset group associated with H. Applications include graph F-factors under the critical-chromatic-number threshold (Theorem 1.5), hypergraph perfect matchings under minimum ℓ-degree conditions (Theorem 1.6), and perfect matchings under codegree conditions (Theorem 1.7). The proof combines concentration inequalities, a Gauss-type lattice-point counting argument, and prior deterministic structural theorems of Han–Treglown and others. Sharpness constructions show the winning probabilities are asymptotically best possible for many H.

Significance. If the result holds, it is a substantial contribution to the study of spanning structures in random induced subgraphs. It moves beyond clique factors and gives a general lattice-based explanation of the probability 1/(rq): the 1/r factor is the usual divisibility of the sampled order, and the 1/q factor reflects the coset structure of the robust-index lattice. The paper also provides matching upper-bound constructions. The proof is detailed and internally coherent; the inheritance step (Lemma 4.1(V4)) is justified by Claim 4.4 and the concentration bounds of Lemma 4.3, and the use of prior deterministic theorems is not circular. The main issue is that several displayed definitions and constants are garbled or too optimistic, but these are local and repairable.

minor comments (4)

[Theorems 1.5–1.7] The displayed definitions of h are garbled and do not match the proofs. From the values t=2r^{k-1}-1, t=2s-1, and t=2s-2 used in the proofs, Theorem 3.2 gives h=4r^k-2r-2, h=max{2k, 2k(2s-1)-2}, and h=max{2k, 4k(s-1)-2}, respectively. The current Theorem 1.5 statement even appears to have a division-by-zero issue for r=2. These should be corrected.
[Proof of Theorem 3.2, (U1)–(U3)] After randomly splitting U' into two almost equal parts, the constants in the displayed events are too large. For a family of s-sets, the expected fraction that falls into one half is 2^{-s}, so (U1), (U2), and (U3) should have constants divided by 2^{r-1}, 2^{tr-1}, and 2^r, respectively. In particular, (U2) as written cannot follow from (V3) and Lemma 2.5 when |U^-|≈|U'|/2. The hierarchy can absorb the smaller constants, so the proof is repairable, but the current text is inaccurate.
[Proof of Theorem 3.2, Step 1] In the greedy covering of V'_0, a previously chosen copy F_j has r vertices in U^+, so it eliminates at most r m^{r-2} candidate (r-1)-sets, not (r-1)m^{r-2}. The constant is immaterial because ρ is tiny, but the displayed bound should be corrected.
[Theorem 3.2, 'In particular' part] The proof of the equality statement explicitly sets V0=∅. This condition is not stated in the 'In particular' sentence. If the robustness condition is interpreted as applying to every copy of F, then property (i) may force V0 to be empty, but the statement should make this explicit for clarity.

Circularity Check

0 steps flagged

No significant circularity found; the probability bound is derived from a new lattice-point-counting argument and external deterministic theorems, not from assuming the target result.

full rationale

The central claim in Theorem 1.5 is not obtained by fitting or by renaming an input. For each H in the stated class, q is defined as the order of the coset group Q(P, L^mu_{P,F}(H)) built from robust index vectors of F-copies in H. Lemma 4.2 then proves, by Gauss lattice-point counting, that the sampled index vector falls in any fixed coset of L^mu_{P,F}(H) with probability 1/(rq) +/- epsilon. This is a genuine counting result, not a consequence of the definition of q. The lower bound P[H[p] contains an F-factor] >= 1/(rq) - epsilon follows by combining this uniform coset distribution with Lemma 4.1 (inheritance of the structural hypotheses) and the external deterministic criterion Theorem 3.1. Lemma 4.1(V4), flagged in the reader's summary, is not an unproven inheritance assumption: it is established by Claim 4.4, which produces a stable plateau mu* with I^{mu*}_{P,F}(H)=I^{mu*/4}_{P,F}(H), and by the concentration bounds of Lemma 4.3, giving I^{mu*}_{P,F}(H)=I^{mu*/2}_{P',F}(H') with high probability. The sharpness examples in Section 5 use the same Lemma 4.2 to exhibit graphs for which the factor event is contained in the coset event of probability 1/(rq), so the upper bound is derived, not assumed. The cited results from Han-Treglown, Han, and Han-Zhao are external published theorems whose assumptions do not include the random-induced-subgraph conclusion; the fact that some authors overlap with the present paper does not make the derivation circular. No equation in the paper reduces to its inputs by construction, and no fitted parameter is renamed as a prediction. Therefore the appropriate circularity score is 0.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 0 invented entities

The central claim introduces no fitted parameters and no new unobserved entities. It rests on prior structural theorems, many from the authors' own earlier work, together with standard analytic tools. The only new technical machinery is the random-sampling inheritance lemma and the Gauss-counting argument for coset probabilities.

axioms (6)

domain assumption Han–Treglown deterministic lattice criterion (Theorem 3.1) is correct and applicable.
Used as a black box: given minimum degree, good partition, and bounded coset group, F-factor existence is equivalent to q-solubility of the lattice system. This is the engine of the final step in the proof of Theorem 3.2.
domain assumption Good-partition and coset-bound lemmas from [13,12,14,9,3] (Lemmas 3.3, 3.4, 3.6–3.9, Proposition 3.5) hold.
The applications in Theorems 1.5–1.7 assume these prior structural results supply the required (F,β,t,c)-good partitions and the bounds on |Q(P,L^μ)|.
standard math Gauss lattice-point counting estimate (Lemma 2.6, from Tao–Vu) holds for all translates of a full-rank lattice.
Used in Lemma 4.2 to estimate the number of integer points of a lattice in a large box; the paper relies on this standard result.
standard math Concentration inequalities (Hoeffding, McDiarmid, Liebenau–Wormald) are valid in the stated forms.
Used throughout Lemma 4.1 and in the random-partition step; these are standard tools.
standard math The hierarchy of constants can be ordered as 1/n0 ≪ 1/C′ ≪ β, μ0 ≪ ε, ρ, γ, c, η, 1/r, 1/D, 1/q, 1/d, 1/t.
The proof assumes this hierarchy to make all union bounds, greedy-covering estimates, and leftover-degree estimates work simultaneously.
domain assumption The sharpness constructions (Construction 1, Construction 2, and the modular hypergraph construction in Section 5) satisfy the stated degree conditions.
The degree computations for the space barriers and the modular k-graphs are straightforward but not fully expanded in the text.

pith-pipeline@v1.3.0-daily-deepseek · 21460 in / 35431 out tokens · 291855 ms · 2026-07-31T23:57:43.459577+00:00 · methodology

0 comments

read the original abstract

Let $F$ be an $r$-vertex graph. In this paper, we study the $F$-factor problem in random induced subgraphs of dense graphs. We show that for any $r$-vertex graph $F$ and $\gamma>0$, if $H$ is an $n$-vertex graph with minimum degree at least $(1-1/\chi_{cr}(F)+\gamma)n$, then for every fixed $p \in (0,1)$, the random induced subgraph $H[p]$ contains an $F$-factor with probability at least $1/(rq)-o_n(1)$, where $q\in \mathbb{N}$ is the order of certain coset group defined from $H$. The probability is asymptotically best possible for infinitely many $F$ and $H$ and yields that a $1/(rq)-o_n(1)$ proportion of the subsets of $H$ induce $F$-factors, interestingly, regardless of whether $H$ itself admits an $F$-factor. Similar results are obtained for perfect matchings in hypergraphs under minimum degree conditions. Our proof combines concentration inequalities, lattice point counting in $\mathbb{Z}^d$ and structural theorems for $F$-factors in dense (hyper)graphs.

discussion (0)

Reference graph

Works this paper leans on

30 extracted references · 3 linked inside Pith

[1]

N. Alon, P. Frankl, H. Huang, V. Rödl, A. Ruciński, and B. Sudakov. Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels.J. Combin. Theory Ser. A, 119(6):1200–1215, 2012

2012
[2]

Alon and R

N. Alon and R. Yuster.H-factors in dense graphs.J. Combin. Theory Ser. B, 66(2):269–282, 1996

1996
[3]

Chang, H

Y. Chang, H. Ge, J. Han, and G. Wang. Matching of given sizes in hypergraphs.SIAM J. Discrete Math., 36(3):2323–2338, 2022

2022
[4]

Draganić, P

N. Draganić, P. Keevash, and A. Müyesser. Cyclic subsets in regular Dirac graphs.Int. Math. Res. Not., (14), 2025

2025
[5]

P. Erdős. A selection of problems and results in combinatorics.Combin. Probab. Comput., 8(1-2):1–6, 1999. Recent trends in combinatorics (Mátraháza, 1995)

1999
[6]

Ferber and V

A. Ferber and V. Jain. Uniformity-independent minimum degree conditions for perfect matchings in hypergraphs. arXiv:1903.12207, 2019

Pith/arXiv arXiv 1903
[7]

Frankl and A

P. Frankl and A. Kupavskii. The Erdős matching conjecture and concentration inequalities.J. Combin. Theory Ser. B, 157:366–400, 2022

2022
[8]

W. Fu, Y. Han, G. Wang, J. Yan, P. Zhang, and Z. Zhou. Sharp small-deviation inequalities for sums of independent nonnegative random variables.arXiv:2607.23980, 2026

Pith/arXiv arXiv 2026
[9]

Gan and J

L. Gan and J. Han. On the Keevash-Knox-Mycroft Conjecture.J. Combin. Theory Ser. B, 174:214–242, 2025

2025
[10]

Hajnal and E

A. Hajnal and E. Szemerédi. Proof of a conjecture of P. Erdős. InCombinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969), volume 4 ofColloq. Math. Soc. János Bolyai, pages 601–623. North-Holland, Amsterdam-London, 1970

1969
[11]

J. Han. Near perfect matchings ink-uniform hypergraphs.Combin. Probab. Comput., 24(5):723–732, 2015

2015
[12]

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

2017
[13]

Han and A

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

2020
[14]

Han and J

J. Han and J. Zhao. Perfect matchings in random sparsifications of dense hypergraphs. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2430–2454. SIAM, 2026

2026
[15]

Hoeffding

W. Hoeffding. Probability inequalities for sums of bounded random variables.J. Amer. Statist. Assoc., 58:13–30, 1963

1963
[16]

Hunter, T

Z. Hunter, T. Liu, A. Milojević, and B. Sudakov. Cyclic subsets of tournaments.Random Structures Algorithms, 68(2):Paper No. e70056, 2026

2026
[17]

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.Internat. J. Found. Comput. Sci., 21(6):905–924, 2010

2010
[18]

Keevash, F

P. Keevash, F. Knox, and R. Mycroft. Polynomial-time perfect matchings in dense hypergraphs.Adv. Math., 269:265–334, 2015

2015
[19]

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

1983
[20]

J. Komlós. Tiling Turán theorems.Combinatorica, 20(2):203–218, 2000

2000
[21]

Komlós, G

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

2001
[22]

Kühn and D

D. Kühn and D. Osthus. The minimum degree threshold for perfect graph packings.Combinatorica, 29(1):65–107, 2009

2009
[23]

Liebenau and N

A. Liebenau and N. Wormald. Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph.J. Eur. Math. Soc., 26(1):1–40, 2023

2023
[24]

H. Liu, M. Niu, L. Wang, and Z. Yan. Tight staircase bounds for cyclic subsets below Dirac’s threshold. arXiv:2607.06551, 2026. 19

Pith/arXiv arXiv 2026
[25]

McDiarmid

C. McDiarmid. On the method of bounded differences. InSurveys in combinatorics, 1989 (Norwich, 1989), volume 141 ofLondon Math. Soc. Lecture Note Ser., pages 148–188. Cambridge Univ. Press, Cambridge, 1989

1989
[26]

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

2009
[27]

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
[28]

Sudakov and V

B. Sudakov and V. Vu. Local resilience of graphs.Random Structures Algorithms, 33(4):409–433, 2008

2008
[29]

W. Sun, S. Wei, and D. Yang. Clique factors in random samplings of regular graphs.arXiv:2512.20287v1, 2025

arXiv 2025
[30]

Tao and V

T. Tao and V. Vu.Additive combinatorics, volume 105 ofCambridge Studies in Advanced Mathematics. Cam- bridge University Press, Cambridge, 2006. JH, BW and JZ. School of Mathematics and Statistics, Beijing Institute of Technology, China, Email:(JH) han.jie@bit.edu.cn, (BW) bin.wang@bit.edu.cn, (JZ) jingwen.zhao@bit.edu.cn. 20

2006

[1] [1]

N. Alon, P. Frankl, H. Huang, V. Rödl, A. Ruciński, and B. Sudakov. Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels.J. Combin. Theory Ser. A, 119(6):1200–1215, 2012

2012

[2] [2]

Alon and R

N. Alon and R. Yuster.H-factors in dense graphs.J. Combin. Theory Ser. B, 66(2):269–282, 1996

1996

[3] [3]

Chang, H

Y. Chang, H. Ge, J. Han, and G. Wang. Matching of given sizes in hypergraphs.SIAM J. Discrete Math., 36(3):2323–2338, 2022

2022

[4] [4]

Draganić, P

N. Draganić, P. Keevash, and A. Müyesser. Cyclic subsets in regular Dirac graphs.Int. Math. Res. Not., (14), 2025

2025

[5] [5]

P. Erdős. A selection of problems and results in combinatorics.Combin. Probab. Comput., 8(1-2):1–6, 1999. Recent trends in combinatorics (Mátraháza, 1995)

1999

[6] [6]

Ferber and V

A. Ferber and V. Jain. Uniformity-independent minimum degree conditions for perfect matchings in hypergraphs. arXiv:1903.12207, 2019

Pith/arXiv arXiv 1903

[7] [7]

Frankl and A

P. Frankl and A. Kupavskii. The Erdős matching conjecture and concentration inequalities.J. Combin. Theory Ser. B, 157:366–400, 2022

2022

[8] [8]

W. Fu, Y. Han, G. Wang, J. Yan, P. Zhang, and Z. Zhou. Sharp small-deviation inequalities for sums of independent nonnegative random variables.arXiv:2607.23980, 2026

Pith/arXiv arXiv 2026

[9] [9]

Gan and J

L. Gan and J. Han. On the Keevash-Knox-Mycroft Conjecture.J. Combin. Theory Ser. B, 174:214–242, 2025

2025

[10] [10]

Hajnal and E

A. Hajnal and E. Szemerédi. Proof of a conjecture of P. Erdős. InCombinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969), volume 4 ofColloq. Math. Soc. János Bolyai, pages 601–623. North-Holland, Amsterdam-London, 1970

1969

[11] [11]

J. Han. Near perfect matchings ink-uniform hypergraphs.Combin. Probab. Comput., 24(5):723–732, 2015

2015

[12] [12]

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

2017

[13] [13]

Han and A

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

2020

[14] [14]

Han and J

J. Han and J. Zhao. Perfect matchings in random sparsifications of dense hypergraphs. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2430–2454. SIAM, 2026

2026

[15] [15]

Hoeffding

W. Hoeffding. Probability inequalities for sums of bounded random variables.J. Amer. Statist. Assoc., 58:13–30, 1963

1963

[16] [16]

Hunter, T

Z. Hunter, T. Liu, A. Milojević, and B. Sudakov. Cyclic subsets of tournaments.Random Structures Algorithms, 68(2):Paper No. e70056, 2026

2026

[17] [17]

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.Internat. J. Found. Comput. Sci., 21(6):905–924, 2010

2010

[18] [18]

Keevash, F

P. Keevash, F. Knox, and R. Mycroft. Polynomial-time perfect matchings in dense hypergraphs.Adv. Math., 269:265–334, 2015

2015

[19] [19]

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

1983

[20] [20]

J. Komlós. Tiling Turán theorems.Combinatorica, 20(2):203–218, 2000

2000

[21] [21]

Komlós, G

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

2001

[22] [22]

Kühn and D

D. Kühn and D. Osthus. The minimum degree threshold for perfect graph packings.Combinatorica, 29(1):65–107, 2009

2009

[23] [23]

Liebenau and N

A. Liebenau and N. Wormald. Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph.J. Eur. Math. Soc., 26(1):1–40, 2023

2023

[24] [24]

H. Liu, M. Niu, L. Wang, and Z. Yan. Tight staircase bounds for cyclic subsets below Dirac’s threshold. arXiv:2607.06551, 2026. 19

Pith/arXiv arXiv 2026

[25] [25]

McDiarmid

C. McDiarmid. On the method of bounded differences. InSurveys in combinatorics, 1989 (Norwich, 1989), volume 141 ofLondon Math. Soc. Lecture Note Ser., pages 148–188. Cambridge Univ. Press, Cambridge, 1989

1989

[26] [26]

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

2009

[27] [27]

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

[28] [28]

Sudakov and V

B. Sudakov and V. Vu. Local resilience of graphs.Random Structures Algorithms, 33(4):409–433, 2008

2008

[29] [29]

W. Sun, S. Wei, and D. Yang. Clique factors in random samplings of regular graphs.arXiv:2512.20287v1, 2025

arXiv 2025

[30] [30]

Tao and V

T. Tao and V. Vu.Additive combinatorics, volume 105 ofCambridge Studies in Advanced Mathematics. Cam- bridge University Press, Cambridge, 2006. JH, BW and JZ. School of Mathematics and Statistics, Beijing Institute of Technology, China, Email:(JH) han.jie@bit.edu.cn, (BW) bin.wang@bit.edu.cn, (JZ) jingwen.zhao@bit.edu.cn. 20

2006