{"id":"f9b1b70b-85b8-442a-afb7-86792d91c9ac","arxiv_id":"2607.10941","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.5,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"Every monadically dependent hereditary graph class has almost-linear neighborhood complexity and n^{o(1)} radius-1 merge-width, witnessed by an efficient construction-sequence algorithm.","lead":"Monadically dependent graph classes have almost-linear neighborhood complexity and almost-bounded radius-1 merge-width. The results give the first decomposition description of these classes and an O(n^5) algorithm that builds the witnessing construction sequence from polynomial neighborhood complexity.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The central claims (Theorems 2, 4 and 5) rest on a clean inductive reduction of VC-dimension via Hamming/merge graphs and a standard packing argument (Haussler) that produces fractional twins. The only external black-box is the classical monadic-dependence \to nowhere-denseness implication for K_{t,t}-free classes, which is solidly cited and not exotic. The reader's worry about that implication is therefore not load-bearing. The O(n^5) algorithm is fully constructive and works for any graph of polynomial neighborhood complexity, giving an independent algorithmic certificate for the radius-1 statement. No hidden assumption, circularity or gap threatens the strongest claim; the verdict ACCEPT with high confidence stands.","tokens_in":24104,"tokens_out":492,"duration_ms":4042,"concrete_test":"Independently verify that the transduction T_{k,c} of Lemma 23 together with the FO definition of the positive/negative merge graphs (quantifier rank ≤ c+2) indeed yields a K_{k+1,k+1}-free bipartite graph to which Corollary 6 applies; if the resulting neighborhood-complexity bound fails to be |A|^{1+o(1)}, the induction collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest-assumption concern (that Corollary 6 might fail for exotic monadically dependent classes free of K_{t,t}) does not land. The paper correctly invokes the classical equivalence that a monadically dependent class free of some K_{t,t} is nowhere dense (Adler–Adler + Dvořák, with direct citations to [30, Lem. 35] and [25, Lem. 13.7]), and nowhere-dense classes are already known to have almost-linear neighborhood complexity. The inductive sparsification (Lemmas 19–26) then reduces the general monadic-dependence case to this base case by repeatedly lowering VC-dimension while losing only polylog factors; the terminal sparsification produces a K_{d+1,d+1}-free bipartite graph that is FO-transducible, so Corollary 6 applies. No circularity or missing case appears. The algorithmic Theorem 5 is self-contained and does not rely on monadic dependence at all.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.5","summary":"The paper proves that every monadically dependent hereditary graph class has almost-linear neighborhood complexity (Theorem 2): for G in the class and Asubseteq V(G), the number of distinct neighborhoods N(v) cap A is |A|^{1+o(1)}. From this it derives that every n-vertex graph in such a class has radius-1 merge-width n^{o(1)} (Theorem 4). The argument is algorithmic: Theorem 5 supplies an O(n^5)-time procedure that, given any n-vertex graph whose neighborhood complexity is O(|A|^d), returns a construction sequence of radius-1 width O(n^{1-1/d} log n). The neighborhood-complexity proof proceeds by induction on VC-dimension via k-sparsifications (Definition 22), Hamming/merge graphs, Haussler packing, and a reduction to the nowhere-dense base case (Corollary 6). The merge-width algorithm uses multiplicative weight updates and fractional twins (Lemmas 13-14).","tokens_in":24346,"tokens_out":753,"duration_ms":6323,"significance":"The results give the first decomposition-based structural description of monadically dependent classes and settle the radius-1 case of the Dreier-Toruńczyk conjecture linking monadic dependence to almost-bounded merge-width. Almost-linear neighborhood complexity immediately yields Welzl orderings, sparse neighborhood covers, spanners, adjacency labeling schemes, and n^{2+o(1)} APSP (Corollary 3), extending these tools beyond the previously settled regimes of nowhere denseness and monadic stability. The O(n^5) algorithm of Theorem 5 is fully explicit, self-contained, and works for any graph of polynomial neighborhood complexity; the classical packing and reweighting ingredients are used cleanly. Together the theorems supply a concrete algorithmic foothold toward FO model checking on monadically dependent classes.","major_comments":[],"minor_comments":[{"comment":"The O(n^5) bound of Theorem 5 is left unoptimized; a short remark comparing it with the near-linear signed-tree constructions known for twin-width would help the reader gauge practicality.","section":"Theorem 5 / end of Section 3"},{"comment":"Definition 22 of k-sparsification is dense; a one-sentence intuition that the functions f_j encode a FO-definable partition of controlled VC-dimension would improve readability before the inductive lemmas.","section":"Definition 22"},{"comment":"In the high-level overview (Section 2) the polylog factors lost at each of the d sparsification steps are stated only asymptotically; an explicit product of the constants from Lemmas 11-12 would make the dependence on d transparent.","section":"Section 2, after Lemma 12"},{"comment":"Figure 1 is reproduced from [16]; a brief caption sentence explaining which stages illustrate radius-1 width three would make the figure self-contained.","section":"Figure 1"}],"recommendation":"accept","confidential_remarks":"The manuscript is technically solid and the weakest-assumption concern raised by the reader (possible failure of Corollary 6 for exotic classes) does not materialize: the classical Adler-Adler/Dvořák reduction is correctly cited and the inductive sparsification reduces cleanly to that base case. I see no load-bearing gaps. Fit for a top theory venue is excellent."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper settles two concrete open questions that sit right in the middle of the FO model-checking program. Theorem 2 shows every monadically dependent class has almost-linear neighborhood complexity; Theorem 4 then gives almost-bounded radius-1 merge-width, and Theorem 5 supplies an O(n^5) algorithm that produces a witnessing construction sequence from any polynomial neighborhood-complexity bound.\n\nWhat is new is the inductive sparsification (Definition 22 and Lemmas 19–26). They start from bounded VC-dimension (which monadic dependence immediately gives), repeatedly thin the set system by one dimension while losing only polylog factors via Hamming/merge graphs and Haussler packing, then land on a terminal K_{d+1,d+1}-free bipartite graph that is FO-transducible. Corollary 6 (the classical nowhere-dense base case) finishes the job. The merge-width half is a clean multiplicative-weight argument that does not need monadic dependence at all; it works for any graph whose neighborhoods shatter at most |A|^d. The proofs are complete, the classical lemmas are cited correctly, and the algorithm is fully explicit.\n\nThe only soft spots are the usual ones for this literature: the o(1) depends non-constructively on the class, and the radius-1 restriction leaves the full Dreier–Toruńczyk conjecture open. Neither is a flaw in the argument; both are stated honestly. The stress-test concern about Corollary 6 does not land—the paper invokes the standard Adler–Adler/Dvořák equivalence and the induction reduces to it cleanly.\n\nThis is for anyone working on structural graph theory, monadic dependence, or FO model checking. The math is solid, the citations are appropriate, and the algorithmic theorem is immediately usable. I would send it to referees without hesitation.","headline":"Solid, fully proved advance: monadic dependence implies almost-linear neighborhood complexity and almost-bounded radius-1 merge-width, with an explicit O(n^5) algorithm.","tokens_in":24968,"tokens_out":477,"would_cite":true,"duration_ms":4671,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C75","68Q25","03C13"],"pacs":[],"model":"grok-4.5","headline":"Monadically dependent graph classes have almost-linear neighborhood complexity and almost-bounded radius-1 merge-width.","keywords":["monadic dependence","neighborhood complexity","merge-width","construction sequences","VC-dimension","first-order model checking","hereditary graph classes"],"falsifier":"Exhibit a hereditary monadically dependent class that contains, for arbitrarily large A, more than |A|^{1+ε} distinct neighborhoods on A for some fixed ε>0, or show that some n-vertex graph of polynomial neighborhood complexity has radius-1 merge-width ω(n^{1-1/d} log n).","tokens_in":25029,"feed_emoji":"🔗","tokens_out":681,"duration_ms":5738,"temperature":0.7,"pith_summary":"Monadic dependence is a candidate dividing line that is hoped to characterize exactly when first-order model checking is fixed-parameter tractable on hereditary graph classes. This paper proves two concrete structural consequences of that property. First, every graph from a monadically dependent class has almost-linear neighborhood complexity: for any vertex set A the number of distinct neighborhoods restricted to A is at most |A| to the power 1+o(1). Second, every n-vertex graph in such a class admits a construction sequence whose radius-1 merge-width is only n to the o(1). The second statement is obtained algorithmically: whenever neighborhoods are polynomial of degree d, an O(n^5) procedure builds a construction sequence of radius-1 width O(n^{1-1/d} log n). Together the results give the first decomposition-based description of monadically dependent classes and settle the radius-1 case of a recent conjecture linking monadic dependence to almost-bounded merge-width.","feed_headline":"Dependent graphs get almost-linear neighborhoods","feed_subtitle":"And an O(n^5) algorithm builds radius-1 construction sequences of width n^{o(1)}","key_machinery":"Inductive sparsification of bipartite graphs that repeatedly extracts a large subset whose neighborhoods have strictly smaller VC-dimension, combined with a greedy leader-merge algorithm that reweights fractional twins via Haussler’s packing lemma.","core_discovery":"Every monadically dependent hereditary graph class has almost-linear neighborhood complexity, and therefore every n-vertex graph in the class has radius-1 merge-width n^{o(1)}. Moreover, any graph whose neighborhoods are bounded by a polynomial of degree d admits, in O(n^5) time, an explicit construction sequence of radius-1 merge-width O(n^{1-1/d} log n).","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Monadic dependence yields almost-linear neighborhood complexity","Dependent graph classes force radius-1 merge-width n^{o(1)}","O(n^5) algorithm builds radius-1 sequences of width n^{1-1/d} log n","Almost-linear neighborhoods imply near-linear radius-1 merge-width","First decomposition for monadically dependent classes: merge-width n^{o(1)}"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The argument that monadic dependence forces almost-linear neighborhoods rests on the classical fact that a monadic-dependent bipartite class free of a fixed complete bipartite subgraph is already nowhere dense.","fun_headline_variants_meta":{"raw":{"variants":["Monadic dependence yields almost-linear neighborhood complexity","Dependent graph classes force radius-1 merge-width n^{o(1)}","O(n^5) algorithm builds radius-1 sequences of width n^{1-1/d} log n","Almost-linear neighborhoods imply near-linear radius-1 merge-width","First decomposition for monadically dependent classes: merge-width n^{o(1)}"]},"model":"grok-4.5","effort":"low","cost_usd":0.006164,"raw_usage":{"total_tokens":1674,"prompt_tokens":874,"num_sources_used":0,"completion_tokens":108,"cost_in_usd_ticks":61640000,"prompt_tokens_details":{"text_tokens":874,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":692,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":874,"tokens_out":108,"duration_ms":5581,"temperature":1.0,"reasoning_tokens":692,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T08:09:37.736679+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a hereditary monadically dependent class that contains, for arbitrarily large A, more than |A|^{1+ε} distinct neighborhoods on A for some fixed ε>0, or show that some n-vertex graph of polynomial neighborhood complexity has radius-1 merge-width ω(n^{1-1/d} log n).","supporting_citations":[],"review_version":1}