{"id":"e7d98a60-9da7-4dd3-b781-4d7eef038181","arxiv_id":"1909.00019","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For any tree or cycle on n vertices, the shortest representing word has length 2n-2; the number of such words has a closed formula, and a new two-letter pattern representation works for every graph except one open case.","lead":"The paper finds exact formulas for the shortest words that encode trees and cycles as word-representable graphs, and generalizes the encoding to arbitrary two-letter patterns. It proves that nearly every two-letter pattern can represent every graph, leaving one open case.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.13 proof overcounts rooted components: the displayed n_x includes an extra deg(x)! factor, contradicting direct local enumeration; branch-independence is not established.","rationale":"The reader's verdict is CONDITIONAL with moderate confidence, and my pass does not change it. The central new result is the tree enumeration formula of Theorem 2.13, and the formula itself appears correct on the paper's examples and on further small cases. However, the proof as written contains a concrete, verifiable overcount: the displayed expression for n_x includes a factor deg(x)! that is not justified by the local insertion construction, and direct local enumeration contradicts it. This is a proof-level defect, not merely a stylistic gap, but it is repair-able by replacing the product over V(T_{x,xy}) with the product over V(T_{x,xy})\\{x}, or by supplying a rigorous proof of Claim 2.14's independence. I also note that in Theorem 2.20 the sentence 'the two 4's must alternate with the two 3's without alternating with the 1 or the 2' is false for C4, since 4 is adjacent to 1 in C4; the result n(C4)=8 is nevertheless true and can be checked separately. The Section 3 representability theorems are less central to the paper's headline but also contain proof gaps, for example the step in Theorem 3.12 relying on the placement of π(w). None of this impugns the authors; these are ordinary referee corrections. The most useful next step is a small brute-force verification of the tree formula, which would cleanly separate a typographical/proof issue from a genuine failure of the independence argument.","tokens_in":13664,"tokens_out":29431,"duration_ms":287343,"concrete_test":"Run an exhaustive search over all words of length 2n-2 for all trees on at most 7 vertices, or at least for the Figure 1 tree and the 5-vertex tree with degree sequence (3,2,1,1,1), and compare the number of minimal word-representants with Theorem 2.13. In the same script, enumerate length-5 words representing the rooted star with center x occurring once and two leaves each occurring twice; check whether the count is 2 rather than the 12 predicted by the displayed n_x expression. If the full-tree counts match Theorem 2.13, the closed form is correct and only the proof's displayed n_x needs correction; if the counts differ, the branch-independence assumption in Claim 2.14 fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Theorem 2.13, after defining n_x as the number of word-representants of T_{x,xy} of length ℓ(T_{x,xy})+1, the paper states n_x = (deg(x)-1)! ∏_{u∈V(T_{x,xy})} deg(u)!. This is inconsistent with the construction preceding it. In that construction, (deg(x)-1)! choices arrange the neighbors of x, and then each non-root vertex contributes a factor deg(v)! for inserting its children; the root x should not contribute an additional deg(x)! factor. Concretely, take the tree in Figure 1 with edge xy=23, so x=2 and T_{x,xy} is the 3-vertex star centered at 2 with leaves 1 and 4. The displayed formula gives n_x = 2!·(3!·1!·1!) = 12. But enumerating words of length 5 over {1,2,4} with 2 occurring once, 1 and 4 twice, and representing this star yields only two words, namely a b x b a and b a x a b for {a,b}={1,4}, so n_x = 2. Hence Equation (1) cannot reduce to the theorem's closed form as written. The underlying gap is Claim 2.14: it multiplies insertion counts for different branches without proving that those choices are independent and cannot interfere across subtrees. The worked examples support the corrected count n_x = (deg(x)-1)! ∏_{u∈V(T_{x,xy})\\{x}} deg(u)!, but the proof as printed overcounts by a factor of deg(x)!, so the derivation does not currently establish the central enumeration formula.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13983,"tokens_out":38141,"duration_ms":333660,"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":[{"comment":"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.","section":"§2.1, Theorem 2.13 proof"},{"comment":"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.","section":"§2.1, Claim 2.14 and the product formula"},{"comment":"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.","section":"§2.2, Theorem 2.20"}],"minor_comments":[{"comment":"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.","section":"§2.1, Theorem 2.6"},{"comment":"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.","section":"§3, Theorem 3.10"},{"comment":"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.","section":"§3, Theorem 3.13"},{"comment":"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.","section":"§2.1, Table 1"},{"comment":"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.","section":"§2.1, conventions"}],"recommendation":"major_revision","confidential_remarks":"The main theorems are likely correct and the paper is worth publishing after a revision. The factor error in Theorem 2.13 is localized and fixable; the cycle proof needs a more careful write-up. I would not reject on the basis of the current gaps. The t-representability section, especially Theorems 3.10–3.12, would benefit from a second careful check of the edge-removal constructions, since the proofs are terse, but I did not find a concrete counterexample."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the two new ideas in this paper are the notion of absolute minimal length for word-representants, with explicit enumeration for trees and cycles, and the t-representability extension of Kitaev's u-representability. The results are plausible and the examples check out, but the proofs as written have real gaps that need cleaning up before I'd trust the details.\n\nThe good part first. Theorem 2.13's formula n(T) = 2 ∏ deg(v)! ∑ 1/(deg(x)deg(y)) is elegant and matches the worked tree, the star, and the path corollary. The idea of counting minimal representants by choosing the two single-occurrence vertices (which must be adjacent) and then arranging the two rooted subtrees is sound. The t-representability universality results in Section 3 are also a natural extension of Kitaev's work, and the proofs have the right general shape.\n\nNow the soft spots, in rough order of severity.\n\n1. The proof of Theorem 2.13 contains a definite algebraic slip. The displayed formula for n_x is (deg(x)-1)! ∏_{u∈V(T_{x,xy})} deg(u)!, but the derivation from the BFS construction gives (deg(x)-1)! ∏_{u≠x} deg(u)!. The printed version includes an extra deg(x)! factor. Plugging the printed n_x and n_y into equation (1) does not produce the stated n(T) — you get an extra factor deg(x)!deg(y) per edge. The corrected n_x does give the theorem. The stress-test's particular example using edge 23 in Figure 1 misreads that figure (the tree is a path, not a star), but the extra-factor point stands.\n\n2. Claim 2.14 and the surrounding BFS argument assume that insertion choices at different branches are independent — that the number of ways for one branch doesn't depend on choices made in another. That may be true, but it's not proved, and it's exactly the kind of thing that can fail. The worked examples support the product formula, but a referee should ask for a rigorous independence argument.\n\n3. The proof of Theorem 2.20 has an unjustified dichotomy: 'the 4's must be between 1 and 2' is asserted, not derived. The case analysis doesn't handle the possibility that one 4 lies before 1, which is actually necessary for n=4 where 4 and 1 are adjacent. The formula n(C_n)=2n is likely right — the construction in Theorem 2.18 checks out — but the proof needs a more careful argument, especially for C4.\n\n4. In Theorem 3.12, the line 'the c^k section cannot intersect with the i^{k-1} section' is false when c=i. A referee should patch that step; it's probably fixable.\n\nOverall, the central results are probably correct, and the paper is a real contribution to the word-representable graphs literature. The proofs are not yet vetted. I'd send it to a serious referee, with a note that the enumeration proof needs a careful rewrite of the n_x formula and the independence claim, and the cycle proof needs a rigorous case analysis. The t-representability section also needs a close look. Not a desk reject, but conditional on revision.","headline":"Genuinely new enumeration results and a natural t-representability extension, but the proofs have several fixable gaps — worth reviewing, not yet vetted.","tokens_in":14500,"tokens_out":30637,"would_cite":true,"duration_ms":251310,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C30","05C05","05C38","68R15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Shortest words that encode trees and cycles now have exact counts","keywords":["word-representable graphs","minimal length representants","pattern avoidance","trees","cycles","t-representability","enumeration","alternation"],"falsifier":"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.","tokens_in":13421,"feed_emoji":"🔠","tokens_out":7834,"duration_ms":68778,"temperature":0.7,"pith_summary":"The paper asks a basic counting question about word-representable graphs: if a graph is encoded by a word whose alternating letters mark its edges, what is the shortest such word, and how many shortest words are there? For every tree on $n$ vertices the answer is length $2n-2$, and the number of shortest representants is given by a closed formula built from vertex degrees. For every cycle the length is also $2n-2$ (with the triangle at length $3$), and the number is exactly $2n$. The paper then broadens the encoding rule from alternation, pattern $11$, to any two-letter pattern $t$, and proves that for most choices of $t$ every graph can be represented. These results give the first exact enumeration of minimal word-representants for two infinite graph families and show that alternation is one member of a larger family of graph-from-word encodings.","feed_headline":"Shortest tree and cycle word-codes counted exactly","feed_subtitle":"A degree-based formula gives the number of minimal alternation words; most two-letter patterns also encode every graph.","key_machinery":"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.","core_discovery":"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\n$$n(T) = 2 \\prod_{v\\in V} \\deg(v)! \\sum_{xy\\in E} \\frac{1}{\\deg(x)\\deg(y)}.$$\n\nFor 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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the base definition of word-representable graphs and the representation number this paper's minimal-length question refines.","marker":"[4]"},{"why":"Establishes that word-representability is equivalent to $k$-word-representability, allowing the paper to study representants without the uniformity requirement.","marker":"[6]"},{"why":"Previous work on the minimal $k$ for uniform representants, the comparison point for the paper's absolute minimal length counts.","marker":"[3]"},{"why":"Gives the $4n$ count of $2$-uniform representants of cycles that the paper contrasts with its own $n(C_n)=2n$.","marker":"[2]"},{"why":"Introduces $u$-representability using two-letter patterns; Section 3 builds on this idea while removing the vertex-order dependence.","marker":"[5]"}],"fun_headline_variants":["Minimal word-representants counted for trees and cycles","Formula gives exact count of shortest word-codes for trees and cycles","Two-letter patterns: most encode every graph, one case open","Counting minimal alternation words: trees, cycles, and paths"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Minimal word-representants counted for trees and cycles","Formula gives exact count of shortest word-codes for trees and cycles","Two-letter patterns: most encode every graph, one case open","Counting minimal alternation words: trees, cycles, and paths"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001136,"raw_usage":{"total_tokens":4749,"prompt_tokens":1008,"completion_tokens":3741,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":624,"completion_tokens_details":{"reasoning_tokens":3671}},"tokens_in":624,"tokens_out":3741,"duration_ms":24955,"temperature":1.0,"reasoning_tokens":3671,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:07:24.903434+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the base definition of word-representable graphs and the representation number this paper's minimal-length question refines."},{"cited_title":"Kitaev and A","cited_arxiv_id":null,"evidence_quote":"Establishes that word-representability is equivalent to $k$-word-representability, allowing the paper to study representants without the uniformity requirement."},{"cited_title":"Halld´ orsson, S","cited_arxiv_id":null,"evidence_quote":"Previous work on the minimal $k$ for uniform representants, the comparison point for the paper's absolute minimal length counts."},{"cited_title":"2-uniform words: cycle graphs, and an algorithm to verify specific word-representations of graphs","cited_arxiv_id":"1806.04673","evidence_quote":"Gives the $4n$ count of $2$-uniform representants of cycles that the paper contrasts with its own $n(C_n)=2n$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces $u$-representability using two-letter patterns; Section 3 builds on this idea while removing the vertex-order dependence."}],"review_version":1}