{"id":"d276f02f-43c3-4b0d-b8a7-38eac3d12e60","arxiv_id":"2506.19493","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper improves the known inclusion between k-local words and (k+1)-representable graphs, but its proof of bounded clique-width for L_k fails on a concrete counterexample.","lead":"This paper links two ideas: words that can be marked with few blocks, and graphs that such words draw. It proves the inclusion L_k ⊆ R_{k+1} cleanly, but the central clique-width argument contains a false step, so the main structural claims are not established.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's REJECT rests entirely on the claim that Lemma 27's label is too coarse because x and y share label (1,1,0) in w_3 but behave differently with a. That comparison is made at the wrong stage: the eta operation is performed before labels are updated from w_2 to w_3, and at w_2 the two letters have different labels. Once this is corrected, the induction step is coherent: per-block occurrence counts in the old marked word determine alternation with the newly marked letter, because the new letter is unmarked in the old word and therefore occurs only outside the old blocks. Label 2 letters never alternate with the new letter, so the special label does not create false edges either. I checked the relabeling for block merges and insertions; the acyclicity argument provides a valid order for the renames. Consequently I find no load-bearing defect in the clique-width bound, the factorial-layer upper bound, or the strict inclusion L_k subset R_{k+1}, and the reader's reason for rejection is not supported.","tokens_in":11025,"tokens_out":35472,"duration_ms":355900,"concrete_test":"Recompute the construction of Lemma 27 for w = a x y b y a x with marking sequence (x,y,a,b) and k=3. Check that before adding a the labels are label^3_{w_2}(x)=(1,0,1) and label^3_{w_2}(y)=(1,1,0), so the eta step connects a only to x; then verify that the final expression represents G(u_3) with exactly the single edge {a,x}. This settles whether the proposed counterexample actually violates Lemma 27.","verdict_should_be":"ACCEPT","load_bearing_attack":"The reader's counterexample to Lemma 27 does not land. The eta-step in Lemma 27 uses the labels of the existing expression E, whose invariant is label^k_{w_{i-1}}(v), not label^k_{w_i}(v). In the proposed word w = a x y b y a x with s=(x,y,a,b), at stage i=3 the relevant old-stage labels are label^k_{w_2}(x)=(1,0,1) and label^k_{w_2}(y)=(1,1,0), which are distinct. The operation eta therefore connects a only to the label (1,0,1), i.e. to x, and the subsequent renames (1,0,1)->(1,1,0), (1,1,0)->(1,1,0), N->(1,1,0) only relabel nodes without adding false edges. The general principle is also sound: if two old letters have the same label in w_{i-1}, they have the same number of occurrences in each marked block; since the newly marked letter is unmarked in w_{i-1}, its occurrences lie only in the gaps between blocks, and the alternation pattern with that letter is fully determined by those per-block counts. If the common label is 2, neither letter alternates with the new letter, so the special label does not create false edges either. Theorems 28, 31, and 32 therefore retain their support.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the class L_k of graphs representable by k-local words and compares it with the class R_k of k-representable graphs. The main results are: Theorem 11, L_k ⊆ R_{k+1}; Theorem 16, L_1 is exactly the class of threshold graphs; index and entropy results for R_k and L_k; Theorem 25 and Corollary 31 placing L_k in the factorial layer for k > 1; and Theorem 28, a clique-width bound cwd(G) ≤ 2^k + 1 for G ∈ L_k, which is used in Theorem 32 to prove L_k ⊊ R_{k+1}. The technical engine is Lemma 27, a constructive induction that maintains a k-expression whose labels record the per-block occurrence counts of the marked word at each stage.","tokens_in":11221,"tokens_out":49866,"duration_ms":518102,"significance":"If correct, the clique-width bound is the main technical contribution: it connects the word-combinatorial notion of locality with a central graph parameter, yields the factorial-layer statement for L_k, and gives the strict separation L_k ⊊ R_{k+1}. The construction in Lemma 27 is explicit and self-contained in spirit, and the inclusion L_k ⊆ R_{k+1} via Lemma 7 is elegant. A notable strength is that the paper gives a direct inductive construction of a k-expression rather than relying on heavy external machinery. I also verified that the counterexample proposed in the stress-test note does not land: Lemma 27 compares labels at stage i-1, where in the example w = a x y b y a x the letters x and y have distinct labels (1,0,1) and (1,1,0) respectively. However, the proof of the key lemma is compressed in places and needs to be written out more rigorously.","major_comments":[{"comment":"The sentence \"for each letter alternating with a, every letter with the same label also alternates with a\" is the crux of the induction but is not proved. The claim is true, but the proof must explain that all occurrences of old letters lie inside marked blocks, all occurrences of the newly marked letter a lie in gaps, and a letter with label 2 can never alternate with a. Alternation with a is then determined by the set of blocks containing the letter together with the positions of a in the gaps, which is exactly what the label records. Please add this argument.","section":"Lemma 27"},{"comment":"The rule for inserting a new block, which drops the last tuple component, is only valid because a new block can arise only when the previous stage had fewer than k blocks, so the dropped component is zero for every old letter. This should be stated explicitly; otherwise the formula appears to lose information. The same point applies when several new blocks are inserted.","section":"Lemma 27, new-block insertion"},{"comment":"The proof of Theorem 16 is not a proof: the sentence \"The definition of threshold graphs and 1-local representable graphs is the same\" is confusing and potentially circular in view of Definition 15, which defines threshold graphs constructively. If this result is already proved in [18], cite the precise theorem and state the result; otherwise give a direct derivation that L_1 equals the threshold graphs.","section":"Theorem 16"},{"comment":"The absorbing convention that label 2 discards all tuple information is intentional, but the paper should explain why this loss is harmless for the induction: once a letter has two occurrences in a single block, it can never alternate with any letter marked later, and merging blocks can only increase occurrence counts. Without this explanation, the rule \"2 is not renamed\" looks arbitrary rather than forced by the semantics of the label.","section":"Definition 26 / Lemma 27"}],"minor_comments":[{"comment":"There are several typographical errors: \"the graphs in this classes\" in the abstract, and \"theclassesL k areageneralisationofthemmotivating\" in the introduction. These should be corrected.","section":"Abstract and Introduction"},{"comment":"The formula for the representation number of the crown graph is garbled in the text: \"⌈k+ 3 2⌉\" should presumably read \\lceil(2k+3)/2\\rceil = k+2. Please fix the typesetting.","section":"Theorem 20"},{"comment":"The text refers to the forbidden induced subgraphs shown in Figure 2, but the figure content is not visible in the manuscript text; ensure the figure is included and clearly labeled.","section":"Figure 2"},{"comment":"The notation in the proof of Lemma 24 conflicts with the earlier notation w_i for marked versions of a word. The marking sequence should be denoted by a different symbol, for example s, to avoid ambiguity.","section":"Lemma 24"},{"comment":"The worked example for the word banana is useful but terse. Expanding it with the intermediate labels at each stage would help the reader verify the renaming steps, especially the treatment of label 2.","section":"Example after Theorem 28"}],"recommendation":"major_revision","confidential_remarks":"The reader's main objection, the alleged counterexample to Lemma 27, does not hold: the comparison in that example is made at the wrong stage of the marking sequence. The central clique-width argument is plausible and likely correct. I recommend major revision mainly because the proof of the key lemma is under-specified in its crucial alternation claim and in the new-block insertion rule, and because Theorem 16 currently has no real proof. The citation to [18] for Theorem 16 should also be checked carefully for overlap and for the exact statement being cited."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe reader's rejection is too harsh. The central counterexample to Lemma 27 does not land: it uses labels from w_i, but the induction invariant is labels from w_{i-1}. For w = a x y b y a x with s=(x,y,a,b), at step i=3, x and y share the same label in w_3 but have distinct old labels (1,0,1) and (1,1,0) in w_2, so the eta step connects a only to x, as it should. The underlying principle is sound: the newly marked letter lies in gaps between blocks of the old marked word, and two letters with identical per-block counts have identical projections with that letter. The special label 2 also forces non-alternation, since two copies in one block cannot alternate with any letter outside that block. So Lemma 27, and the theorems built on it, are not refuted by this example.\n\nWhat is genuinely new and good: Theorem 11 gives a clean inclusion L_k ⊆ R_{k+1}, improving the previous R_{2k} bound; the argument that letters with more than k+1 occurrences are isolated is simple and self-contained. The clique-width bound cwd(G) ≤ 2^k+1 is the most substantial contribution, and it has real consequences: bounded clique-width for L_k, membership in the factorial layer, and the strict inclusion L_k ⊊ R_{k+1} via unbounded clique-width of circle graphs. The Bell-number lower bound is a neat construction.\n\nThe soft spots are presentation-level rather than mathematical. Theorem 16 is not proved; it cites the authors' own [18] and claims the definitions of threshold graphs and 1-local representable graphs are \"the same,\" which is sloppy. A referee should ask for an actual derivation or a clear statement that it is a prior result. Lemma 27's proof is terse, especially the label-renaming step with block merges and insertions; the acyclicity of the rename graph needs a more careful write-up. These are fixable.\n\nThis paper deserves a serious referee. The inclusion and the lower bound are solid; the clique-width theorem is worth checking carefully. I'd recommend send to review, with requests to expand Lemma 27 and repair Theorem 16.\n\nBest.","headline":"The reader's rejection is too harsh; the Lemma 27 counterexample misreads the induction invariant, and the paper's main results appear sound.","tokens_in":11825,"tokens_out":16924,"would_cite":true,"duration_ms":157006,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C62","68R15","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every graph represented by a $k$-local word has clique-width at most $2^k+1$, placing $L_k$ strictly inside $R_{k+1}$.","keywords":["word-representable graphs","k-local words","clique-width","threshold graphs","factorial layer","hereditary graph classes","Bell number","circle graphs"],"falsifier":"Take the 3-local word $a x y b y a x$ with marking sequence $(x,y,a,b)$. At the third stage the letters $x$ and $y$ have the same block-occurrence label $(1,1,0)$, yet the projection onto $a,x$ is $a x a x$, which alternates, while the projection onto $a,y$ is $a y y a$, which does not; this directly contradicts Lemma 27, the step on which the clique-width bound rests.","tokens_in":10769,"feed_emoji":"🧩","tokens_out":11738,"duration_ms":106825,"temperature":0.7,"pith_summary":"This paper connects the parsing complexity of words—their locality—to the structural complexity of the graphs the words represent. It claims that every graph represented by a $k$-local word is $(k+1)$-representable, and that the inclusion is strict: $L_k \\subsetneq R_{k+1}$ for every $k \\in \\mathbb{N}$. It also identifies $L_1$ with threshold graphs, proves that $L_k$ lies in the factorial layer for $k > 1$, and bounds the clique-width of every graph in $L_k$ by $2^k+1$. If these results hold, word locality becomes a useful structural restriction: graphs arising from local words inherit algorithmic tractability and are separated from the larger class of $(k+1)$-representable graphs.","feed_headline":"Word locality caps graph complexity at 2^k+1","feed_subtitle":"Bounded clique-width makes these graphs algorithmically tractable and separates L_k from R_{k+1}.","key_machinery":"The load-bearing device is the marking process that defines $k$-locality together with the label function $\\mathrm{label}^k_m$, which records, for each letter, which marked blocks of the current marked word contain one occurrence (with a special value $2$ when a block contains two or more occurrences). Lemma 27 claims that this label can be maintained by a $\\Sigma_k$-expression as letters are marked one by one: new edges to the freshly marked letter are added according to labels, and labels are updated when blocks merge or new blocks appear. This induction is what yields the clique-width bound $|\\Sigma_k| = 2^k+1$.","core_discovery":"The paper's central claim is that locality of a representing word is a structural constraint on the represented graph, not just a property of the word. Concretely, it proves $L_k \\subseteq R_{k+1}$ and then, using the clique-width bound $\\mathrm{cwd}(G) \\le 2^k+1$ for $G \\in L_k$, derives $L_k \\subsetneq R_{k+1}$: since $2$-representable graphs are exactly circle graphs and circle graphs have unbounded clique-width, the bounded clique-width of $L_k$ forces the inclusion to be proper. Along the way the paper shows that $L_1$ is exactly the class of threshold graphs and that $L_k$ has factorial speed for $k>1$, placing these classes in the factorial layer.","pith_inferences":["The correctness of the separation $L_k \\subsetneq R_{k+1}$ currently rests on the clique-width bound; if the labelling induction has a flaw, a revised proof would need a different invariant to keep the strictness argument alive.","If the bound survives in corrected form, locality would give a new bridge between pattern-matching complexity and graph parameters, complementing the known connections between locality, pathwidth, and cutwidth.","A natural testable extension is to compute the maximum clique-width of graphs representable by $k$-local words on small alphabets exhaustively, to see whether $2^k+1$ is tight."],"forward_implications":["$L_k \\subseteq R_{k+1}$ for every $k$, and since $R_{k+1}$ contains circle graphs with unbounded clique-width, the containment is proper.","Graphs in $L_k$ have clique-width at most $2^k+1$, so NP-hard problems such as Hamiltonian path and minimum maximal matching are polynomial-time solvable on this class whenever a suitable expression can be constructed.","$L_k$ is hereditary and lies in the factorial layer for $k>1$; $L_1$ is exactly the threshold graphs, characterized by the forbidden induced subgraphs $P_4$, $C_4$, and $2K_2$.","The separation $L_k \\subsetneq R_{k+1}$ shows that $k$-locality is a strictly stronger restriction than $(k+1)$-representability."],"supporting_citations":[{"why":"Introduces locality and the marking-sequence and block formalism that defines the class $L_k$.","marker":"[13]"},{"why":"Previous work relating representability and locality; it supplies the prior inclusion and the starting characterization of 1-local representable graphs reused for $L_1$.","marker":"[18]"},{"why":"Foundational definition of word-representable graphs and $k$-representability, including the fact that circle graphs are exactly the 2-representable graphs.","marker":"[26]"},{"why":"Shows circle graphs have unbounded clique-width, the contrast used to make the inclusion $L_k \\subsetneq R_{k+1}$ strict.","marker":"[21]"},{"why":"Gives the bound on the speed of hereditary classes with bounded clique-width, used to place $L_k$ in the factorial layer.","marker":"[2]"},{"why":"Gives representation numbers of crown graphs, used to rule out $E_{2,0}$ and compute the index of $R_{k+1}$ and $L_k$.","marker":"[20]"},{"why":"Provides non-word-representable graphs in $E_{0,2}$ and $E_{1,1}$, used in the index argument.","marker":"[27]"},{"why":"Supplies the forbidden induced subgraph characterization of threshold graphs used for $L_1$.","marker":"[30]"}],"fun_headline_variants":["Word locality bounds graph clique-width and growth","Local words cap clique-width, keep graphs in factorial layer","Locality separates graph classes via clique-width bound","Word locality yields proper subclasses with bounded width"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole proof of bounded clique-width rests on the premise that two letters with the same pattern of block occurrences will always alternate with a newly marked letter in the same way; if that pattern can coincide while the alternation differs, the induction step collapses.","fun_headline_variants_meta":{"raw":{"variants":["Word locality bounds graph clique-width and growth","Local words cap clique-width, keep graphs in factorial layer","Locality separates graph classes via clique-width bound","Word locality yields proper subclasses with bounded width"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000864,"raw_usage":{"total_tokens":3673,"prompt_tokens":795,"completion_tokens":2878,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":411,"completion_tokens_details":{"reasoning_tokens":2818}},"tokens_in":411,"tokens_out":2878,"duration_ms":22138,"temperature":1.0,"reasoning_tokens":2818,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:35:32.166164+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the 3-local word $a x y b y a x$ with marking sequence $(x,y,a,b)$. At the third stage the letters $x$ and $y$ have the same block-occurrence label $(1,1,0)$, yet the projection onto $a,x$ is $a x a x$, which alternates, while the projection onto $a,y$ is $a y y a$, which does not; this directly contradicts Lemma 27, the step on which the clique-width bound rests.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces locality and the marking-sequence and block formalism that defines the class $L_k$."},{"cited_title":"Fleischmann, L","cited_arxiv_id":null,"evidence_quote":"Previous work relating representability and locality; it supplies the prior inclusion and the starting characterization of 1-local representable graphs reused for $L_1$."},{"cited_title":"Kitaev and A","cited_arxiv_id":null,"evidence_quote":"Foundational definition of word-representable graphs and $k$-representability, including the fact that circle graphs are exactly the 2-representable graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows circle graphs have unbounded clique-width, the contrast used to make the inclusion $L_k \\subsetneq R_{k+1}$ strict."},{"cited_title":"Allen, V","cited_arxiv_id":null,"evidence_quote":"Gives the bound on the speed of hereditary classes with bounded clique-width, used to place $L_k$ in the factorial layer."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives representation numbers of crown graphs, used to rule out $E_{2,0}$ and compute the index of $R_{k+1}$ and $L_k$."},{"cited_title":"Kitaev and H","cited_arxiv_id":null,"evidence_quote":"Provides non-word-representable graphs in $E_{0,2}$ and $E_{1,1}$, used in the index argument."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the forbidden induced subgraph characterization of threshold graphs used for $L_1$."}],"review_version":2}