{"id":"547a036f-430e-475b-bfd4-9be4444429e1","arxiv_id":"2607.09049","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every n-vertex graph of VC-dimension ≤ d has a homogeneous set of size at least n^{(C d)^{-d}} for an absolute constant C.","lead":"Graphs of VC-dimension at most d always contain a clique or independent set of size at least n to the power (C d)^{-d}. This sharpens the previous double-exponential bound and gives explicit exponents for many geometric and model-theoretic graph classes.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the regularity black box as the sole external ingredient and correctly judges the rest of the argument to be self-contained and low-risk. My re-inspection of the dimension-drop, fixed-power iteration and constant absorption confirms that the single-exponential improvement is obtained exactly as claimed; no internal inconsistency or untracked loss of polynomial factors appears. Consequently the ACCEPT verdict and high-confidence assessment stand without adjustment.","tokens_in":22966,"tokens_out":543,"duration_ms":21442,"concrete_test":"Re-derive the size lower bound of the η-restricted subgraph in Lemma 2.11 for the base case r=1 (where C_0 consists of complete/empty graphs and s_0=1) by expanding all absolute constants from Lemmas 2.4, 2.7–2.9; confirm that the resulting exponent is still of the form (h·1)^{-1} and that the same h works for the inductive step s_r ≤ C r s_{r-1}.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1.2 / Theorem 3.1) rests on a fully explicit inductive sparsification that improves the NSS double-exponential exponent by inducting on external VC-dimension classes C_r (rather than |U_{r+1}|) and by fixing the restrictedness improvement power at 4 (Lemma 2.10) instead of letting it depend on the previous reciprocal exponent. The only external input is the quantitative ultra-strong regularity lemma (Theorem 2.3) supplying equipartitions of length ≤ ε^{-K d}; the paper correctly invokes the polynomial dependence (via Fox–Pach–Suk) inside Lemma 2.4 and absorbs the resulting factors into the absolute constant h of the final bound s_r ≤ (h r)^r. Dimension-drop (Lemma 2.6), purity lifting (Lemma 2.1), iterative alternatives (Lemmas 2.7–2.11) and cograph conversion (Lemma 2.12) form a closed chain with no hidden circularity or missing quantitative control. The probabilistic upper bound of order 1/d in Remark 5.2 shows the new lower bound is not tight, but does not affect correctness of the claimed single-exponential guarantee.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper proves a quantitative Erdős–Hajnal theorem for graphs of VC-dimension at most d: there is an absolute constant h such that every such n-vertex graph G satisfies max{ω(G), α(G)} ≥ |G|^{(h d)^{-d}} (Theorem 1.2). This improves the double-exponential lower bound η_d ≥ 2^{-2^{O(d)}} of Nguyen–Scott–Seymour to a single-exponential form. The argument works with the nested classes C_r of graphs free of a bi-induced copy of the universal shattering bigraph U_{r+1}, obtains pure blockades via the quantitative ultra-strong regularity lemma, proves a dimension-drop lemma for mixed vertices on the pattern graph, and runs an iterative sparsification that yields either a highly restricted induced subgraph or a complete/anticomplete blockade; a standard cograph conversion then produces the recurrence s_r ≤ C r s_{r-1} with s_0 = 1. Quantitative consequences are derived for polynomial Rödl subgraphs, multicolour hypergraph Ramsey numbers under bounded VC-dimension, tournaments, NIP/semi-algebraic graphs, Boolean combinations, bounded-rank and bounded-sign-rank graphs, and dot-product threshold graphs.","tokens_in":23268,"tokens_out":889,"duration_ms":17459,"significance":"The result is a clean and substantial quantitative improvement on a theorem that settled a conjecture of Fox–Pach–Suk. By inducting directly on external VC-dimension rather than on the exponential size of U_{d+1} and by fixing the restrictedness power in the sparsification step, the authors replace a double-exponential dependence by a single-exponential one of the form (C d)^{-d}. The proof is fully explicit, self-contained once the published regularity lemma is granted, and immediately yields concrete exponents for a long list of geometric, algebraic and model-theoretic graph classes. The matching probabilistic upper bound of order 1/d (Remark 5.2) shows that the new lower bound is not tight, yet the single-exponential guarantee is already the best general bound available and will be useful for further quantitative work in induced Ramsey theory.","major_comments":[],"minor_comments":[{"comment":"In the statement of Lemma 2.4 the constant b is chosen as 34K; a short parenthetical remark that any sufficiently large multiple of K works would make the dependence on the regularity constant completely transparent.","section":null},{"comment":"Lemma 2.10 (the fixed-power iteration) is used with p=4 throughout; it would help the reader if the authors briefly noted that any fixed p≥2 works and that the concrete choice only affects the absolute constant h.","section":null},{"comment":"In the proof of Theorem 3.1 the authors enlarge s_{r-1} if necessary so that s_{r-1}≥ r. While correct, a one-line remark that this only weakens the inductive hypothesis would remove any momentary doubt.","section":null},{"comment":"Section 4.3 lists many applications by citing the reductions of Nguyen–Scott–Seymour; adding a single sentence that the only change is the substitution of the new exponent (hd)^{-d} would make the section self-contained for readers who do not have [36] open.","section":null},{"comment":"Typographical: in the abstract the displayed inequality uses |G| (Cd)^{-d} without the exponentiation symbol rendered as a superscript in some PDF viewers; a small LaTeX adjustment would improve readability.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a high-quality quantitative refinement of a recent breakthrough. I see no reason to delay publication; the improvements are genuine and the write-up is careful. Fit for a top combinatorics journal is excellent."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper upgrades the Nguyen–Scott–Seymour EH exponent for VC-dimension ≤ d from double-exponential to single-exponential: max{\\omega,\\alpha} ≥ n^{(h d)^{-d}}. That is the whole story, and it is real.\n\nWhat is new is the inductive organization. Instead of forbidding the huge universal bigraph U_{d+1} and inducting on its size (which is exponential in d), they work with the nested classes C_r of graphs with no bi-induced U_{r+1}, i.e., external VC-dimension ≤ r. The key dimension-drop lemma (2.6) shows that if a vertex is mixed on many blocks of a pure blockade, the pattern graph lands in C_{r-1}. Combined with a fixed-power (y to y^4) sparsification iteration rather than a power that depends on the previous reciprocal exponent, the recurrence collapses to s_r ≤ C r s_{r-1}, hence s_r ≤ (C r)^r. The rest is the usual pure-blockade + cograph conversion machinery, carefully quantified. The only external black box is the already-published polynomial ultra-strong regularity lemma; they absorb its factors cleanly into the absolute constant.\n\nThe write-up is complete and inspectable: every quantitative constant is tracked through Lemmas 2.1–2.12 and the induction in Section 3. The long list of corollaries (Rödl, hypergraph Ramsey, tournaments, sign-rank, semi-algebraic, Boolean combinations, etc.) is just the same reductions with the new exponent plugged in; useful but not the main contribution. Remark 5.2 gives a matching-order probabilistic upper bound of roughly 1/d, so the new lower bound is not tight, but that does not touch correctness.\n\nSoft spots are minor. The absolute constant h is not optimized, and the regularity dependence still sits inside the tower of constants, but nothing is hidden or circular. Citation pattern is appropriate; they correctly credit NSS and Fox–Pach–Suk.\n\nThis is for anyone working on quantitative induced Ramsey, geometric graph theory, or NIP/semi-algebraic extremal problems. The math is solid. I would send it to referees without hesitation and would cite the main theorem myself.","headline":"Clean single-exponential EH bound for bounded VC-dimension by smarter induction on external dimension classes; solid and worth citing.","tokens_in":23872,"tokens_out":571,"would_cite":true,"duration_ms":6181,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C69","05D10","68Q32"],"pacs":[],"model":"grok-4.5","headline":"Graphs of VC-dimension d contain a clique or independent set of size n to the power 1 over (C d)^d.","keywords":["Erdős–Hajnal conjecture","VC-dimension","homogeneous sets","iterative sparsification","pure blockades","external VC-dimension","polynomial Rödl property","hypergraph Ramsey"],"falsifier":"Either exhibit, for infinitely many $d$, an $n$-vertex graph of VC-dimension $d$ whose largest clique or independent set has size smaller than $n^{(C d)^{-d}}$ for every fixed $C$, or show that every such graph already contains a homogeneous set larger than $n$ to a power better than $1/d$, matching the random-graph upper bound of order $1/d$ given in the paper.","tokens_in":23871,"feed_emoji":"📐","tokens_out":832,"duration_ms":7791,"temperature":0.7,"texified_at":"2026-08-05T21:17:17.044553+00:00","pith_summary":"The paper improves the quantitative form of the Erdős–Hajnal property for graphs of bounded VC-dimension. Earlier work already showed that every $n$-vertex graph of VC-dimension at most $d$ has a clique or independent set of size at least $n$ to a positive power that depends only on $d$, but the power was only double-exponentially small in $d$. The new bound replaces that double-exponential loss by a single-exponential one: the power is at least $\\frac{1}{(C d)^d}$ for an absolute constant $C$. The argument works by refining an iterative sparsification procedure. Instead of inducting on the size of a large forbidden bipartite pattern, it inducts directly on the external VC-dimension, using a dimension-drop lemma that forces the pattern graph of a pure blockade to live in a lower class whenever a vertex is mixed on many blocks. The same improved exponent immediately yields sharper polynomial Rödl statements, multicolour hypergraph Ramsey bounds under bounded VC-dimension, and explicit Erdős–Hajnal-type estimates for tournaments, semi-algebraic graphs, NIP structures, bounded-rank and bounded-sign-rank graphs, and Boolean combinations of low-complexity relations.","texify_model":"deepseek-v4-flash","texify_usage":{"total_tokens":6187,"prompt_tokens":698,"completion_tokens":5489,"prompt_tokens_details":{"cached_tokens":0},"prompt_cache_hit_tokens":0,"prompt_cache_miss_tokens":698,"completion_tokens_details":{"reasoning_tokens":4850}},"feed_headline":"VC-dimension-d graphs get single-exponential Erdős–Hajnal","feed_subtitle":"Largest clique or independent set is at least n to the power 1 over (C d)^d","key_machinery":"Dimension-drop on pure blockades: if a vertex is mixed on every block of an $\\epsilon$-pure blockade whose pattern graph contains a bi-induced copy of the universal shattering bigraph $U_r$, then the original graph contains a bi-induced copy of $U_{r+1}$; consequently the pattern graph itself belongs to the class $C_{r-1}$ of graphs of external VC-dimension at most $r-1$, allowing a clean inductive step that multiplies the reciprocal exponent by only a linear factor in $r$.","core_discovery":"There exists an absolute constant $h$ such that every graph $G$ of VC-dimension at most $d$ satisfies $\\max\\{\\omega(G),\\alpha(G)\\} \\ge |G|^{(h d)^{-d}}$. Equivalently the Erdős–Hajnal exponent $\\eta_d$ is at least $(h d)^{-d}$, improving the previous lower bound $2^{-2^{O(d)}}$.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Bounded VC-dimension yields single-exp Erdős–Hajnal sets","VC-dim d graphs have hom sets of size n to the (Cd)^{-d}","Sharper single-exponential EH bound for VC-dimension d","Homogeneous sets n^{(Cd)^{-d}} in graphs of VC-dim ≤d","Improved η_d ≥ (Cd)^{-d} for VC-bounded graphs"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The whole construction rests on a quantitative ultra-strong regularity lemma that partitions a VC-dimension $d$ graph into at most $\\epsilon^{-K d}$ nearly pure pairs; if that polynomial length bound fails, the size of the extracted blockades collapses.","fun_headline_variants_meta":{"raw":{"variants":["Bounded VC-dimension yields single-exp Erdős–Hajnal sets","VC-dim d graphs have hom sets of size n to the (Cd)^{-d}","Sharper single-exponential EH bound for VC-dimension d","Homogeneous sets n^{(Cd)^{-d}} in graphs of VC-dim ≤d","Improved η_d ≥ (Cd)^{-d} for VC-bounded graphs"]},"model":"grok-4.5","effort":"low","cost_usd":0.004788,"raw_usage":{"total_tokens":1480,"prompt_tokens":927,"num_sources_used":0,"completion_tokens":104,"cost_in_usd_ticks":47880000,"prompt_tokens_details":{"text_tokens":927,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":449,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":927,"tokens_out":104,"duration_ms":4622,"temperature":1.0,"reasoning_tokens":449,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-13T00:42:13.065858+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Either exhibit, for infinitely many $d$, an $n$-vertex graph of VC-dimension $d$ whose largest clique or independent set has size smaller than $n^{(C d)^{-d}}$ for every fixed $C$, or show that every such graph already contains a homogeneous set larger than $n$ to a power better than $1/d$, matching the random-graph upper bound of order $1/d$ given in the paper.","supporting_citations":[],"review_version":1}