{"id":"f7be598c-4fdf-4386-b759-ae709165b267","arxiv_id":"2607.27870","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Random induced subgraphs of dense graphs contain F-factors with asymptotically tight probability 1/(rq), where q is the order of a lattice coset group.","lead":"This paper proves that, under a natural minimum-degree condition, a random induced subgraph of a dense graph contains a perfect tiling by any fixed small graph F with probability at least 1/(rq), where r is the number of vertices of F and q is a lattice obstruction derived from the host graph. The bound is asymptotically tight for infinitely many pairs (F,H), and similar results are proved for perfect matchings in hypergraphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader identified Lemma 4.1(V4) as the most fragile premise, and I agree that this is the part to scrutinize. However, on inspection the proof handles it: Claim 4.4 supplies a plateau μ* with I^{μ*}=I^{μ*/4}, and the concentration argument of Lemma 4.3 then gives the two inclusions with strict margins. The coset-uniformity argument in Lemma 4.2 is also technically sound. The remaining issue is the typographical garbling of the exponent h in Theorem 1.5, but this is a statement-level blemish, not a mathematical gap in the proof of the probability bound. Consequently the reader's ACCEPT verdict should stand unchanged.","tokens_in":21842,"tokens_out":51068,"duration_ms":436470,"concrete_test":"Run a Monte Carlo simulation for F=K_{2,4} and H=K_{n/2,n/2} with p=1/2 and n up to a few thousand, and compare the empirical probability that H[p] has a K_{2,4}-factor against 1/12-o(1). If the deviation exceeds the expected finite-size error, revisit Lemma 4.1(V4) or Lemma 4.2; otherwise the central probability claim is corroborated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking the proof, I find no load-bearing flaw in the central claim. The reader's flagged point, Lemma 4.1(V4), is not an unproven inheritance assumption: it is established by Claim 4.4 (a finite descent producing a plateau I^{μ*}=I^{μ*/4}) together with the concentration bounds in Lemma 4.3. The strict margins are real: for v in I^{μ*}, the sampled count is at least (3/4)μ* m^r, while for v outside I^{μ*/4} it is at most (1/2)μ* m^r, so the desired equality at threshold μ*/2 follows. Lemma 4.2 is sound: Gauss lattice-point counting gives the 1/(rq) coset distribution, and its conditional use in Theorem 3.2 is legitimate because i_P(Vp) is independent of Vp∩V0. The only real defect is the garbled exponent h in the statement of Theorem 1.5, which the reader also noticed; it does not undermine the probability assertion. Thus the central theorem survives scrutiny.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":22071,"tokens_out":47543,"duration_ms":385191,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Theorems 1.5–1.7"},{"comment":"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.","section":"Proof of Theorem 3.2, (U1)–(U3)"},{"comment":"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.","section":"Proof of Theorem 3.2, Step 1"},{"comment":"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.","section":"Theorem 3.2, 'In particular' part"}],"recommendation":"minor_revision","confidential_remarks":"I support publication after minor revisions. The central theorem and its proof are sound; the issues are local typos and constant slips. The proofs rely on previously published structural results, including some by the authors, but these are external and not circular. The authors should carefully correct the h definitions in Theorems 1.5–1.7 and the constants in the random-partition step of Theorem 3.2."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nWho 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.","headline":"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.","tokens_in":22531,"tokens_out":1729,"would_cite":true,"duration_ms":19611,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","05C80","05C65","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"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","keywords":["F-factor","random induced subgraph","critical chromatic number","lattice method","coset group","dense hypergraphs","perfect matching","index vector"],"falsifier":"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.","tokens_in":21737,"feed_emoji":"🧩","tokens_out":6452,"duration_ms":61140,"temperature":0.7,"pith_summary":"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.","feed_headline":"Random induced subgraphs factor with exact odds 1/(rq)","feed_subtitle":"A lattice parameter of the host graph, not just sampled vertex count, controls which subsets admit F-factors.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Random induced subgraphs hit F-factors with odds 1/(rq)","Lattice parameter q fixes factor odds at 1/(rq)","Exact odds 1/(rq) for F-factors in random subgraphs","Subset factor chance: 1/(rq), set by lattice","Hidden lattice sets factor probability to 1/(rq)"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Random induced subgraphs hit F-factors with odds 1/(rq)","Lattice parameter q fixes factor odds at 1/(rq)","Exact odds 1/(rq) for F-factors in random subgraphs","Subset factor chance: 1/(rq), set by lattice","Hidden lattice sets factor probability to 1/(rq)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000233,"raw_usage":{"total_tokens":1357,"prompt_tokens":799,"completion_tokens":558,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":543,"completion_tokens_details":{"reasoning_tokens":462}},"tokens_in":543,"tokens_out":558,"duration_ms":5077,"temperature":1.0,"reasoning_tokens":462,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T23:57:43.459577+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}