{"id":"9d41fdb6-3d16-468d-911b-973792c100c3","arxiv_id":"2607.16118","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"The Erdős–Rogers function f_{s,s+1}(n) is Θ(√(n log n)) for every s ≥ 2, proved by a new random-graph construction.","lead":"This paper proves that for every s ≥ 2, the size of the largest K_s-free subset guaranteed in any K_{s+1}-free graph on n vertices grows like √(n log n), up to constant factors. The result settles the exact power of log n in a long-standing Ramsey-theoretic problem and matches a known lower bound.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's novelty hinges on an ambiguous summary of Mubayi–Verstraëte [36]; if [36] already proved O(√(n log n)), Theorem 1.1 is not new and the disproof of their conjecture is incoherent.","rationale":"The reader's verdict is CONDITIONAL, mainly because of the [36] citation issue and the external lower bound. I agree that the [36] ambiguity is the decisive concern for the paper's main claim: it determines whether Theorem 1.1 is new or already known. I did not find a concrete error in the probabilistic construction or in Lemmas 3.4/3.5; the apparent uniformity of the random K_s in Lemma 3.4 is justified by the vertex-transitivity of the random model, and the union bound gives (e/k)^k = o(1) as required. The lower bound from [28] is a standard external theorem about clique colourings and appears appropriately applied to K_{s+1}-free graphs. Therefore the verdict need not change: the paper should be accepted only after the [36] bound is checked and the typographical ambiguity is corrected. If the check shows the weaker bound was intended, the main theorem is new and the mathematical content is solid; if the stronger bound was intended, the claim of novelty collapses and the paper should be substantially reframed.","tokens_in":18896,"tokens_out":38733,"duration_ms":310044,"concrete_test":"Check the statement of the main theorem in Mubayi–Verstraëte [36] (Bull. LMS 57 (2025) 582–598, or the arXiv version) and record the exact upper bound: is it O(C(s)√(n log n)) or O(C(s)√n log n)? If the former, Theorem 1.1 for s≥3 was already known and the paper's disproof of [36, Conjecture 1] is untenable; if the latter, the apparent inconsistency is resolved and the novelty claim stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central mathematical proof appears internally sound: the construction is K_{s+1}-free (Lemma 2.3), the two key Lemmas 3.4 and 3.5 supply the required K_s in every large set, and the parameter identities such as m = 16k log n check out. The lower bound is imported from [28], but that is a legitimate external theorem and I found no reason to doubt its applicability. The load-bearing issue is instead an internal inconsistency in the paper's own description of prior work. Section 1 states that Mubayi–Verstraëte [36] already proved f_s(n) ≤ C(s)√(n log n) for every s ≥ 3. Since the same section cites [28] for the matching lower bound f_s(n) ≥ c√(n log n), this would already give Theorem 1.1 for s ≥ 3, making the claimed disproof of [36, Conjecture 1] logically impossible. The only way the narrative is coherent is if the intended [36] bound was the weaker O(√n log n), i.e. the square root applies only to n and the log is unsquared. The manuscript's typography repeatedly renders '√nlogn' without parentheses, so this ambiguity must be resolved against the published source. This is a novelty/crediting concern rather than a correctness flaw, but it is the single most load-bearing issue: if the strong reading is accurate, the paper's main theorem is not original.","agreement_with_reader":"partial"},"referee_report":null,"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hey,\n\nThe headline: the main theorem is probably correct and the construction is genuinely nice, but the paper needs a careful pass on how it credits Mubayi–Verstraëte [36]. The introduction says [36] already proved f_s(n) ≤ C(s)√(n log n). If that's literally right, Theorem 1.1 isn't new and the disproof of their conjecture is incoherent. I think it's a typo in the manuscript—the intended bound is O(√n log n), with the log unsquared—because the abstract and the rest of the paper treat log-exponent 1/2 as the new content. But the authors have to fix this before publication; right now a reader has to guess.\n\nWhat's actually new: the construction itself—two random blow-ups of K_s copies, with a two-stage edge deletion—and Theorem 1.2, which extends the upper bound to every K_s-free H. The proof of the upper bound checks out at the level I went through: the K_{s+1}-freeness argument is clean, the parameter bookkeeping (m=16k log n, β≈s^{-2}) is consistent, and Lemmas 3.4 and 5.1 do the heavy lifting plausibly. I didn't find a fatal hole.\n\nSoft spots: (1) The [36] citation ambiguity is load-bearing for novelty. The reader is right to flag it. (2) The lower bound is imported from Joret–Micek–Reed–Smid [28]. That's legitimate—an external theorem can be cited—but it means the Θ result stands only as deep as [28] is solid. (3) The write-up is terse in places, especially the deterministic counting in Section 5; a referee should push for more detail. (4) The constant in Theorem 3.1 is O(s^3), and Section 6.1 discusses improvements; that's fine.\n\nWho's it for: people working on Ramsey theory and Erdős–Rogers functions. It deserves a serious referee, with a request to clarify the [36] statement and expand a few proof steps. If the citation resolves as expected, this is a nice result.","headline":"The main theorem looks right and the construction is original, but the paper must fix an ambiguous citation of Mubayi–Verstraëte before the novelty claim is credible.","tokens_in":19821,"tokens_out":2069,"would_cite":true,"duration_ms":17488,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C55","05C80","05C35","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every s ≥ 2, the Erdős–Rogers function satisfies f_s(n) = Θ(√(n log n)), settling its order up to constants.","keywords":["Erdős–Rogers function","Ramsey theory","K_s-free subgraphs","random graph construction","clique chromatic number","probabilistic combinatorics","extremal graph theory","blow-up graphs"],"falsifier":"For a fixed s (say s=3) and moderately large n, simulate the paper's random construction with the stated parameters and check whether a random k-set of size k = C(s)√(n log n) contains a copy of K_s with probability at least 1 − e^{−Ω(m)}, as Lemma 3.4 predicts. A violation would indicate a flaw in the closed-edge argument. Alternatively, find an infinite family of K_{s+1}-free graphs on n vertices in which the largest K_s-free subset has size o(√(n log n)); such graphs would contradict the claimed lower bound.","tokens_in":18568,"feed_emoji":"🧩","tokens_out":7401,"duration_ms":60771,"temperature":0.7,"pith_summary":"The paper establishes that the Erdős–Rogers function f_s(n)—the largest K_s-free subset guaranteed in every K_{s+1}-free graph on n vertices—grows as Θ(√(n log n)) for every s ≥ 2. The upper bound comes from an explicit probabilistic construction: a K_{s+1}-free graph in which every set of at least C(s)√(n log n) vertices contains a copy of K_s. This determines the exponent of log n to be exactly 1/2, refuting a conjecture in the literature that the exponent was 1−o(1). The lower bound is not proved here but is imported from a known theorem on clique chromatic numbers. The same construction extends to show that for any K_s-free graph H, the generalised function f_{H,K_s}(n) is O(√(n log n)).","feed_headline":"Erdős–Rogers function is Θ(√(n log n))","feed_subtitle":"A random overlay of two blow-ups plus edge deletions gives the matching upper bound; log exponent is exactly 1/2.","key_machinery":"The key machinery is a random overlay of two r-blow-ups of the balanced complete s-partite graph, followed by two edge-deletion steps. The first deletion removes any edge lying in the vertex sets of at least two random blow-ups; the second deletes one edge from every triangle not contained in a single blow-up, choosing an edge of the minority colour. This produces a K_{s+1}-free graph. The proof tracks 'closed edges'—pairs of vertices connected by a path of length at most two—because an edge can be deleted only if it is closed with respect to either the other colour or earlier-revealed blow-ups. The two central lemmas bound the number of closed edges in any k-set and show that, conditional o","core_discovery":"The central claim is Theorem 1.1: for every s ≥ 2, f_s(n) = Θ(√(n log n)). The paper proves the upper bound by constructing, for each s and large n, a K_{s+1}-free graph G on n vertices in which every set of at least C(s)√(n log n) vertices spans a copy of K_s. The construction takes two independent random unions of m copies of the balanced complete s-partite graph with ℓ/r vertices, blows each copy up by a factor r, overlays them on the same vertex set, and then deletes edges in two steps: first removing any edge lying in the vertex sets of two different blow-ups, then deleting one edge from every triangle that is not contained in a single blow-up. The resulting graph is K_{s+1}-free. The p","pith_inferences":["The closed-edge statistic may be a reusable tool for other graph-removal problems: any deletion rule that only removes edges with a short witness path can be analysed by the same two-lemma structure.","The external lower bound is a soft dependency: a self-contained proof of the matching lower bound would make the Θ result internal, and the paper's framework suggests that the clique-chromatic-number theorem might be provable by similar probabilistic blow-up methods.","A natural testable extension is to vary the deletion rules (e.g., deleting edges with dependent probabilities) to see whether the √(n log n) threshold is robust or an artifact of the specific two-step deletion.","The s-dependence of the upper bound constant is likely not optimal; the paper's own remarks indicate a possible improvement to O(s^{3/2}√(log s)), and one could attempt to push the construction to O(s) or even O(1) by changing the overlay scheme."],"forward_implications":["The exponent of log n in f_s(n) is exactly 1/2 for all s ≥ 2, so the function is now determined up to a constant factor; the conjecture that the exponent was 1−o(1) is false.","For any K_s-free graph H, the generalised Erdős–Rogers function f_{H,K_s}(n) is O(√(n log n)); when H contains K_{s−1}, it is Θ(√(n log n)).","The construction avoids algebraic objects entirely, using only random blow-ups and edge deletions, suggesting a broader template for forcing subgraphs into large sets of F-free graphs.","The lower bound's constant is independent of s, while the upper bound's constant is a polynomial in s; the paper sketches an improved constant O(s^{3/2}√(log s)) with more work.","A natural barrier of k = Θ(s √(log s) √(n log n)) is identified for constructions of this type, indicating where new ideas would be needed."],"fun_headline_variants":["Erdős–Rogers function pinned to Θ(√(n log n))","Tight bound for Erdős–Rogers: √(n log n)","Erdős–Rogers: every large set contains a K_s","Asymptotic for Erdős–Rogers function settled","Erdős–Rogers function: Θ(√(n log n)) for all s"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The matching lower bound rests entirely on an external theorem asserting that every graph on n vertices can be vertex-coloured with O(√(n/log n)) colours so that no maximal clique is monochromatic; if that theorem fails, the paper only proves an upper bound and the Θ statement collapses.","fun_headline_variants_meta":{"raw":{"variants":["Erdős–Rogers function pinned to Θ(√(n log n))","Tight bound for Erdős–Rogers: √(n log n)","Erdős–Rogers: every large set contains a K_s","Asymptotic for Erdős–Rogers function settled","Erdős–Rogers function: Θ(√(n log n)) for all s"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000935,"raw_usage":{"total_tokens":3810,"prompt_tokens":687,"completion_tokens":3123,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":431,"completion_tokens_details":{"reasoning_tokens":3016}},"tokens_in":431,"tokens_out":3123,"duration_ms":20407,"temperature":1.0,"reasoning_tokens":3016,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T21:17:28.560074+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed s (say s=3) and moderately large n, simulate the paper's random construction with the stated parameters and check whether a random k-set of size k = C(s)√(n log n) contains a copy of K_s with probability at least 1 − e^{−Ω(m)}, as Lemma 3.4 predicts. A violation would indicate a flaw in the closed-edge argument. Alternatively, find an infinite family of K_{s+1}-free graphs on n vertices in which the largest K_s-free subset has size o(√(n log n)); such graphs would contradict the claimed lower bound.","supporting_citations":[],"review_version":1}