Pith. sign in

REVIEW 4 major objections 5 minor 33 references

Word-Representable Graphs and Locality of Words

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every graph represented by a $k$-local word has clique-width at most $2^k+1$, placing $L_k$ strictly inside $R_{k+1}$.

desk verdict The reader's rejection is too harsh; the Lemma 27 counterexample misreads the induction invariant, and the paper's main results appear sound. read the letter →

arxiv 2506.19493 v1 pith:OGPVAUKJ submitted 2025-06-24 math.CO cs.FL

Philipp Böll , Pamela Fleischmann , Annika Huch , Jana Krei{ss} , Tim Löck , Kajus Park , Max Wiedenhöft This is my paper · ORCID
classification math.COcs.FL MSC 05C6268R1505C75
keywords word-representablegraphsk-localwordsclique-widththresholdfactoriallayerhereditarygraphclassesBellnumbercircle
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • $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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [Lemma 27] 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.
  2. [Lemma 27, new-block insertion] 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.
  3. [Theorem 16] 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.
  4. [Definition 26 / Lemma 27] 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.
minor comments (5)
  1. [Abstract and Introduction] There are several typographical errors: "the graphs in this classes" in the abstract, and "theclassesL k areageneralisationofthemmotivating" in the introduction. These should be corrected.
  2. [Theorem 20] 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.
  3. [Figure 2] 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.
  4. [Lemma 24] 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.
  5. [Example after Theorem 28] 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.

Circularity Check

1 steps flagged · score 2.0 of 10

One minor self-citation supports the L1=threshold claim; the main derivation chain is otherwise self-contained.

  1. self citation load bearing [Theorem 16, Section 4]
    "In [18], the authors introduced the class of1-local representable graphs and showed that it contains exactly the graphs represented by1-local words, i.e., L1. The definition of threshold graphs and1-local representable graphs is the same."

    The proof of Theorem 16 does not derive L1=threshold graphs from the paper's own definitions of k-local words and L1. It relies entirely on a citation to [18], whose author list overlaps with the present paper, and asserts that the definition of threshold graphs and the cited class are the same. If [18] defined '1-local representable graphs' as threshold graphs, the theorem is a definitional renaming; if not, no argument is supplied. The step is not load-bearing for the main results: Theorem 11, Theorem 28, and Theorem 32 are each argued from definitions and external cited theorems rather than from this L1 characterization.

full rationale

The central derivation chain is largely self-contained. Lemma 9 and Theorem 11 prove L_k⊆R_{k+1} from the definitions of k-locality, alternation, and k-representability, with Lemma 7 providing the needed non-alternation argument. The clique-width bound in Theorem 28 is obtained by an explicit inductive construction (Lemma 27) using Σ_k-expressions, and the properness in Theorem 32 follows from external results on circle graphs and 2-representability ([21], [26]) together with the bounded clique-width bound. The factorial-layer statement combines Theorem 25 with Theorem 30, again using external and internal estimates. The only circularity-adjacent step is Theorem 16, whose proof amounts to a self-citation plus a statement that the two definitions coincide; this is a minor self-citation that does not support the paper's principal claims. The possible flaw in Lemma 27 identified by a reader concerns the correctness of the label-invariance inference, not the reduction of a prediction to its inputs, so it does not affect the circularity score. Overall the paper's main results have independent mathematical content and do not reduce to their assumptions.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No free parameters appear. The paper depends on several cited external theorems and on the self-cited characterization of L1. The most fragile premise is the ad hoc label-sufficiency claim inside Lemma 27, which is false; a concrete counterexample is w=a x y b y a x with marking sequence (x,y,a,b).

assumptions (7)
  • standard math Crown graph H_{n,n} has representation number ceil(n/2) (cited [20]).
    Used in Theorem 20 to show that E_{2,0} is not contained in R_{k+1} or L_k; if this external result is misstated, the index argument fails.
  • standard math Circle graphs are exactly the 2-representable graphs and have unbounded clique-width (cited [26], [21]).
    Used in Theorem 32 to show that R_{k+1} has unbounded clique-width and hence cannot equal L_k if the L_k clique-width bound held.
  • standard math Alekseev-Bollobás-Thomason Theorem: hereditary classes with index 1 have entropy 0 (cited [1]).
    Used in Corollary 22 to obtain the upper bound on speed for R_{k+1} and L_k.
  • standard math Allen-Lozin-Rao Theorem: a hereditary class with bounded clique-width has speed at most n! C^n (cited [2]).
    Used in Corollary 31 to place L_k in the factorial layer; this step inherits the invalidity of the clique-width proof.
  • standard math Threshold graphs are characterized by the forbidden induced subgraphs in Figure 2 (cited [30]).
    Used after Theorem 16 to give the forbidden-subgraph description of L_1.
  • domain assumption The class of 1-local representable graphs from [18] coincides with threshold graphs.
    Theorem 16's proof is literally a citation to [18]; no derivation is given in this paper, and [18] shares authors with the present work.
  • ad hoc to paper Two letters with the same label label^k_{w_i} have the same alternation behaviour with every other letter.
    This is the false premise inside Lemma 27. The 3-local word a x y b y a x with marking (x,y,a,b) gives x and y the same label (1,1,0) at stage 3, but a alternates with x and not with y.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Word-Representable Graphs and Locality of Words." pith.science (2026). https://pith.science/paper/OGPVAUKJ

