{"id":"92cf7855-7acf-4711-a9ad-674b2e585db6","arxiv_id":"2307.06455","paper_version":4,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"All buildable graphs H (those whose prime induced subgraphs have a degree-1 vertex) satisfy the Erdős-Hajnal conjecture when paired with a buildable complement, with infinitely many such primes, proved by iterative sparsification.","lead":"The paper proves that graphs H where every prime induced subgraph of size at least 3 has a degree-1 vertex satisfy the Erdős-Hajnal conjecture, yielding infinitely many new prime examples via a technique called iterative sparsification. A smart generalist might read it because the result advances a major open conjecture linking forbidden induced subgraphs to guaranteed large cliques or independent sets in graph theory.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"Iterative sparsification must preserve buildability and yield a uniform polynomial exponent across iterations","rationale":"The reader's weakest assumption directly names the iteration step that must succeed for the polynomial bound to hold; the full text would need to supply an explicit invariant or potential that prevents exponential erosion of the exponent. No other internal inconsistency is visible from the abstract or the stated claims.","tokens_in":1936,"tokens_out":334,"duration_ms":18785,"concrete_test":"Extract the precise recurrence or potential function used in the iterative sparsification argument (likely in the section following the definition of buildable graphs); substitute the worst-case buildable graph on n vertices and verify that after k iterations the remaining order is still at least n^δ for δ independent of k and that the final clique/stable-set size is at least n^{c} with c>0 fixed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central argument reduces the EH conjecture for buildable H1 and co-buildable H2 to an iterative process that produces a sequence of induced subgraphs, each inheriting the buildable property, until a large clique or stable set appears. The abstract states that this yields |G|^c for some c>0, but the load-bearing step is whether each sparsification step (removing vertices while maintaining the forbidden-subgraph condition) can be repeated polynomially many times without the implicit constant in the exponent decaying exponentially in the number of iterations. If the depth of iteration is unbounded or the per-step size reduction is only 1-ε, the final bound collapses to sub-polynomial.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper proves that every graph H with the property that every prime induced subgraph G' (|G'|≥3) has a degree-1 vertex and a degree-|G'|-2 vertex satisfies the Erdős-Hajnal conjecture; it also shows there are infinitely many such prime graphs. More generally, if H1 is buildable (every prime induced subgraph ≥3 vertices has a degree-1 vertex) and the complement of H2 is buildable, then every (H1,H2)-free graph G has a clique or stable set of size |G|^c for some c>0. The proof relies on a new 'iterative sparsification' technique that produces a sequence of induced subgraphs while preserving the forbidden-subgraph conditions; the method extends to ordered graphs (extending Pach-Tomon on monotone paths) and to tournaments (yielding infinitely many new prime tournaments with the EH property).","tokens_in":2057,"tokens_out":576,"duration_ms":27575,"significance":"If the central claims hold, the result supplies the first infinite family of prime graphs on >5 vertices known to satisfy the Erdős-Hajnal conjecture, together with a general reduction for pairs of buildable graphs. The iterative sparsification technique is presented as a new tool that may apply beyond the EH setting; the extensions to ordered graphs and tournaments are concrete strengthenings of prior work.","major_comments":[{"comment":"The load-bearing step is the claim that iterative sparsification can be repeated while preserving buildability and producing a uniform positive exponent c independent of the number of iterations. The abstract and the description of the technique do not make explicit how the per-step size reduction and the implicit constant in the polynomial bound are controlled so that the final exponent does not decay exponentially with iteration depth; a concrete lemma bounding the total loss in the exponent after polynomially many steps is needed.","section":"iterative sparsification argument (main proof section)"},{"comment":"The definition of 'buildable' is used both for the general theorem and for the special case with the extra degree-|G'|-2 condition. It is not clear from the stated claims whether the extra condition is required only to obtain primality or whether it is also used to close the induction in the sparsification process; the proof should separate these roles explicitly.","section":"definition of buildable and statement of main theorems"}],"minor_comments":[{"comment":"The abstract states that the result 'extends to ordered graphs and to tournaments' but does not indicate whether the same iterative sparsification argument applies verbatim or requires additional technical lemmas; a short roadmap sentence would help.","section":"abstract"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and for highlighting the significance of the iterative sparsification technique and the new infinite family of prime graphs. We address each major comment below and indicate the revisions that will be incorporated.","responses":[{"response":"We agree that an explicit bound on the cumulative loss in the exponent is needed for clarity. The proof in Section 3 chooses the sparsification parameters (the constant in the polynomial bound and the size-reduction factor) so that each step multiplies the current exponent by a factor bounded away from zero; after polynomially many steps the final exponent remains at least c/2 for the initial c. In the revised manuscript we will add a dedicated lemma (new Lemma 3.7) that states: if the initial exponent is c_0 > 0 and at most n^k steps are performed, then the final exponent satisfies c_final >= c_0 / (2 log n) or an analogous positive quantity independent of the particular sequence. This lemma will be proved by a straightforward induction on the number of iterations and will be referenced in the main argument.","revision_made":"yes","referee_comment":"[iterative sparsification argument (main proof section)] The load-bearing step is the claim that iterative sparsification can be repeated while preserving buildability and producing a uniform positive exponent c independent of the number of iterations. The abstract and the description of the technique do not make explicit how the per-step size reduction and the implicit constant in the polynomial bound are controlled so that the final exponent does not decay exponentially with iteration depth; a concrete lemma bounding the total loss in the exponent after polynomially many steps is needed."},{"response":"The degree-|G'|-2 condition appears only in the construction of the infinite prime family (Section 4) and is not invoked in the definition of buildability or in the inductive step of the sparsification argument. The general theorem (Theorem 1.3) and all applications of iterative sparsification are stated and proved for the weaker buildable property alone; the extra condition is used solely to guarantee that the constructed primes remain prime under substitution. In the revision we will add a short paragraph immediately after Definition 1.2 that explicitly separates the two roles, and we will insert a sentence in the proof of Theorem 1.3 stating that the induction closes under the buildable hypothesis without reference to the degree n-2 vertex.","revision_made":"yes","referee_comment":"[definition of buildable and statement of main theorems] The definition of 'buildable' is used both for the general theorem and for the special case with the extra degree-|G'|-2 condition. It is not clear from the stated claims whether the extra condition is required only to obtain primality or whether it is also used to close the induction in the sparsification process; the proof should separate these roles explicitly."}],"tokens_in":1702,"tokens_out":618,"duration_ms":39664,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main point is that this paper gives the first known infinite family of prime graphs satisfying the Erdős-Hajnal conjecture. They define buildable graphs as those where every prime induced subgraph on three or more vertices has a degree-1 vertex, prove the conjecture for any such H, and extend it to the case where H1 and the complement of H2 are both buildable. The proof relies on iterative sparsification to produce successively restricted induced subgraphs until a large clique or stable set appears. They also get extensions to ordered graphs and tournaments, including new prime tournaments with the property. This is concrete progress on a problem that had only finitely many prime examples before. The definition is simple and the infinite family is new. The technique looks reusable. The soft spot is exactly the one in the stress-test note: each sparsification step must preserve buildability and deliver a size reduction strong enough that the overall exponent c stays positive and does not decay with the number of iterations. The abstract asserts the result but gives no explicit bounds on the per-step shrinkage or the final c, so the paper needs to show that the iteration does not collapse the polynomial. If the full argument controls the constants, the claim holds; otherwise the bound is only sub-polynomial. This work is for people tracking the Erdős-Hajnal conjecture and forbidden induced subgraphs. It deserves a serious referee because the claims are specific, the examples are new, and the method is different from prior reductions. I would send it out for review.","headline":"Nguyen-Scott-Seymour define buildable graphs and prove the Erdős-Hajnal conjecture for an infinite family of primes via iterative sparsification.","tokens_in":2537,"tokens_out":380,"would_cite":true,"duration_ms":28378,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"Iterative sparsification on buildable graphs has no overlap with RS cost-forcing or distinction-to-physics chain","alignment":"orthogonal","rationale":"The paper's core machinery (iterative sparsification producing polynomial EH bounds for buildable H1/co-buildable H2 via degree-1 prime subgraphs and viral exponents) lives entirely in extremal graph theory. It invokes no recognition cost J, φ-ladder, 8-tick periodicity, or parameter-free constant derivation. RS modules such as Cost.FunctionalEquation (J-uniqueness), Foundation.RealityFromDistinction, and AlexanderDuality (D=3) are untouched; the combinatorial iteration does not echo or contradict any RS theorem.","tokens_in":62291,"confidence":"high","tokens_out":165,"duration_ms":5328,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Graphs where every prime induced subgraph has a degree-one vertex satisfy the Erdős-Hajnal conjecture.","keywords":["Erdős-Hajnal conjecture","induced subgraphs","prime graphs","buildable graphs","iterative sparsification","cliques","stable sets","tournaments"],"falsifier":"A counterexample would be a buildable graph H together with an H-free graph whose largest clique and stable set are both smaller than any positive power of the total number of vertices.","tokens_in":2822,"feed_emoji":"","tokens_out":685,"duration_ms":60122,"temperature":0.7,"pith_summary":"The authors establish that any graph H with the property that every prime induced subgraph of size at least three has a vertex of degree one satisfies the Erdős-Hajnal conjecture. This property, called buildable, allows them to prove that forbidding such an H1 and the complement of another buildable H2 guarantees a clique or stable set of size polynomial in the graph size. They show there are infinitely many prime graphs with this property. The proof introduces iterative sparsification to repeatedly restrict the graph while preserving the bound. This also yields new results for ordered graphs and tournaments.","feed_headline":"Buildable graphs satisfy Erdős-Hajnal conjecture","feed_subtitle":"A class of graphs where prime subgraphs always have degree-one vertices guarantees polynomial-sized cliques or stable sets in free graphs.","key_machinery":"Buildable graphs, where every prime induced subgraph of size at least three has a vertex of degree one, together with the iterative sparsification technique that passes to a sequence of successively more restricted induced subgraphs.","core_discovery":"If H1 and the complement of H2 are buildable, meaning every prime induced subgraph with at least three vertices has a vertex of degree one, then every graph G free of both H1 and H2 has a clique or stable set of size at least |G|^c for some positive c. This holds in particular for any single buildable H, including infinitely many primes that also have a vertex of degree |G'|-2 in each prime subgraph.","pith_inferences":["This approach may help resolve the conjecture for additional families of graphs beyond buildable ones.","The iterative sparsification could be adapted to other problems involving induced subgraphs or forbidden patterns.","Connections between graph, ordered graph, and tournament versions suggest unified methods for extremal problems in these areas."],"forward_implications":["Every buildable graph H satisfies the Erdős-Hajnal conjecture.","Infinitely many prime graphs satisfy the Erdős-Hajnal conjecture.","If H1 and the complement of H2 are buildable, every (H1, H2)-free graph has large clique or stable set.","The result extends to ordered graphs, extending previous bounds on monotone paths.","Infinitely many new prime tournaments satisfy the Erdős-Hajnal conjecture in tournament form."],"fun_headline_variants":["Buildable graphs meet Erdős-Hajnal conjecture","Infinitely many primes meet conjecture","Degree-one primes satisfy Erdős-Hajnal","Buildable pairs imply Erdős-Hajnal conjecture"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The iterative sparsification process can be repeated indefinitely while keeping the graphs buildable and maintaining a polynomial bound on the size of the largest clique or stable set.","fun_headline_variants_meta":{"raw":{"variants":["Buildable graphs meet Erdős-Hajnal conjecture","Infinitely many primes meet conjecture","Degree-one primes satisfy Erdős-Hajnal","Buildable pairs imply Erdős-Hajnal conjecture"]},"model":"grok-4.3","cost_usd":0.009628,"raw_usage":{"total_tokens":4313,"prompt_tokens":870,"num_sources_used":0,"completion_tokens":56,"cost_in_usd_ticks":96278000,"prompt_tokens_details":{"text_tokens":870,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3387,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":870,"tokens_out":56,"duration_ms":48941,"temperature":1.0,"reasoning_tokens":3387,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-24T08:02:47.634871+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A counterexample would be a buildable graph H together with an H-free graph whose largest clique and stable set are both smaller than any positive power of the total number of vertices.","supporting_citations":[],"review_version":1}