REVIEW 3 major objections 5 minor 9 references
Enumeration and Extensions of Word-representants
T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Shortest words that encode trees and cycles now have exact counts
desk verdict Genuinely new enumeration results and a natural t-representability extension, but the proofs have several fixable gaps — worth reviewing, not yet vetted. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central encoding mechanism is that two letters $x$ and $y$ form an edge exactly when the subword they induce avoids the pattern $11$; writing this pattern condition as the definition of adjacency lets the paper vary the pattern. For the enumeration, the load-bearing structure is a structural lemma (Lemma 2.8) saying that in any minimal representant of a tree, the two singly occurring vertices $x$ and $y$ split the word into two consecutive blocks, one from each side of the edge $xy$. Counting then proceeds by a breadth-first insertion argument (Claim 2.14): at each stage the neighbors of a vertex $z$ are inserted around the two copies of $z$, with $\deg(z)!$ legal ways to place them, and multiplying these factorial choices over all vertices yields the product in the formula.
What would settle it
Enumerate, for a small tree such as the double-star with two adjacent degree-$3$ vertices, every word of length $2n-2$ whose alternation pattern gives exactly the tree's edges, and compare the total with $2\prod_v \deg(v)! \sum_{xy\in E} 1/(\deg(x)\deg(y))$; a mismatch would show the independence assumption in Claim 2.14 fails.
Extended reading notes
Core claim
For a tree $T$ with at least two vertices, the paper proves that every minimal length word-representant has length $2n-2$, and that the number of such representants is $$n(T) = 2 \prod_{v\in V} \deg(v)! \sum_{xy\in E} \frac{1}{\deg(x)\deg(y)}.$$ For a cycle $C_n$ with $n\ge 3$, it proves $\ell(C_n)=2n-2$ for $n\ge4$ (with $\ell(C_3)=3$) and $n(C_n)=2n$. The same machinery also gives the path count $n(P_k)=(k+1)2^{k-3}$ for $k\ge3$. In the second half, the paper defines $t$-representability for any two-letter pattern $t$, shows that every graph is $t$-representable when $t$ has the form $a^k b^l a$, when $t=a^k b^l$ with $k,l\ge2$, and when $t=a^k b$ with $k\ge3$, and leaves the case $a^2b$ (equivalently $ab^2$) open.
Load-bearing premise
The tree-counting formula multiplies the factorial choices made in different branches of the tree, assuming those insertion decisions never interfere with each other; if inserting vertices in one branch can force a different order in another branch, the product formula overcounts.
Editorial extensions
If this is right
- Every tree and every cycle on $n$ vertices has a word-representant of length $2n-2$, and no shorter word can encode it; the paper proves both by explicit construction and a triangle-free lower bound.
- The number of shortest representants of a tree is determined entirely by its degree sequence through the formula $2\prod_v \deg(v)! \sum_{xy\in E} 1/(\deg(x)\deg(y))$; for paths this specializes to $(k+1)2^{k-3}$.
- For the patterns the paper handles, pattern avoidance on two letters encodes every graph, so this encoding language is much broader than alternation alone.
- The cycle count $n(C_n)=2n$ sits alongside the previously known count of $4n$ for $2$-uniform representants, showing that relaxing uniformity changes the minimal representant count in a controlled way.
- The open case $a^2b$ is the only two-letter pattern, up to reversal, for which the representable graphs are not yet characterized.
Reading between the lines
- The same breadth-first insertion method may extend from trees to unicyclic graphs, where the cycle would contribute a correction term; a direct test is to derive a formula for $n(G)$ on graphs with exactly one cycle and compare it with brute-force enumeration on small cases.
- The unresolved $a^2b$ case is likely to have a nontrivial boundary rather than universal representability, since the paper's constructions for the other patterns all rely on being able to insert a long block of a repeated letter without creating forbidden subwords.
- The identity $n(P_k)=(k+1)2^{k-3}$ matching an existing integer sequence suggests a bijective explanation may exist between minimal path representants and other counted objects, but the paper only poses this as an open problem.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies two aspects of word-representable graphs. In Section 2 the authors define ℓ(G) and n(G) as the length and number of minimal-length word-representants, prove that every tree T on n vertices satisfies ℓ(T)=2n−2, and give the closed formula n(T)=2∏_{v} deg(v)! ∑_{xy∈E} 1/(deg(x)deg(y)). For cycles they prove ℓ(C_n)=2n−2 for n≥4 and n(C_n)=2n for n≥3. In Section 3 they introduce t-representability, where an edge is present exactly when the induced subword avoids a two-letter pattern t, and they prove that every graph is t-representable for patterns of the forms a^k b^l a, a^k b^l with k,l≥2, and a^k b with k≥3, leaving a^2 b open. The paper closes with several open problems.
Significance. The enumeration formulas for trees and cycles are natural and, if the proofs are completed, constitute the first exact counts of minimal-length (not necessarily uniform) word-representants for these families; they complement existing work on uniform representants and the 2-uniform counts for cycles recalled in Remark 2.21. The t-representability framework is a clean generalization of 11-representability, and the universality results cover all but one two-letter pattern class. The paper is written accessibly, and the small cases are checked by hand in Tables 1 and 2, which increases confidence in the stated formulas. The main weakness is that the proof of Theorem 2.13 contains a factor error in the intermediate quantities n_x and n_y, and the proof of Theorem 2.20 is too terse in its uniqueness argument; both issues are repairable.
major comments (3)
- [§2.1, Theorem 2.13 proof] The displayed formulas for n_x and n_y are incorrect and cause the derivation to contradict the theorem's own formula. After Claim 2.14 the proof states n_x=(deg(x)−1)! ∏_{u∈V(Tx,xy)} deg(u)!, but the product should be over V(Tx,xy)\ {x}; otherwise the factor deg(x)! is counted twice. For the tree in Figure 1 with edge xy=13, T_{1,13} is the two-vertex tree on {1,2}; the displayed formula gives n_x=(2−1)!·2!·1!=2, while the actual length-3 representants with 1 occurring once and 2 twice form the single word 212. Removing the factor deg(1)! gives the correct value, and the corrected expressions reduce Equation (1) exactly to the closed form in the theorem statement. The proof also needs to state the convention for ℓ of a single-vertex subtree, since for leaf components the phrase 'length ℓ(Tx,xy)+1' gives length 2 instead of the single-letter word required by Lemma 2.8.
- [§2.1, Claim 2.14 and the product formula] The transition from Claim 2.14 to the product formula assumes that insertion choices at different vertices of Tx,xy are independent. Claim 2.14 is proved only for one vertex z and its children; the sentence 'Continuing in this manner' multiplies the deg(z)! counts over all non-root vertices without showing that choices made for one branch do not change the allowed positions in another. This independence is true, because each insertion is local to an occurrence of the parent and preserves the relative order of all previously placed letters, but it is a load-bearing step and should be stated explicitly before the product is formed.
- [§2.2, Theorem 2.20] The uniqueness argument for n(C_n)=2n is not fully proved. The sentence 'otherwise both 4's will be to the right of the 2' needs a justification ruling out the alternative that one 4 lies to the left of 1; this follows from the facts that 1 must alternate with the two 4s while 2 must not alternate with them, but the proof should say so. Similarly, the inductive statement 'every successive number must have at least one instance to the right of the 2, and hence both instances to the right of the 2' is asserted without an explicit induction; as written, the proof relies on an unstated invariant about the positions of the processed vertices. I believe the claim is correct and the gaps are fillable, but the printed proof does not yet establish uniqueness.
minor comments (5)
- [§2.1, Theorem 2.6] In the proof of Theorem 2.6, after replacing one instance of b by aba, the argument that a and b alternate and that a does not alternate with any other letter uses the fact that at most two vertices occur once in the smaller tree; this should be made explicit.
- [§3, Theorem 3.10] The final sentence of the contradiction in Theorem 3.10, 'But by our construction, the opposite happens', is hard to follow; please expand the order comparison in the appended suffix.
- [§3, Theorem 3.13] The claim that appending σ(w) cannot introduce the pattern aa across the boundary deserves a one-sentence justification using the fact that w|xy is alternating when xy is an edge.
- [§2.1, Table 1] In Table 1 it would help to state explicitly that the twelve words are grouped by the choice of the leaf occurring once (u_k) and the position of u_k.
- [§2.1, conventions] The paper should mention explicitly that Lemma 2.5 and Theorem 2.6 assume the tree has at least two vertices; the single-vertex convention is otherwise needed in §2.1.
Circularity Check
No circularity: the paper's counting formulas are derived from the definitions and prior non-author results, not from their own conclusions.
full rationale
The paper is self-contained against external benchmarks. The enumeration results for trees and cycles (Theorems 2.13 and 2.20) are proved by direct structural analysis of minimal word-representants, relying on definitions from Kitaev's prior work and external results such as Theorem 1.3, none of which are authored by the present authors. There is no fitting of parameters, no renaming of a known result as a new prediction, and no uniqueness theorem imported from the authors' own prior work. The extension to t-representability in Section 3 is a new definitional framework built on Kitaev's notion, and the universality theorems are proved by explicit word-construction arguments rather than by assuming the conclusion. Even if the proof of Theorem 2.13 contains an enumerative gap or overcount concern in Claim 2.14, that would be a correctness issue, not circularity: the claimed formula is not equivalent to its input by construction. No load-bearing step in the derivation chain reduces to a self-citation or a definitional identity, so the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (3)
- standard math For two letters x,y in a word w, x and y alternate if and only if the subword w|xy avoids the pattern 11.
- domain assumption The paper uses Kitaev's theorem (Theorem 1.3) that word-representable graphs are exactly k-word-representable for some k.
- ad hoc to paper The counting argument in Theorem 2.13 assumes that the factorial insertion counts at different branches of a tree are independent and can be multiplied.
Cite this review
Pith. "Pith review of Enumeration and Extensions of Word-representants." pith.science (2026). https://pith.science/paper/UKZWHD6E
@misc{pith2026190900019,
author = {Pith},
title = {Pith review of: Enumeration and Extensions of Word-representants},
year = {2026},
howpublished = {\url{https://pith.science/paper/UKZWHD6E}},
note = {Machine review of arXiv:1909.00019}
}
abstract
Given a finite word $w$ over a finite alphabet $V$, consider the graph with vertex set $V$ and with an edge between two elements of $V$ if and only if the two elements alternate in the word $w$. Such a graph is said to be word-representable or 11-representable by the word $w$; this latter terminology arises from the phenomenon that the condition of two elements $x$ and $y$ alternating in a word $w$ is the same as the condition of the subword of $w$ induced by $x$ and $y$ avoiding the pattern 11. In this paper, we first study minimal length words which word-represent graphs, giving an explicit formula for both the length and the number of such words in the case of trees and cycles. We then extend the notion of word-representability (or 11-representability) of graphs to $t$-representability of graphs, for any pattern $t$ on two letters. We prove that every graph is $t$-representable for any pattern $t$ on two letters (except for possibly one class of $t$). Finally, we pose a few open problems for future consideration.
Figures
Reference graph
Works this paper leans on
- [1]
-
[2]
2-uniform words: cycle graphs, and an algorithm to verify specific word-representations of graphs
A. Daigavane, M. Singh, B. K. George. 2-uniform words: cycle gr aphs, and an algorithm to verify specific word-representations of graphs, arXiv preprint: https://arxiv.org/pdf/1806.04673.pdf
-
[3]
M. Halld´ orsson, S. Kitaev, and A. Pyatkin. Graphs capturing alt ernations in words, Lect. Notes Comput. Sci. 6224 (2010) 436–437. Proc. 14th Conf. on Developments in La nguage Theory, DLT 2010, London, Ontario, Canada, August 17-20, 2010
work page 2010
-
[4]
S. Kitaev. A comprehensive introduction to the theory of word- representable graphs, Lecture Notes in Comput. Sci. 10396 (2017), 36–67
work page 2017
-
[5]
S. Kitaev. Existence of u-representation of Graphs, J. Graph Theory 85 (2017) 3, 661–668
work page 2017
-
[6]
S. Kitaev and A. Pyatkin. On representable graphs, J. Autom. Lang. Comb. 13 (2008) 1, 45–54
work page 2008
- [7]
-
[8]
S. Kitaev and S. Seif. Word problem of the Perkins semigroup via dir ected acyclic graphs. Order 25 (2008) 3, 177–194
work page 2008
Show all 9 references
-
[9]
N. J. A. Sloane. The on-line encyclopedia of integer sequences, p ublished electronically at https://oeis.org/
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.