@misc{pith2026250619493,
  author       = {Pith},
  title        = {Pith review of: Word-Representable Graphs and Locality of Words},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OGPVAUKJ}},
  note         = {Machine review of arXiv:2506.19493}
}
abstract

In this work, we investigate the relationship between $k$-repre\-sentable graphs and graphs representable by $k$-local words. In particular, we show that every graph representable by a $k$-local word is $(k+1)$-representable. A previous result about graphs represented by $1$-local words is revisited with new insights. Moreover, we investigate both classes of graphs w.r.t. hereditary and in particular the speed as a measure. We prove that the latter ones belong to the factorial layer and that the graphs in this classes have bounded clique-width.

Figures

Figures reproduced from arXiv: 2506.19493 by the authors.

Figure 1
Figure 1. Graph represented by the word analog. The theory of word-representable graphs was introduced by Kitaev and Pyatkin in [26] as a tool for semigroup theory, and an introduction to this theory can be found in [25]. It has applications in periodic scheduling [23,25], topology [31], and the power domination problem from physics [9], but is also important from a theoretical perspective since word-representable graphs gene… view at source ↗
Figure 2
Figure 2. Forbidden induced subgraphs of L 1 . This means that the classes L k for k ∈ N are a generalisation of the important threshold graphs, which further motivates to investigate them. However, we have not found a forbidden induced subgraph characterisation of L k for k > 1, and it is unknown if these classes are finitely defined. Another important aspect of hereditary graph classes is the asymptotic growth of their size… view at source ↗
Figure 4
Figure 4. A graph in E1,1 that is not in R (the colouring indicates a partition into a clique and an independent set). With this we can show that the indices of Rk+1 and L k are both 1 for every k ∈ N. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figures from the paper (1 more)
Figure 5
Figure 5. Figure 5: Graph with clique-width 2. Note that a graph with clique-width 1 cannot have any edges because we can only add edges between distinct labels. Therefore, this graph has a clique-width of 2. Using these definitions, we can show that L k has a bounded clique-width based o…

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 31 canonical work pages

  1. [18]

    Fleischmann, L

    P. Fleischmann, L. Haschke, T. Löck, and D. Nowotka. Word-representable graphs from a word’s perspective.Acta Informatica, 61(4):383–400, 2024

    work page 2024

  2. [1]

    V. E. Alekseev. On the entropy values of hereditary classes of graphs.Discrete Mathematics and Applications, 3(2):191–200, 1993

    work page 1993

  3. [2]

    Allen, V

    P. Allen, V. V. Lozin, and M. Rao. Clique-width and the speed of hereditary properties.Electron. J. Comb., 16(1), 2009

    work page 2009

  4. [3]

    D. Angluin. Finding patterns common to a set of strings.J. Comput. Syst. Sci., 21(1):46–62, 1980

    work page 1980

  5. [4]

    A. Atminas. Well-quasi-ordering of combinatorial structures. Unpublished doctoral dissertation, 2015

    work page 2015

  6. [5]

    Atminas, A

    A. Atminas, A. Collins, J. Foniok, and V. V. Lozin. Deciding the Bell number for hereditary graph properties.SIAM J. Discret. Math., 30(2):1015–1031, 2016

    work page 2016

  7. [6]

    C. Beth, P. Fleischmann, A. Huch, D. Kazempour, P. Kröger, A. Kulow, and M. Renz.k-local graphs.CoRR, 2024. URL:https://doi.org/10.48550/arXiv. 2410.00601

    work page Pith review arXiv doi:10.48550/arxiv.2410.00601 2024

  8. [7]

    Bollobás

    B. Bollobás. Hereditary and monotone properties of combinatorial structures. Surveys in combinatorics 2007, 346:1, 2007

    work page 2007

