{"id":"2cbd255d-7aea-45e7-8dc8-beaf7b0a8491","arxiv_id":"2502.00872","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Word-representable split graphs have representation number at most 3, and the graphs with representation number exactly 3 are characterized by a family of induced subgraphs.","lead":"The paper proves that every word-representable split graph can be encoded by a word in which each vertex appears exactly three times. It also pinpoints which split graphs need all three copies, using a short list of forbidden subgraphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No internal gap found in the R(G) ≤ 3 proof; the load-bearing step is the cited external Theorem 3, which Algorithm 1 assumes to obtain the labeling of C.","rationale":"I traced Algorithm 1 on representative configurations including A-only, B-only, mixed A/B, equal m_a values, the d = m_a boundary, and l_b = d, and checked the alternation arguments in Lemmas 2–4. The constructed word is genuinely 3-uniform, and the alternation or non-alternation claims hold in the tested cases. The main proof is internally consistent. The only place where correctness is not settled by the paper itself is the external characterization Theorem 3; if that theorem were false or missing a condition, the central bound would lack support. This matches the reader's weakest_assumption. I also noted a minor proof typo in Lemma 1 at the d = m_a boundary, but it is not load-bearing because the lemma's conclusion remains true after the line 18 replacement. The later characterization results additionally rely on the unpublished preprint [4] for split comparability graphs, but that does not affect the central R(G) ≤ 3 claim. Verdict remains ACCEPT.","tokens_in":70,"tokens_out":30230,"duration_ms":412487,"concrete_test":"Implement the [18] labeling routine and Algorithm 1; exhaustively generate all word-representable split graphs on up to 7 vertices using the semi-transitive orientation criterion, verify that the labels from [18] satisfy Theorem 3(i)–(iii), and then brute-force check the constructed word w against every edge/non-edge pair. If any graph fails the labeling conditions or w misrepresents a pair, Theorem 5 collapses; if none fails, the external premise and the construction cohere for all small cases.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 5 depends entirely on Theorem 3 ([15,18]): the A/B classification, Remark 1, and all alternation lemmas in Section 3 use the interval-neighborhood labeling conditions. The present paper neither proves nor independently checks this characterization. If the 'if' direction of Theorem 3 required an extra hidden condition, the 3-uniform word constructed by Algorithm 1 could fail to represent some word-representable split graph, and R(G) ≤ 3 would not follow from this proof. I found no internal derivation gap in Lemmas 2–4 once Theorem 3 is granted. Minor issue: Lemma 1 writes m_adn_a ≪ p3 when m_a = d, which is impossible because p3 has only one copy of the label d; the intended m_aan_a still follows after line 18 since the d occurrence is replaced by d followed by reverse(p1|A), so the proof is fixable but should be corrected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies word-representable split graphs. Its main result is Theorem 5: every word-representable split graph has representation number at most three. The proof takes an external labeling characterization (Theorem 3, attributed to [15,18]), partitions the independent vertices into classes A and B according to whether their clique-neighborhoods are two-ended or interval, and gives Algorithm 1 that outputs a 3-uniform word w = p1(p1|B)^R p2 p3. Lemmas 1-4 verify alternation for adjacent and non-adjacent pairs, and Theorem 5 assembles these checks. The paper then characterizes the subclass with representation number exactly three (Theorem 6) as those containing an induced graph from the family C3, and, for split comparability graphs (Theorem 8), as those containing F0 or F1(5).","tokens_in":12752,"tokens_out":42655,"duration_ms":401368,"significance":"If correct, the paper resolves the open question of the representation number of word-representable split graphs, proving a uniform upper bound of 3 and identifying the exact induced-subgraph obstructions to representation number 3. The construction is explicit and algorithmic, and the alternation lemmas are self-contained case analyses once the external labeling theorem is granted. The paper also makes good use of the published forbidden-subgraph characterizations of split circle and split permutation graphs. The main caveats are an edge case in the interval notation that the proof does not handle, and a dependence on an unpublished companion preprint for part of the exact-three characterization. Apart from these points, I found no internal derivation gap in the central R(G) ≤ 3 argument.","major_comments":[{"comment":"As stated, Theorem 3 does not cover independent vertices with N(a) = ∅, because the notation [a,b] is defined only for a ≤ b and neither [l,r] nor [1,m] ∪ [n,k] can be empty under that convention. Such vertices occur in word-representable split graphs (for example, K2 ∪ K1 with the isolated vertex in I), so the A/B partition and Algorithm 1 do not apply to all allowed inputs. Please add an explicit reduction: an isolated independent vertex can be represented by appending its three occurrences consecutively to the constructed word, or extend the interval notation and adjust Algorithm 1 accordingly. This is a local fix, but it is load-bearing for Theorem 5 as written.","section":"Section 2, Theorem 3 and Section 3, Algorithm 1"},{"comment":"The proof that F1(5) is a comparability graph invokes Theorem 4, which is cited only as the authors' preprint [4] and is not proved in this manuscript. Since Theorem 8 is a stated characterization of the paper, this is a load-bearing external dependence. Please either prove Theorem 4 (or the specific labeling conditions used for F1(5)) directly in the paper, or cite a peer-reviewed source for it.","section":"Section 3.2, Theorems 7 and 8"}],"minor_comments":[{"comment":"The displayed subword m_a d n_a is not actually a subword of p3 when m_a = d, because p3 contains only one copy of d. The intended conclusion m_a a n_a ≪ p3 is still correct after line 18, but the notation should be clarified, for example by writing m_a ... d ... n_a and explaining that the middle position may coincide with m_a.","section":"Lemma 1, proof"},{"comment":"The paper implicitly uses that w is 3-uniform, but this is never stated as a separate observation. It would help to say explicitly: C-vertices occur in p1, p2, p3; B-vertices occur in p1, (p1|B)^R, p2; and A-vertices occur in p1, p2, p3.","section":"Section 3, after Algorithm 1"},{"comment":"The backward labeling statement 'vertices c_{k−3},...,c_{k−m} are labeled m−1,...,2' is not meaningful when m = 1, since m−1 = 0 is not a label. The contradiction can still be obtained for m = 1, but the case needs a separate sentence or a cleaner index convention.","section":"Lemma 10, Case 1"},{"comment":"The converse direction uses the fact that an induced non-circle subgraph makes the whole graph non-circle; this is the heredity of circle graphs and should be stated explicitly.","section":"Theorem 6, proof"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the central R(G) ≤ 3 proof appears sound conditional on the cited characterization of word-representable split graphs, but the isolated-vertex edge case in Theorem 3 should be fixed before publication. The exact-three characterization for split comparability graphs currently rests on an unpublished same-author preprint [4], which I would want resolved (either by including a proof or by pointing to a refereed source) before accepting the paper's full set of claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: this paper proves that every word-representable split graph has representation number at most 3, and it gives an explicit algorithm that constructs a 3-uniform representing word. I read the construction carefully and the proof of Theorem 5 holds up. The systematic case analysis in Lemmas 2–4 checks every adjacency type and I didn't find a gap. The main theorem is genuinely new — earlier work only bounded the permutation-representation number of split comparability graphs, not the representation number of all word-representable split graphs.\n\nWhat's actually good: Algorithm 1 is a real contribution. It uses the interval-neighborhood labeling of the clique from Kitaev–Long–Ma–Wu / Kitaev–Pyatkin and builds three permutations that, when concatenated, represent the graph. The proof that the word is 3-uniform and that alternation matches adjacency is careful. The exact-3 characterization for word-representable split graphs (Theorem 6) is also new, and the forbidden family C3 is explicitly described and mostly verified. The paper is clearly written and self-contained except for its external dependencies.\n\nSoft spots, in proportion to how soft they are. The main load-bearing step is Theorem 3, the known characterization of word-representable split graphs by clique labelings. The paper cites it from [15,18] and uses it to define the sets A and B and to justify every lemma in Section 3. That's legitimate — the result is published — but the current proof is entirely contingent on it. If that theorem had a hidden condition, the construction would fail. I've no reason to doubt it, but I'd expect the paper to state the dependence more forthrightly. The bigger issue is Theorem 4 from the authors' own preprint [4], used to identify F1(5) as a comparability graph in Theorem 7. The characterization of split comparability graphs with representation number 3 is thus contingent on an unrefereed result. That needs to be fixed: either include a proof of Theorem 4 or drop it if a published version exists. There is also a minor slip in Lemma 1: the subword m_adn_a is impossible when m_a = d, since p3 is a permutation at that point and has only one copy of d. The intended result still follows after the line-18 replacement, so it's easily repairable, but it should be corrected.\n\nBottom line: this is a worthwhile paper for anyone working on word-representable graphs. The core result appears correct and the algorithmic construction is a nice addition. It deserves a serious referee and, with minor revisions addressing the preprint dependency and the Lemma 1 slip, I'd be happy to see it published.","headline":"A credible and likely correct resolution of R(G)≤3 for word-representable split graphs, but the exact-3 characterization for comparability graphs leans on an unpublished preprint by the same authors.","tokens_in":13294,"tokens_out":5559,"would_cite":true,"duration_ms":51178,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Every word-representable split graph has a 3-uniform word representative.","keywords":["word-representable graphs","representation number","split graphs","comparability graphs","3-uniform words","circle graphs","forbidden induced subgraphs","algorithmic word construction"],"falsifier":"Take any split graph whose clique labeling satisfies the three conditions of Theorem 3, run Algorithm 1, and check the alternation pattern of the resulting word against the graph's adjacency matrix; a single edge whose two letters fail to alternate, or a single non-edge whose two letters do alternate, would refute Theorem 5. An exhaustive search over small split graphs computing their representation number would also settle the bound: finding one word-representable split graph with representation number 4 is a counterexample.","tokens_in":12403,"feed_emoji":"🔤","tokens_out":13705,"duration_ms":126622,"temperature":0.7,"pith_summary":"A split graph is a graph whose vertices can be split into a clique, where every pair is adjacent, and an independent set, where no edges appear. A graph is word-representable when some finite word over its vertices has the property that two letters alternate exactly when the two vertices are adjacent. This paper proves that every word-representable split graph is 3-word-representable: there is always a word in which each vertex appears exactly three times. The proof is constructive, producing the word by a fixed algorithm from the clique labeling supplied by an earlier characterization. The paper also characterizes exactly when three appearances are necessary: among word-representable split graphs, this happens precisely when the graph contains one of the listed induced subgraphs, and among split comparability graphs only when it contains $F_0$ or $F_1(5)$.","feed_headline":"Split graphs that words can draw need only 3 copies of each vertex","feed_subtitle":"A constructive proof builds a 3-uniform word for any such graph and tells exactly when fewer repeats cannot work.","key_machinery":"The machine that carries the argument is Algorithm 1's word $w=p_1(p_1|_B)^R p_2 p_3$, where $p_1$ and $p_2$ are permutations on the whole vertex set, $p_3$ is a permutation on $C\\cup A$ only, and the $B$-vertices receive their third occurrence in the reversed subword $(p_1|_B)^R$. Because every vertex appears in three of these four factors, $w$ is 3-uniform. The insertion rules place each independent vertex $a$ beside the boundary of its neighborhood in the ordered clique: $A$-vertices go next to the right end of their left interval in $p_1$ and the left end of their right interval in $p_2$; $B$-vertices go next to the two ends of their single interval in $p_1$ and $p_2$; and $p_3$ is built by reversing the $A$-order after a pivot $d$, which Remark 1 guarantees lies between all left ends and all right ends of $A$-neighborhoods. These placements reduce the alternation checks in Lemmas 1–4 to the interval order.","core_discovery":"On the paper's own terms, the discovery is an upper bound with a witness: every word-representable split graph $G=(I\\cup C,E)$ has $R(G)\\le 3$. After labeling the clique $C$ as $1,\\dots,k$ according to Theorem 3, each independent vertex has a neighborhood of one of two shapes, a single interval $[l,r]$ (collected in $B$) or two end intervals $[1,m]\\cup[n,k]$ (collected in $A$). Algorithm 1 constructs three permutations $p_1,p_2,p_3$ and returns the 3-uniform word $w=p_1(p_1|_B)^R p_2 p_3$. Lemmas 2–4 check every pair type: clique–clique edges alternate, independent-to-clique adjacencies alternate, and all non-edges fail to alternate, so $w$ represents $G$. Theorem 6 then characterizes $R(G)=3$ by the presence of an induced subgraph from the family $\\mathcal{C}_3$, and Theorem 8 restricts that characterization for split comparability graphs to $F_0$ and $F_1(5)$.","pith_inferences":["A complexity corollary the paper does not state: since word-representable split graphs are recognizable in polynomial time and Algorithm 1 supplies a 3-uniform word, deciding whether a split graph has representation number at most 3 is polynomial for this class, even though the general problem is NP-complete.","The exact-3 characterization is expressed through the family $\\mathcal{C}_3$ sitting inside the larger circle-graph forbidden family $\\mathcal{C}$; the paper's conclusion suggests that shrinking this to a list of minimal forbidden induced subgraphs is the next step, and would make the $R(G)=3$ test purely structural.","The same concatenation pattern, three factors with the middle factor reversed over one type of independent vertex, may transfer to any graph class admitting an interval-neighborhood labeling of the same two-shape form, not only split graphs."],"forward_implications":["Every word-representable split graph has a concrete 3-uniform representative, so the representation number of the entire class is bounded by 3.","A word-representable split graph has representation number exactly 3 precisely when it contains an induced copy of $F_0$, an even $k$-sun ($k\\ge 4$), or $F_1(k)$/$F_2(k)$ for odd $k\\ge 5$; otherwise its representation number is at most 2.","For split comparability graphs, representation number 3 is equivalent to containing $F_0$ or $F_1(5)$ as an induced subgraph.","Because the upper-bound proof is an algorithm rather than an existence argument, the representing word is produced directly from the clique labeling."],"supporting_citations":[{"why":"Supplies Theorem 3, the interval-neighborhood labeling characterization of word-representable split graphs that Algorithm 1 takes as input.","marker":"[15,18]"},{"why":"Gives the polynomial-time procedure that finds this clique labeling, making the 3-uniform construction algorithmic.","marker":"[18]"},{"why":"Establishes that representation number at most two is exactly the circle graphs, used to identify $R(G)=3$, and provides the neighborhood/comparability lemma used in non-word-representability arguments.","marker":"[10]"},{"why":"Provides the forbidden induced subgraph family $\\mathcal{C}$ for circle graphs within split graphs, which Theorem 6 invokes to force an induced $\\mathcal{C}_3$ subgraph when $R(G)=3$.","marker":"[1]"},{"why":"Proves even $k$-suns are word-representable and odd $k$-suns with center are not, contributing the key members of $\\mathcal{C}_3$.","marker":"[15]"},{"why":"Shows $M_V$ (isomorphic to $T_8$) is non-word-representable, adding another member of the excluded family.","marker":"[3]"},{"why":"Characterizes split comparability graphs by forbidden $B_1,B_2,B_3$; used to show $F_0$ and $F_1(5)$ are the only comparability graphs in $\\mathcal{C}_3$.","marker":"[8]"}],"fun_headline_variants":["Word-representable split graphs need at most 3 repeats","Representation number of split graphs capped at 3","Every word-representable split graph has a 3-uniform word","Split graphs need only 3 repeats in word representation","Constructive proof caps split graph repeats at 3"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on an earlier theorem, taken as given, that every word-representable split graph has its clique vertices ordered so that each independent vertex's neighbors form either one consecutive block or two blocks at the two ends, with three compatibility rules between these blocks, and that such an ordering can be found in polynomial time. If that theorem had a hidden extra condition or the ordering procedure could fail, the word constructed here would not be guaranteed to represent every word-representable split graph.","fun_headline_variants_meta":{"raw":{"variants":["Word-representable split graphs need at most 3 repeats","Representation number of split graphs capped at 3","Every word-representable split graph has a 3-uniform word","Split graphs need only 3 repeats in word representation","Constructive proof caps split graph repeats at 3"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000727,"raw_usage":{"total_tokens":3238,"prompt_tokens":910,"completion_tokens":2328,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":526,"completion_tokens_details":{"reasoning_tokens":2249}},"tokens_in":526,"tokens_out":2328,"duration_ms":16425,"temperature":1.0,"reasoning_tokens":2249,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T17:26:26.483063+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any split graph whose clique labeling satisfies the three conditions of Theorem 3, run Algorithm 1, and check the alternation pattern of the resulting word against the graph's adjacency matrix; a single edge whose two letters fail to alternate, or a single non-edge whose two letters do alternate, would refute Theorem 5. An exhaustive search over small split graphs computing their representation number would also settle the bound: finding one word-representable split graph with representation number 4 is a counterexample.","supporting_citations":[{"cited_title":"Kitaev and A","cited_arxiv_id":null,"evidence_quote":"Gives the polynomial-time procedure that finds this clique labeling, making the 3-uniform construction algorithmic."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that representation number at most two is exactly the circle graphs, used to identify $R(G)=3$, and provides the neighborhood/comparability lemma used in non-word-representability arguments."},{"cited_title":"Bonomo-Braberman, G","cited_arxiv_id":null,"evidence_quote":"Provides the forbidden induced subgraph family $\\mathcal{C}$ for circle graphs within split graphs, which Theorem 6 invokes to force an induced $\\mathcal{C}_3$ subgraph when $R(G)=3$."},{"cited_title":"Kitaev, Y","cited_arxiv_id":null,"evidence_quote":"Proves even $k$-suns are word-representable and odd $k$-suns with center are not, contributing the key members of $\\mathcal{C}_3$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows $M_V$ (isomorphic to $T_8$) is non-word-representable, adding another member of the excluded family."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Characterizes split comparability graphs by forbidden $B_1,B_2,B_3$; used to show $F_0$ and $F_1(5)$ are the only comparability graphs in $\\mathcal{C}_3$."}],"review_version":1}