{"id":"3d86ee99-a58e-4324-84f2-6a887cdf26ad","arxiv_id":"2411.14138","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every strictly 1-balanced graph F, the random graph G(n,p) gets an F-factor exactly at the sharp threshold where F-isolated vertices vanish, confirming Ruciński's conjecture.","lead":"This paper proves that for every strictly 1-balanced graph F, the sharp probability threshold for the random graph G(n,p) to contain an F-factor is exactly the threshold at which the last F-isolated vertex disappears. This confirms a 30-year-old conjecture by Ruciński and unifies earlier partial results for complete graphs and 'nice' graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 5.5's 'so B2 holds' is not justified for long bad cycles: the avoidable configuration built from Fi may have more than 2e(F)^2 F-edges, outside the event B2.","rationale":"The reader's weakest assumption correctly focused on the imported classification Lemma 3.1 and its role in controlling coupling failures. I agree that this lemma is load-bearing; the proof of the main theorem would collapse without it. However, the most concrete failure mode I find is not the lemma's exact statement but how Section 5.5 combines it with the bounded-size event B2. Lemma 3.1 bounds the size of the subconfiguration inducing a single F-edge by e(F) F-edges, but Section 5.5 then builds an avoidable configuration from an entire bad clean cycle Fi, whose length is not controlled by Lemma 3.1 and can in principle be much larger than 2e(F)^2. The event B2 was deliberately restricted to avoidable configurations with at most 2e(F)^2 F-edges precisely so that Lemma 3.2 gives o(1) by a finite union bound; the proof in Section 5.5 needs this restriction but does not verify it. I do not assert that the theorem is false; I am pointing to a specific proof step that is currently unjustified. A correct repair might show that bad cycles relevant to a first failure must have bounded length, or that any larger constructed configuration contains a bounded avoidable subconfiguration. Until such an argument appears, the paper's central Proposition 5.1 has a gap. This does not change the reader's CONDITIONAL verdict, since the gap is repairable and the rest of the proof appears coherent, but it strengthens the need for a careful revision.","tokens_in":16822,"tokens_out":33252,"duration_ms":310691,"concrete_test":"Re-derive Section 5.5 while tracking the number of F-edges in (Fi\\I)∪⋃_{F′∈I} C(F′). Either prove from Lemma 3.1 and the definition of a bad cycle that this number is always at most 2e(F)^2, or exhibit a clean F-cycle Fi of length k>2e(F)^2 with all but one of its F-edges in H0 and the missing F-edge induced by a short clean cycle in C1, and check that the resulting union contains no bounded avoidable subconfiguration. For F=K3 this reduces to a finite combinatorial search up to length 2e(F)^2+1; any witness invalidates the current proof of Proposition 5.1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Proposition 5.1, Section 5.5 handles bad cycles Fi (i<0 with Ei⊂Ej∪R) by applying Lemma 3.1 to each induced F-edge F′ of Fi. If no bounded avoidable configuration appears, the proof forms (Fi\\I) ∪ ⋃_{F′∈I} C(F′), where C(F′)∈C1 is a short clean cycle inducing F′, and concludes 'so B2 holds'. But B2, defined in Section 5.2, only bounds avoidable configurations with at most 2e(F)^2 F-edges. The constructed union has e(Fi) + Σ_{F′∈I} e(C(F′)) F-edges; Lemma 3.1 only gives e(C(F′))≤e(F) and gives no bound on e(Fi), the length of the bad cycle. Since C^c_1 in Section 5.3 enumerates all potential clean cycles — not just those of length at most e(F) — long bad cycles are not excluded. If a long Fi occurs with, say, one induced F-edge, the union is a connected F-graph of nullity at least 2 whose size can exceed 2e(F)^2; such a graph need not contain a bounded avoidable subconfiguration, so the fact that P(B2)=o(1) does not cover it. Unless an implicit bound e(Fi)=O(e(F)^2) for bad cycles is proved, the case analysis of Proposition 5.1 has a genuine gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies sharp thresholds for F-factors in the Erdős–Rényi random graph G(n,p), where F is a strictly 1-balanced graph. The main result, Theorem 1.5, states that for every strictly 1-balanced F with s>0 edges on r≥2 vertices, the sharp threshold for the existence of an F-factor coincides with the sharp threshold p* for the disappearance of F-isolated vertices, confirming a conjecture of Ruciński. The proof follows the coupling strategy of Riordan and Heckel: it constructs a coupling (Theorem 1.6) between G(n,p) and the random F-graph HF(n,π) such that whp every F-edge of HF is present in G. The coupling handles the main technical difficulty, the existence of induced F-edges, by classifying them via Riordan's Lemma 3.1 into avoidable configurations and clean F-cycles. A novel ingredient is the introduction of 'dummy edges' and the auxiliary random d-graph G*(n,p) to treat sparse clean F-cycles. Once the coupling is established, Theorem 1.5 follows by merging F-edges on the same vertex set to obtain a random r-uniform hypergraph and applying Kahn's solution to Shamir's problem (Theorem 1.4).","tokens_in":17154,"tokens_out":13216,"duration_ms":116514,"significance":"If correct, the paper resolves a thirty-year-old conjecture by Ruciński and unifies the previously known cases (complete graphs and 'nice' graphs) into a general statement for all strictly 1-balanced graphs. The coupling theorem (Theorem 1.6) is a strong, flexible tool that may transfer other spanning-structure results from random hypergraphs to random graphs. The paper contains several original ideas, notably the use of dummy edges to balance the probabilities of sparse clean cycles and the proof that clean d-cycles are strictly balanced (Lemma 3.4), which is used to control overlaps. The exposition is generally clear and the proof is detailed, building on the substantial prior work of Riordan and Heckel.","major_comments":[{"comment":"The proof that Qcb = 0 unless B holds contains an unjustified step. For each induced F-edge F′ of the bad cycle Fi, the text claims 'there exists a cycle C(F′) in C1 that induces F′'. However, Lemma 3.1 only guarantees a clean F-cycle in the F-graph of the shadow graph of HF(n,π), not necessarily a clean cycle whose F-edges are all present in HF(n,π). The set C1 consists of clean cycles that are actually present in HF(n,π) (and coupled to G*). A clean cycle appearing only in the shadow graph may have some F-edges missing from HF(n,π), so it is not in C1. Consequently, the constructed configuration (Fi\\I) ∪ ⋃_{F′∈I} C(F′) is not shown to be a sub-F-graph of HF(n,π), and the conclusion 'so B2 holds' does not follow. This is a load-bearing gap in the proof of Proposition 5.1, because bad cycles with length > e(F) are not excluded by the definition of C1.","section":"Section 5.5"},{"comment":"Even if each C(F′) were in C1, the avoidable configuration (Fi\\I) ∪ ⋃_{F′∈I} C(F′) may have more than 2e(F)^2 F-edges, so it is not covered by the event B2, which only controls avoidable configurations with at most 2e(F)^2 F-edges. The text does not provide any bound on e(Fi), the length of a bad cycle; the index set C_1^c in Section 5.3 enumerates all potential clean cycles, including those of arbitrarily large length. Thus a long bad cycle with only one induced F-edge yields a connected F-graph of nullity at least 2 and size exceeding 2e(F)^2, which need not contain a bounded avoidable subconfiguration. The fact that P(B2)=o(1) is therefore insufficient to rule it out. An additional argument bounding the length of bad cycles, or an extension of B2 to unbounded avoidable configurations with a corresponding whp bound, is required.","section":"Section 5.5 and Section 5.2"},{"comment":"The statements of Theorems 1.5 and 1.6 are for r≥2, but the proof in Section 3.1 begins 'We fix a strictly 1-balanced graph F on r > 2 vertices' and the case r=2 is never treated. For r=2, the graph F is necessarily K2, and the result is the classical perfect matching threshold, which is known and also follows from Theorem 1.2 (the complete-graph case). The paper should either add a short separate argument for r=2 or modify the statements of Theorems 1.5 and 1.6 to r>2. As written, the theorem statements exceed what the proof establishes.","section":"Section 3.1 and Theorems 1.5, 1.6"}],"minor_comments":[{"comment":"In the proof of Proposition 4.4, the phrase 'there is a coupling of of (X_C)_C' contains a duplicated 'of' and should be corrected.","section":"Section 4.2"},{"comment":"The statement 'π′j = 1 exactly if Fj is in some cycle in C1' would benefit from clarification: 'in' means 'is one of the F-edges of'. This distinction matters because Section 5.4 and Section 5.5 rely on the difference between an F-edge being a member of a clean cycle and being merely induced by its shadow graph.","section":"Section 5.3"},{"comment":"The display 'cF(G(n,p)) = cF(G*(n,p)) ⊇ HF(n,π)' uses the notation cF(G*) without a definition. Since G* is a d-graph containing dummy edges, it should be stated explicitly that cF(G*) refers to the set of copies of F using only the usual edges of G*.","section":"Section 2.4"},{"comment":"In the proof of Lemma 4.2, the inequality chain leading to f(S) < 0 is concise; in particular, the application of Lemma 3.4 to the case where S includes the dummy edge is implicit. A short explanatory sentence would improve readability and prevent ambiguity.","section":"Section 4.1, Lemma 4.2"}],"recommendation":"major_revision","confidential_remarks":"The gap identified in Section 5.5 is substantial and affects the central coupling theorem. That said, the overall strategy is credible and the gap appears to be repairable—for instance, by proving that bad cycles have bounded length or by enlarging B2 to cover avoidable configurations of unbounded size with a suitable whp bound. The r=2 issue is minor and easily fixed. I would not recommend rejection at this stage, but the revision must address the Section 5.5 argument in detail. It may also be worth verifying the exact content of Riordan's Lemma 19, since the proof's use of C1 depends on whether the clean cycle produced by that lemma is present in the underlying F-graph or only in its shadow graph."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe short version: this paper very likely establishes the sharp F-factor threshold for all strictly 1-balanced graphs, resolving Ruciński's conjecture, and it introduces two genuinely useful techniques (dummy edges and a direct Chen–Stein coupling over clean cycles). But I think there's a gap in Section 5.5 that needs to be closed before I'd trust the main theorem.\n\nWhat's good: The theorem is a clean unification of the complete-graph result (Heckel/Riordan) and Riordan's 'nice graph' result. The coupling theorem (1.6) is stated with explicit constants and should transfer to k-connectivity and loose Hamilton cycles. I checked several of the key bounds — Lemma 3.4 (clean d-cycles are strictly balanced) and the overlap estimates in Section 4.1 — and they look right. The use of Kahn's solution to Shamir's problem is appropriate, and the self-citations are for context, not for the central derivation.\n\nThe soft spot: Section 5.5, in the proof of Proposition 5.1. When handling a bad cycle F_i with E_i ⊂ E_j ∪ R, the text says that if no bounded avoidable configuration appears, then each induced F-edge in F_i is induced by a cycle in C1, and the union (F_i\\I) ∪ ⋃ C(F') is an avoidable configuration, 'so B2 holds.' But B2 only bounds avoidable configurations with at most 2e(F)^2 F-edges. F_i can be a clean cycle of arbitrary length; the union has e(F_i) + Σ e(C(F')) F-edges, which can exceed 2e(F)^2. I don't see an argument that this large union contains a bounded avoidable subconfiguration. Since C^c_1 enumerates all clean cycles, long bad cycles are not excluded. This is load-bearing: if a long bad cycle can exist, Q_cb ≥ 1 and the bound π_j ≥ (1−Q)p^{e(F)} fails. Unless there's an implicit bound on the length of bad cycles that I'm missing, this is a genuine gap.\n\nMinor: Theorem 1.5 states r≥2, but Section 3.1 fixes r>2 and never returns to r=2. The r=2 case is just perfect matching, so it's a one-line fix, but as written the statement is not proved.\n\nIf the Section 5.5 gap is closed, this is a very strong paper. As is, it deserves a serious referee, but the referee should push on that point. I'd bring it to a reading group and would cite it if I worked on factor thresholds.\n\nBest,\n[Your name]","headline":"A serious, well-written proof of Ruciński's conjecture that has a real gap in Section 5.5, plus a minor r=2 mismatch; fix the gap and it's a strong paper.","tokens_in":17722,"tokens_out":11771,"would_cite":false,"duration_ms":98533,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","05C80","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every strictly 1-balanced graph F, the sharp threshold for an F-factor in G(n,p) is exactly the sharp threshold for the disappearance of F-isolated vertices.","keywords":["F-factor","sharp threshold","random graph G(n,p)","strictly 1-balanced graph","F-isolated vertices","random F-graph","coupling","perfect matching in random hypergraphs"],"falsifier":"Find a strictly 1-balanced graph F and an F-graph with an induced F-edge whose minimal inducing subgraph has more than e(F) F-edges and is neither an avoidable configuration nor a clean F-cycle, or compute for a concrete F (such as a four-cycle) that the F-factor threshold differs from the threshold for disappearance of F-isolated vertices.","tokens_in":16619,"feed_emoji":"🎲","tokens_out":10927,"duration_ms":89200,"temperature":0.7,"pith_summary":"This paper proves that for every strictly 1-balanced graph F, the sharp threshold for the random graph G(n,p) to contain an F-factor — a partition of the vertex set into vertex-disjoint copies of F — is exactly the sharp threshold for the disappearance of F-isolated vertices, meaning vertices that lie in no copy of F. This confirms a conjecture from 1992 that the two thresholds coincide for all strictly 1-balanced F, settling the leading constant in the F-factor threshold for a broad natural class of graphs. Earlier results at this precision covered only complete graphs and a restricted class of 'nice' graphs. The proof constructs a coupling between G(n,p) and a random F-graph so that, with high probability, every F-edge of the latter appears as a copy of F in the former; the F-factor threshold then follows from the sharp threshold for perfect matchings in random hypergraphs.","feed_headline":"F-factor thresholds proven sharp for all strictly 1-balanced graphs","feed_subtitle":"For every strictly 1-balanced F, the F-factor threshold equals the threshold for F-isolated vertices to vanish.","key_machinery":"The argument is carried by the random F-graph $H_F(n,\\pi)$ together with a classification of induced F-edges. An F-edge is induced by an F-graph when it is not one of the F-edges but is forced to appear as a copy of F in the shadow graph; such forced edges are exactly what can break a direct coupling. A classification lemma says that every induced F-edge is induced by a sub-F-graph with at most $e(F)$ F-edges that is either an avoidable configuration (a connected F-graph of nullity at least two) or a clean F-cycle (a cycle of F-edges overlapping in single vertices, or two F-edges overlapping in exactly two vertices). Sparse clean F-cycles, consisting of two F-edges sharing exactly one graph edge, have a probability mismatch with their shadow graphs, so the paper inserts independent dummy edges for them and works with the random d-graph $G^*(n,p)$; every clean d-cycle then has exactly $k e(F)$ edges and is strictly balanced. Clean cycles in $H_F$ and $G^*$ are matched with high probability through a Poisson approximation theorem, and the two-stage coupling then extends the matching to all F-edges by bounding conditional inclusion probabilities.","core_discovery":"The main theorem states that for any strictly 1-balanced graph F with s>0 edges on r≥2 vertices, the sharp threshold for the existence of an F-factor in G(n,p) is\n\n$$p^* = \\left(\\frac{\\operatorname{aut}(F)}{r!}\\,\\frac{\\ln n}{\\binom{n-1}{r-1}}\\right)^{1/s},$$\n\nprecisely the sharp threshold for the disappearance of F-isolated vertices given by Theorem 1.1. Here strictly 1-balanced means that every proper nontrivial subgraph S of F has smaller 1-density, $e(S)/(v(S)-1) < e(F)/(v(F)-1)$, and $\\operatorname{aut}(F)$ is the number of automorphisms of F. The supporting coupling theorem states that for suitable p and any $\\pi \\le (1-n^{-\\delta}) p^{e(F)}$, the random graph G(n,p) and the random F-graph $H_F(n,\\pi)$ can be coupled so that, with high probability, every F-edge of $H_F$ is present as a copy of F in G. The paper further notes that the same results hold for strictly 1-balanced uniform hypergraphs, with a simplified proof in uniformity greater than 3.","pith_inferences":["The constructed coupling is the standard ingredient for hitting-time results, so it is plausible that in the random graph process the step at which the last F-isolated vertex disappears also contains an F-factor for every strictly 1-balanced F; the paper does not state this.","The dummy-edge device for sparse clean cycles may be reusable in other threshold problems where a rare subconfiguration causes the expected counts of the random graph and the auxiliary structure to differ by a polynomial factor.","The strict balancedness of clean d-cycles suggests that other hypergraph threshold results, such as k-connectivity or loose Hamilton cycles, could be transferred to G(n,p) for arbitrary strictly 1-balanced F, not only the perfect-matching case.","A concrete numerical check for a small F, such as a four-cycle, around $(1\\pm\\varepsilon)p^*$ would test how quickly the F-factor probability transitions; the theorem predicts a sharp jump within that window."],"forward_implications":["For every strictly 1-balanced graph F, the sharp threshold for F-factors is the explicit formula above, determined only by the edge count, vertex count, and automorphism count of F.","The F-factor threshold equals the threshold for the disappearance of F-isolated vertices, so the last vertex not contained in any copy of F is, with high probability, the only obstruction to an F-factor.","The coupling transfers threshold results from random F-graphs to G(n,p), making results for perfect matchings, and potentially for connectivity and loose Hamilton cycles, available for arbitrary strictly 1-balanced F.","The same sharp threshold and coupling hold for strictly 1-balanced uniform hypergraphs, with a simpler proof when the uniformity exceeds 3."],"supporting_citations":[{"why":"Supplies the classification of induced F-edges into avoidable configurations and clean F-cycles, and the coupling framework that the proof adapts.","marker":"[24]"},{"why":"Provides the two-stage coupling algorithm and conditional-probability bounds that are extended here from triangles to general strictly 1-balanced F.","marker":"[13]"},{"why":"Establishes that the F-factor threshold and the F-isolated-vertex threshold have the same order for strictly 1-balanced F, setting the sharp-result target.","marker":"[16]"},{"why":"Gives the sharp threshold for perfect matchings in random r-uniform hypergraphs, used to convert the coupling into an F-factor threshold.","marker":"[18]"},{"why":"Supplies the companion hitting-time threshold for perfect matchings in random hypergraphs, supporting the same transfer of results.","marker":"[17]"},{"why":"Supplies the Poisson approximation theorem used to couple clean F-cycles with clean d-cycles.","marker":"[3]"},{"why":"Formulated the conjecture that the two sharp thresholds coincide and provided the first threshold bounds for factors.","marker":"[27]"},{"why":"Contains the sharp threshold for the disappearance of F-isolated vertices (Theorem 1.1) and the general treatment of F-isolated vertices.","marker":"[15]"}],"fun_headline_variants":["F-factor thresholds sharp for every strictly 1-balanced graph","30-year Rucinski conjecture on F-factors resolved","Exact F-factor thresholds in random graphs","All strictly 1-balanced F get sharp factor thresholds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on the claim that whenever a copy of F is forced to appear by other copies, the forcing configuration is always one of two known small types; if a third type existed, the coupling could fail outside the controlled error event.","fun_headline_variants_meta":{"raw":{"variants":["F-factor thresholds sharp for every strictly 1-balanced graph","30-year Rucinski conjecture on F-factors resolved","Exact F-factor thresholds in random graphs","All strictly 1-balanced F get sharp factor thresholds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000599,"raw_usage":{"total_tokens":2862,"prompt_tokens":1069,"completion_tokens":1793,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":685,"completion_tokens_details":{"reasoning_tokens":1730}},"tokens_in":685,"tokens_out":1793,"duration_ms":12864,"temperature":1.0,"reasoning_tokens":1730,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:30:16.615827+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a strictly 1-balanced graph F and an F-graph with an induced F-edge whose minimal inducing subgraph has more than e(F) F-edges and is neither an avoidable configuration nor a clean F-cycle, or compute for a concrete F (such as a four-cycle) that the F-factor threshold differs from the threshold for disappearance of F-isolated vertices.","supporting_citations":[{"cited_title":"Random cliques in random graphs and sharp thresholds forF-factors","cited_arxiv_id":null,"evidence_quote":"Supplies the classification of induced F-edges into avoidable configurations and clean F-cycles, and the coupling framework that the proof adapts."},{"cited_title":"Random triangles in random graphs","cited_arxiv_id":null,"evidence_quote":"Provides the two-stage coupling algorithm and conditional-probability bounds that are extended here from triangles to general strictly 1-balanced F."},{"cited_title":"Factors in random graphs.Random Structures & Algorithms, 33(1):1–28, 2008","cited_arxiv_id":null,"evidence_quote":"Establishes that the F-factor threshold and the F-isolated-vertex threshold have the same order for strictly 1-balanced F, setting the sharp-result target."},{"cited_title":"Asymptotics for Shamir’s problem.Advances in Mathematics, 422:109019, 2023","cited_arxiv_id":null,"evidence_quote":"Gives the sharp threshold for perfect matchings in random r-uniform hypergraphs, used to convert the coupling into an F-factor threshold."},{"cited_title":"Hitting times for Shamir’s problem","cited_arxiv_id":null,"evidence_quote":"Supplies the companion hitting-time threshold for perfect matchings in random hypergraphs, supporting the same transfer of results."},{"cited_title":"Two moments suffice for Poisson ap- proximations: the Chen-Stein method.The Annals of Probability, pages 9–25, 1989","cited_arxiv_id":null,"evidence_quote":"Supplies the Poisson approximation theorem used to couple clean F-cycles with clean d-cycles."},{"cited_title":"Matching and covering the vertices of a random graph by copies of a given graph","cited_arxiv_id":null,"evidence_quote":"Formulated the conjecture that the two sharp thresholds coincide and provided the first threshold bounds for factors."},{"cited_title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","cited_arxiv_id":null,"evidence_quote":"Contains the sharp threshold for the disappearance of F-isolated vertices (Theorem 1.1) and the general treatment of F-isolated vertices."}],"review_version":1}