{"id":"b9773848-97e3-4a67-8e23-57976e85fb8d","arxiv_id":"1909.01461","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For fixed s, optimal K_s-free pseudorandom graphs would imply r(s,t)=t^{s-1+o(1)}, and new constructions improve the cycle Ramsey lower bounds to r(C5,t) > t^{11/8} and r(C7,t) > t^{11/9}.","lead":"This paper proves new lower bounds for Ramsey numbers of cycles, improving the exponent of t for C5 and C7, and shows that optimal pseudorandom clique-free graphs would settle the exponent for classical Ramsey numbers. Ramsey numbers are a central object in combinatorics that appear throughout computer science and discrete mathematics, so exponent improvements attract wide interest.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"C7 bound in Theorem 5 relies on Ree–Tits octagons, which exist only for q=2^{2n+1}; this sparse sequence cannot yield the stated (1+o(1))t^{11/9} for all t.","rationale":"The reader's conditional verdict was driven by the omitted C7 derivation and the unstated parameters of the Ree–Tits octagons. My read sharpens that concern: the omitted details are not merely a matter of exposition, because the known parameter range for octagons is q=2^{2n+1}, giving a multiplicative gap of 4^9 in the corresponding t-values. Monotonicity of Ramsey numbers then forces a constant bounded away from 1 for arbitrary t, so the (1+o(1)) form in Theorem 5's second bound is not justified by the cited construction. The C5 theorem, the conditional Corollary 2, and the general framework remain credible; the C5 bound uses generalized hexagons of order (q,q^3), which exist for all prime powers and give a dense enough t-sequence. The overall paper still merits the same conditional disposition, with the C7 statement needing either a corrected constant, a subsequential formulation, or a genuinely dense family of girth-16 incidence graphs.","tokens_in":8013,"tokens_out":46396,"duration_ms":434091,"concrete_test":"Consult the classification in Van Maldeghem's 'Generalized Polygons' (or the cited [18,36]) to verify whether finite thick generalized octagons of order (q,q^2) exist for all prime powers q or only for q=2^{2n+1}. If only the latter, compute the monotonicity interpolation for t between consecutive t_q: since t_{q+1}/t_q = 4^9, the best uniform constant in r(C7,t) ≥ c t^{11/9} is at most 4^{-11} up to o(1), which would disprove the stated (1+o(1)) form. Then request the omitted C7 derivation to see whether a dense family of girth-16 incidence graphs with the same part sizes is intended.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 5 states r(C7,t) ≥ (1+o(1))t^{11/9} as t→∞, but the cited Ree–Tits octagons exist only for q=2^{2n+1} (Feit–Higman classification of generalized octagons; see Van Maldeghem, Generalized Polygons). The construction then gives n≈q^{11} and t≈q^9 only along this sparse sequence: consecutive q are separated by a factor 4, so consecutive t are separated by 4^9. For arbitrary large t, monotonicity of r(C7,t) can at best give r(C7,t) ≥ c t^{11/9} with c roughly 4^{-11} by using the preceding t_i; it cannot give a (1+o(1)) constant. The paper explicitly says the C7 details are omitted, but in this case the parameter range is exactly what controls the leading constant. The C5 half of Theorem 5 is not affected: generalized hexagons of order (q,q^3) exist for all prime powers q, so q and t≈q^8 can be chosen densely enough for the (1+o(1)) form.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper is a short note connecting pseudorandom (n,d,lambda)-graphs to Ramsey lower bounds. Theorem 1 gives a general lower bound on r(F,t) from any F-free (n,d,lambda)-graph, via an Alon-Rodl count of independent sets followed by a random-subset argument; Corollary 2 turns this into a conditional statement that optimal K_s-free pseudorandom graphs would imply r(s,t)=t^{s-1+o(1)}. Corollaries 3 and 4 apply the same theorem to odd cycles and to C6 and C10, giving polylogarithmic improvements over the random C_l-free-process bounds. Theorem 5 uses a different random block construction on incidence graphs of generalized hexagons and Ree-Tits octagons to obtain r(C5,t) >= (1+o(1))t^{11/8} and r(C7,t) >= (1+o(1))t^{11/9}.","tokens_in":1418,"tokens_out":1476,"duration_ms":800835,"significance":"If the C7 part is corrected, the paper's significance is real: the C5 lower bound is the first unconditional exponent improvement for a cycle-complete Ramsey number over the random C_l-free process, and the conditional result on K_s-free pseudorandom graphs gives a clean reduction of a classical problem. The C5 computation is explicit and sound, and the random-subset application of the Alon-Rodl bound is elegant and likely reusable. The paper also correctly identifies that the C7 exponent 11/9 still exceeds the random-process exponent 6/5, so the central novelty survives even after the leading-constant issue in the C7 statement is fixed.","major_comments":[{"comment":"The displayed bound in Eq. (5) is r(F,t) > n/(20 lambda log^2 n), but the proof gives r(F,t) >= pn - 1 with p = log^2 n/(2 e^2 lambda), hence r(F,t) = Omega(n log^2 n / lambda). The reciprocal placement of log^2 n is a typo: the intended bound is r(F,t) > n log^2 n/(20 lambda). This is load-bearing because Corollaries 2-4 use the stronger form; for example, substituting the printed (5) into the Alon-Kahale parameters in Corollary 3 gives a denominator log^{(4l-6)/(l-2)} t rather than the claimed log^{2/(l-2)} t, while the corrected bound gives exactly the stated corollaries.","section":"Section 2, Eq. (5)"},{"comment":"The C7 half of Theorem 5 is not supported as stated. The construction uses Ree-Tits octagons, which exist only for q = 2^{2n+1}, as in the cited Van Maldeghem reference. The construction gives n ~ q^{11} and t ~ q^9 only along this sparse geometric progression. Since r(C7,t) is monotone, filling the gaps for arbitrary t yields at best r(C7,t) >= c t^{11/9} with a constant of order 4^{-11}, not (1+o(1)) t^{11/9}. The sentence 'We omit the details for this case' hides exactly the calculation that controls the leading constant. The theorem and abstract should be corrected, either by restricting the asymptotic to t of the form q^9 with q = 2^{2n+1}, or by weakening the conclusion to r(C7,t) = Omega(t^{11/9}). The C5 half is not affected, because generalized hexagons of order (q,q^3) exist for all prime powers q.","section":"Section 3, Theorem 5 (second statement)"}],"minor_comments":[{"comment":"For t_u = 0, the probability that I intersects N_G(u) spans no edge in H is 1, while 2^{1-t_u} = 2. The displayed equality in (9) and (10) should be an inequality P(e(I cap N_G(u)) = 0) <= 2^{1-t_u} and similarly for the product; the subsequent expectation bound is unaffected because the inequality is the needed upper bound.","section":"Section 3, Eqs. (9)-(10)"},{"comment":"The phrase 'we may take t = (1+o(1))q^8' is too terse. To make the exponent m - (q+1)t tend to -infinity, one must take t = (1+epsilon)q^8 with epsilon q^9 -> infinity; the authors should state this explicitly rather than leaving the o(1) unspecified.","section":"Section 3, proof of Theorem 5"},{"comment":"The assertion that H is automatically F-free when G is L(F)-free is stated without proof. A short justification is needed, because the correspondence between a copy of F in H and a copy of some member of L(F) in G is not immediate.","section":"Section 4, Theorem 7"},{"comment":"The remark that for l=3 the bound 'matches the lower bound of Spencer' should specify that this is Spencer's local-lemma bound r(3,t) = Omega(t^2/log^2 t), not the later Kim bound, to avoid ambiguity.","section":"Abstract and Corollary 3"}],"recommendation":"major_revision","confidential_remarks":"The paper is a short note with a sound C5 result and a useful conditional theorem, but the C7 statement as written is false for arbitrary t because of the sparse existence of Ree-Tits octagons. I recommend major revision rather than rejection: weakening the C7 conclusion to an Omega(t^{11/9}) bound preserves the claimed exponent improvement, and the typo in Eq. (5) is clearly fixable. The authors should also be asked to make the omitted C7 details explicit, since they are directly relevant to the leading constant."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this note has one clean conditional theorem and one solid new unconditional exponent improvement for r(C5,t), but the C7 claim in Theorem 5 does not hold as stated. The paper deserves refereeing, but the C7 part needs to be fixed.\n\nThe conditional theorem (Theorem 1 + Corollary 2) is the kind of reduction that makes a classical problem worth restating: if optimal K_s-free pseudorandom graphs exist, then r(s,t)=t^{s-1+o(1)}. The proof is a short application of the Alon–Rödl independent set bound and it checks out. The polylog improvements for odd cycles and for C6, C10 are routine applications of known pseudorandom constructions, but they form a useful companion.\n\nThe real new meat is the C5 lower bound r(C5,t) ≥ (1+o(1))t^{11/8}, which beats the random-process exponent. The random block construction is sound: the girth-12 incidence graph of the generalized hexagon kills C5, and the first moment calculation gives independence number below q^8. That is a genuine exponent improvement, and it is the first of its kind for a graph with cycles, as far as I know.\n\nThe soft spot is C7. The proof is not given, and the stress-test concern is correct: the Ree–Tits octagons exist only for q=2^{2n+1}, a sparse set, so the (1+o(1)) form for all t cannot be obtained from those graphs by monotonicity. You get at best c t^{11/9} for a small constant. The abstract and Theorem 5 need amending, either by stating the bound only along the sequence or by lowering the constant. This is a real error, not cosmetic, but it does not damage the C5 result or the conditional theorem.\n\nMinor points: Theorem 1's inequality (5) is weaker than what the proof actually shows; no harm. The concluding remarks are speculative but clearly labelled. The citation pattern looks fine.\n\nOverall: this is a worthy note for a combinatorics audience. A referee should send it back for revision rather than desk-reject. The C5 part is publishable as is; the C7 claim needs correction.","headline":"A clean conditional theorem and a real C5 exponent improvement are undercut by an overreaching C7 claim that relies on sparse Ree–Tits octagons.","tokens_in":8824,"tokens_out":7329,"would_cite":true,"duration_ms":66307,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D10","05C55","05B25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Optimal clique-free pseudorandom graphs would pin the Ramsey exponent to $t^{s-1+o(1)}$; a related counting argument improves the lower bounds for cycle Ramsey numbers.","keywords":["Ramsey numbers","pseudorandom graphs","(n,d,λ)-graphs","independent sets","odd cycles","random graph process","generalized hexagons","Ramsey exponents"],"falsifier":"For the C5 bound, check whether the needed bipartite incidence graphs with parts of sizes $(q+1)(q^8+q^4+1)$ and $(q^3+1)(q^8+q^4+1)$, degrees $q+1$ and $q^3+1$, and girth at least 12 exist for every large $q$; if they exist only sparsely, the $(1+o(1))$ form can fail. For the conditional claim, exhibiting an $s\\ge 4$ for which every $K_s$-free $(n,d,\\lambda)$-graph with $d=\\Omega(n^{1-1/(2s-3)})$ has $\\lambda=\\omega(\\sqrt{d})$ would remove the hypothesis of Corollary 2.","tokens_in":7766,"feed_emoji":"🎲","tokens_out":15031,"duration_ms":118753,"temperature":0.7,"pith_summary":"This note proves that pseudorandom graphs are sufficient to determine the asymptotic exponents of classical Ramsey numbers. If $K_s$-free $(n,d,\\lambda)$-graphs with near-optimal degree $d=\\Omega(n^{1-1/(2s-3)})$ and $\\lambda=O(\\sqrt{d})$ exist, then $r(s,t)=t^{s-1+o(1)}$, matching the known upper bound up to subpolynomial factors. Unconditionally, it gives new lower bounds for cycle-complete Ramsey numbers: $r(C_5,t)\\ge (1+o(1))t^{11/8}$ and $r(C_7,t)\\ge (1+o(1))t^{11/9}$, improving the exponent over the bounds from the random $C_\\ell$-free process. It also improves $r(C_\\ell,t)$ by polylogarithmic factors for all odd $\\ell\\ge 5$ and for $\\ell\\in\\{6,10\\}$. The engine is a short counting lemma for independent sets in pseudorandom graphs, plus a random block construction over high-girth incidence graphs.","feed_headline":"Ideal clique-free graphs would settle Ramsey exponents","feed_subtitle":"Near-optimal clique-free graphs would give tight Ramsey bounds; new block constructions beat random processes for C5 and C7.","key_machinery":"The central object is the family of $(n,d,\\lambda)$-graphs: $d$-regular graphs on $n$ vertices whose nontrivial adjacency eigenvalues are at most $\\lambda$ in absolute value. The load-bearing tool is a counting lemma stating that, for $t\\ge 2n\\log^2 n/d$, the number of independent $t$-sets in such a graph is at most $(2e^2\\lambda/\\log_2 n)^t$. A random-sampling step then keeps each vertex with probability about $\\log^2 n/(2e^2\\lambda)$ and deletes one vertex from every independent $t$-set, producing an $F$-free graph with no independent set of size $t$ and order roughly $n/(\\lambda\\log n)$. For the cycle results, the machinery is a random block construction: take a high-girth bipartite graph $G$ with parts $U,V$, split each $U$-neighborhood randomly into two parts, and put a complete bipartite graph between them; the resulting graph $H$ on $V$ is $F$-free because of the girth, and its independent-set count is controlled by the part sizes and degrees.","core_discovery":"The paper's central claim is that an $F$-free $(n,d,\\lambda)$-graph forces a lower bound on the Ramsey number $r(F,t)$: whenever such a graph exists, $r(F,t)>n/(20\\lambda\\log_2 n)$ for $t=\\lceil 2n\\log^2 n/d\\rceil$. For $F=K_s$, optimal pseudorandom graphs with $d=\\Omega(n^{1-1/(2s-3)})$ and $\\lambda=O(\\sqrt{d})$ then give $r(s,t)=\\Omega(t^{s-1}/\\log^{2s-4}t)$, which combines with the known upper bound to yield $r(s,t)=t^{s-1+o(1)}$. For odd cycles, applying the same theorem to existing pseudorandom $C_\\ell$-free graphs yields $r(C_\\ell,t)=\\Omega(t^{(\\ell-1)/(\\ell-2)}/\\log^{2/(\\ell-2)}t)$ for odd $\\ell\\ge 5$, and for $\\ell=6,10$ it gives $r(C_6,t)=\\Omega(t^{5/4}/\\sqrt{\\log t})$ and $r(C_{10},t)=\\Omega(t^{9/8}/\\log^{1/4}t)$. The random block construction, starting from incidence graphs of generalized hexagons and octagons, proves $r(C_5,t)\\ge (1+o(1))t^{11/8}$ and $r(C_7,t)\\ge (1+o(1))t^{11/9}$; the paper notes these are the first graphs $F$ containing cycles for which the lower-bound exponent for $r(F,t)$ surpasses the random $F$-free process bound.","pith_inferences":["One consequence the paper leaves implicit: if $r(s,t)$ turned out to be smaller than $t^{s-1+o(1)}$ for some $s\\ge 4$, then optimal $K_s$-free pseudorandom graphs would be impossible, making the construction problem as hard as the Ramsey exponent itself.","The incidence-graph ingredient for the cycle bounds is limited to the few girths realized by generalized polygons; extending the exponent improvements to longer odd cycles would require new high-girth bipartite graphs with comparably tight degree ratios.","Because the random-sampling proof uses only a small number of random bits, an explicit construction of optimal $K_s$-free pseudorandom graphs would likely translate, after derandomization, into explicit Ramsey graphs with the same exponent; this is suggested by the paper's remark that its construction uses fewer random bits than the random process.","The exponents $11/8$ and $11/9$ are not proven optimal; the block method is a template, and any high-girth bipartite graph with parameters satisfying the expected-count inequality would push these exponents upward."],"forward_implications":["If optimal $K_s$-free pseudorandom graphs exist for every fixed $s\\ge 4$, then the classical Ramsey exponent is determined: $r(s,t)=t^{s-1+o(1)}$.","For every odd $\\ell\\ge 5$, the lower bound $r(C_\\ell,t)=\\Omega(t^{(\\ell-1)/(\\ell-2)}/\\log^{2/(\\ell-2)}t)$ improves the random $C_\\ell$-free process bound by a polylogarithmic factor.","For $\\ell=6$ and $\\ell=10$, the new bounds $r(C_6,t)=\\Omega(t^{5/4}/\\sqrt{\\log t})$ and $r(C_{10},t)=\\Omega(t^{9/8}/\\log^{1/4}t)$ exceed the previous best lower bounds.","The block construction proves $r(C_5,t)\\ge (1+o(1))t^{11/8}$ and $r(C_7,t)\\ge (1+o(1))t^{11/9}$, raising the exponent in these cycle-complete Ramsey lower bounds.","The generalized random block theorem converts any sufficiently dense $L(F)$-free bipartite graph into a lower bound on $r(F,t)$, so better such graphs would immediately improve Ramsey exponents."],"supporting_citations":[{"why":"Supplies the independent-set counting theorem that drives Theorem 1.","marker":"[5]"},{"why":"Provides the random H-free process lower bounds that the paper improves or matches for cycles.","marker":"[9]"},{"why":"Supplies the $C_\\ell$-free pseudorandom graphs for odd $\\ell$ used in Corollary 3.","marker":"[3]"},{"why":"Gives the eigenvalue lower bound for $K_s$-free graphs that defines the optimality condition in Corollary 2.","marker":"[35]"},{"why":"Source for the generalized quadrangle and hexagon graphs behind the C6 and C10 bounds.","marker":"[10]"},{"why":"Provides the polarity-graph constructions of generalized quadrangles and hexagons used in Corollary 4.","marker":"[27]"},{"why":"Contains the generalized hexagon and octagon incidence graphs used in the C5 and C7 block construction.","marker":"[18]"},{"why":"Standard reference for the generalized polygons whose incidence graphs supply the girth and degree parameters in Theorem 5.","marker":"[36]"}],"fun_headline_variants":["Pseudorandom graphs could pin down Ramsey exponents","Optimal Ramsey bounds conditional on clique-free graphs","New C5, C7 Ramsey lower bounds beat random process","If ideal clique-free graphs exist, Ramsey numbers optimal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The C5 and C7 bounds assume that the required high-girth bipartite incidence graphs with the stated part sizes and degrees exist for all large q; the conditional Ramsey-exponent result assumes optimal $K_s$-free pseudorandom graphs exist, a major open problem.","fun_headline_variants_meta":{"raw":{"variants":["Pseudorandom graphs could pin down Ramsey exponents","Optimal Ramsey bounds conditional on clique-free graphs","New C5, C7 Ramsey lower bounds beat random process","If ideal clique-free graphs exist, Ramsey numbers optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00105,"raw_usage":{"total_tokens":4504,"prompt_tokens":1133,"completion_tokens":3371,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":749,"completion_tokens_details":{"reasoning_tokens":3320}},"tokens_in":749,"tokens_out":3371,"duration_ms":64176,"temperature":1.0,"reasoning_tokens":3320,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:18:20.416696+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the C5 bound, check whether the needed bipartite incidence graphs with parts of sizes $(q+1)(q^8+q^4+1)$ and $(q^3+1)(q^8+q^4+1)$, degrees $q+1$ and $q^3+1$, and girth at least 12 exist for every large $q$; if they exist only sparsely, the $(1+o(1))$ form can fail. For the conditional claim, exhibiting an $s\\ge 4$ for which every $K_s$-free $(n,d,\\lambda)$-graph with $d=\\Omega(n^{1-1/(2s-3)})$ has $\\lambda=\\omega(\\sqrt{d})$ would remove the hypothesis of Corollary 2.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the independent-set counting theorem that drives Theorem 1."},{"cited_title":"Bohman, P","cited_arxiv_id":null,"evidence_quote":"Provides the random H-free process lower bounds that the paper improves or matches for cycles."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the $C_\\ell$-free pseudorandom graphs for odd $\\ell$ used in Corollary 3."},{"cited_title":"Sudakov, T","cited_arxiv_id":null,"evidence_quote":"Gives the eigenvalue lower bound for $K_s$-free graphs that defines the optimality condition in Corollary 2."},{"cited_title":"Brouwer, A","cited_arxiv_id":null,"evidence_quote":"Source for the generalized quadrangle and hexagon graphs behind the C6 and C10 bounds."},{"cited_title":"Lazebnik, V","cited_arxiv_id":null,"evidence_quote":"Provides the polarity-graph constructions of generalized quadrangles and hexagons used in Corollary 4."},{"cited_title":"Govaert, H","cited_arxiv_id":null,"evidence_quote":"Contains the generalized hexagon and octagon incidence graphs used in the C5 and C7 block construction."},{"cited_title":"Van Maldeghem, Generalized polygons, Modern Birkh¨ auser Classics","cited_arxiv_id":null,"evidence_quote":"Standard reference for the generalized polygons whose incidence graphs supply the girth and degree parameters in Theorem 5."}],"review_version":1}