Show all 33 references
  1. [8]

    Casel, J

    K. Casel, J. D. Day, P. Fleischmann, T. Kociumaka, F. Manea, and M. L. Schmid. Graph and string parameters: Connections between pathwidth, cutwidth and the localitynumber. InICALP 2019,volume132ofLIPIcs,pages109:1–109:16.Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019

    2019

  2. [9]

    Chandrasekaran and A

    S. Chandrasekaran and A. Sulthana. k-Power domination of crown graph.IJAER, 14(13):3066–3068, 2019

    2019

  3. [10]

    Collins, S

    A. Collins, S. Kitaev, and V. V. Lozin. New results on word-representable graphs. Discret. Appl. Math., 216:136–141, 2017

    2017

  4. [11]

    D. G. Corneil and U. Rotics. On the relationship between clique-width and treewidth.SIAM J. Comput., 34(4):825–847, 2005

    2005

  5. [12]

    Courcelle, J

    B. Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width.Theory Comput. Syst., 33(2):125– 150, 2000

    2000

  6. [13]

    J. D. Day, P. Fleischmann, F. Manea, and D. Nowotka. Local patterns. In37th IARCS, FSTTCS 2017, volume 93 ofLIPIcs, pages 24:1–24:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017

    2017

  7. [14]

    H. N. de Ridder et al. Information System on Graph Classes and their Inclu- sions (ISGCI).https://www.graphclasses.org/classes/gc_328.html

  8. [15]

    Espelage, F

    W. Espelage, F. Gurski, and E. Wanke. How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. InGraph-Theoretic Concepts in Computer Science, 2001, volume 2204 ofLNCS, pages 117–128. Springer, 2001

    2001

  9. [16]

    M. R. Fellows, F. A. Rosamond, U. Rotics, and S. Szeider. Clique-width is NP- complete.SIAM J. Discret. Math., 23(2):909–939, 2009

    2009

  10. [17]

    Z. Feng, H. Fernau, P. Fleischmann, K. Mann, and S. C. Sacher. Generalized word- representable graphs.CoRR, abs/2411.03274, 2024. URL:https://doi.org/10. 48550/arXiv.2411.03274. 14

    2024 doi arXiv

  11. [19]

    Fleischmann, L

    P. Fleischmann, L. Haschke, F. Manea, D. Nowotka, C. T. Tsida, and J. Wieden- beck. Blocksequences of k-local words. InSOFSEM 2021, volume 12607 ofLNCS, pages 119–134. Springer, 2021

    2021

  12. [20]

    M. Glen, S. Kitaev, and A. V. Pyatkin. On the representation number of a crown graph.Discret. Appl. Math., 244:89–93, 2018

    2018

  13. [21]

    M. C. Golumbic and U. Rotics. On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci., 11(3):423–443, 2000

    2000

  14. [22]

    M. M. Halldórsson, S. Kitaev, and A. V. Pyatkin. Semi-transitive orientations and word-representable graphs.Discret. Appl. Math., 201:164–171, 2016

    2016

  15. [23]

    Halldórsson, S

    M.M. Halldórsson, S. Kitaev, and A.V. Pyatkin. Graphs capturing alternations in words. InDLT, volume 6224 ofLNCS, pages 436–437, 2010

    2010

  16. [24]

    Johansson

    O. Johansson. Clique-decomposition, NLC-decomposition, and modular decomposition-relationships and results for random graphs.Congressus Numer- antium, pages 39–60, 1998

    1998

  17. [25]

    Kitaev and V

    S. Kitaev and V. V. Lozin.Words and Graphs. Monographs in Theoretical Com- puter Science. An EATCS Series. Springer, 2015

    2015

  18. [26]

    Kitaev and A

    S. Kitaev and A. V. Pyatkin. On representable graphs.J. Autom. Lang. Comb., 13(1):45–54, 2008

    2008

  19. [27]

    Kitaev and H

    S. Kitaev and H. Sun. Human-verifiable proofs in the theory of word-representable graphs.RAIRO Theor. Informatics Appl., 58:9, 2024

    2024

  20. [28]

    D. Knop, M. Koutecký, T. Masarík, and T. Toufar. Simplified algorithmic metathe- orems beyond MSO: treewidth and neighborhood diversity.Log. Methods Comput. Sci., 15(4), 2019

    2019

  21. [29]

    Lothaire.Combinatorics on Words

    M. Lothaire.Combinatorics on Words. Cambridge Mathematical Library. Cam- bridge University Press, 1997

    1997

  22. [30]

    N. V. R. Mahadev and U. N. Peled.Threshold graphs and related topics, volume 56 ofAnnals of Discrete Mathematics. Elsevier, 1995

    1995

  23. [31]

    Oliveros and A.J

    D. Oliveros and A.J. Torres. From word-representable graphs to altered tverberg- type theorems.Discrete & Computational Geometry, pages 1–17, 2025

    2025

  24. [32]

    Oum and P

    S. Oum and P. D. Seymour. Approximating clique-width and branch-width.J. Comb. Theory B, 96(4):514–528, 2006

    2006

  25. [33]

    E. R. Scheinerman and J. S. Zito. On the size of hereditary classes of graphs.J. Comb. Theory B, 61(1):16–39, 1994. 15

    1994

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.