pith. sign in

arxiv: 2605.02268 · v2 · pith:QPQBFWWYnew · submitted 2026-05-04 · 🧮 math.CO · cs.DM

Word-Representability of Shift Graphs

Suchanda Roy , Ramesh Hariharasubramanian This is my paper

Pith reviewed 2026-05-25 06:50 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords shift graphsword-representable graphsgeneralized shift graphsline graphsline digraphsde Bruijn graphsalternating words
0
0 comments X

The pith

Shift graphs on k-tuples are word-representable, as are their multi-shift generalizations.

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

Shift graphs have vertices consisting of all strictly increasing k-tuples chosen from {1, ..., n} and place an edge between two tuples precisely when one is obtained from the other by a single shift of its entries. The paper establishes that every such graph admits a word on its vertex set in which two letters alternate if and only if the corresponding tuples are adjacent under the shift rule. The same construction works when adjacency is defined by any fixed number of simultaneous shift conditions. The resulting family supplies explicit word-representable graphs whose ordinary line graphs cease to be word-representable once the number of vertices reaches five, while the corresponding line digraphs remain word-representable.

Core claim

We prove that the entire class of shift graphs is word-representable. We also introduce a natural generalization of shift graphs in which adjacency is defined by more than one shift condition, and show that these generalized shift graphs are likewise word-representable. As a consequence, we obtain an explicit family of graphs exhibiting a contrast between line graph and line digraph constructions: there exists a family of word-representable graphs whose line graphs are not word-representable when the number of vertices is at least 5, while their line digraphs are word-representable.

What carries the argument

A single word over the vertex set of k-tuples whose letter-alternation pattern reproduces exactly the shift-adjacency relation (one or more simultaneous shifts).

If this is right

  • Generalized shift graphs defined by any fixed number of simultaneous shift conditions are word-representable.
  • The line graph of any such word-representable graph fails to be word-representable once it has at least five vertices.
  • The line digraph of the same graph remains word-representable.
  • Shift graphs appear as induced subgraphs of simplified de Bruijn graphs yet stay word-representable even though some simplified de Bruijn graphs are not.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The explicit word construction may extend to other families of overlap or shift graphs arising from de Bruijn-type objects.
  • Word-representability is preserved under the passage from a shift graph to its multi-shift generalization.
  • The separation between line-graph and line-digraph behavior supplies a concrete test case for any conjecture that tries to characterize when word-representability is closed under line operations.

Load-bearing premise

The shift rule on k-tuples can be realized by the alternation pattern of some word without creating unwanted alternations between non-adjacent pairs.

What would settle it

An explicit pair n > k together with a proof that no finite word over the set of k-tuples alternates exactly on the shift edges of G(n,k).

read the original abstract

A graph $G=(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $w$ if and only if $xy\in E$. For integers $n>k>0 $, the shift graph $G(n,k)$ is the graph whose vertex set consists of all increasing $k$-tuples $(x_1,x_2,\dots,x_k)$ with $1\le x_1<x_2<\cdots<x_k\le n$, where two vertices $(x_1,\dots,x_k)$ and $(y_1,\dots,y_k)$ are adjacent whenever $x_{i+1}=y_i$ for all $1\le i\le k-1$ or $y_{i+1}=x_i$ for all $1\le i\le k-1$. Shift graphs are classical examples of sparse graphs having arbitrarily high chromatic number and odd girth. We further observe that shift graphs arise naturally as induced subgraphs of simplified de Bruijn graphs. Although simplified de Bruijn graphs contain non-word-representable members in general, we prove that the entire class of shift graphs is word-representable. We also introduce a natural generalization of shift graphs in which adjacency is defined by more than one shift condition, and show that these generalized shift graphs are likewise word-representable. As a consequence, we obtain an explicit family of graphs exhibiting a contrast between line graph and line digraph constructions: there exists a family of word-representable graphs whose line graphs are not word-representable when the number of vertices is at least $5$, while their line digraphs are word-representable.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proves that all shift graphs G(n,k) (vertices are increasing k-tuples from [n], edges via single forward or backward shift) are word-representable, introduces a natural multi-shift generalization of these graphs that is likewise word-representable, notes that shift graphs arise as induced subgraphs of simplified de Bruijn graphs, and derives an explicit family of word-representable graphs whose line graphs are non-word-representable (for |V| >= 5) while their line digraphs remain word-representable.

Significance. If the explicit word constructions hold, the result supplies a concrete, infinite family separating word-representability of line graphs from line digraphs and embeds the classically extremal shift graphs (arbitrarily high chromatic number, large odd girth) into the word-representable class. The de Bruijn-graph embedding and the line/line-digraph contrast are presented as direct corollaries of the main existence theorems.

minor comments (2)
  1. The abstract states the line-graph/line-digraph contrast for 'the number of vertices is at least 5' but does not indicate which specific member of the family first exhibits the separation; a sentence in the introduction or §4 clarifying the smallest example would improve readability.
  2. Notation for the multi-shift generalization is introduced only in the abstract; an explicit definition with the precise adjacency rule (multiple simultaneous shift conditions) should appear in the body before the proof that these graphs are word-representable.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and the recommendation of minor revision. The report lists no specific major comments.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper offers a direct combinatorial existence proof that every shift graph G(n,k) and its multi-shift generalizations admit a word over the vertex set whose alternation pattern matches the shift-adjacency relation exactly. The argument proceeds from the explicit definition of vertices as increasing k-tuples and edges via the two shift conditions, without any reduction of the target property to a fitted parameter, self-referential equation, or load-bearing self-citation. The de Bruijn-graph embedding and line-graph/line-digraph corollaries are derived after the main existence result and do not feed back into it. This is a standard non-circular proof structure for a class defined by explicit combinatorial rules.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard combinatorial definitions of graphs, words, and alternation; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of graphs, words over an alphabet, and the alternation condition for edges
    The paper builds directly on these background notions from graph theory and combinatorics on words.

pith-pipeline@v0.9.0 · 5843 in / 1298 out tokens · 55159 ms · 2026-05-25T06:50:15.668965+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    On chromatic number of graphs and set-systems.Acta Math

    Paul Erd˝ os and Andr´ as Hajnal. On chromatic number of graphs and set-systems.Acta Math. Acad. Sci. Hungar, 17(61-99):1, 1966

    work page 1966

  2. [2]

    Interval orders and shift graphs

    Zoltan F¨ uredi, P´ eter Hajnal, Vojtech R¨ odl, and William T Trotter. Interval orders and shift graphs. 1992

    work page 1992

  3. [3]

    Alternation graphs

    Magn´ us M Halld´ orsson, Sergey Kitaev, and Artem Pyatkin. Alternation graphs. InGraph-Theoretic Concepts in Computer Science: 37th International Workshop, WG 2011, Tepl´ a Monastery, Czech Republic, June 21-24, 2011. Revised Papers 37, pages 191–202. Springer, 2011

    work page 2011

  4. [4]

    Halld´ orsson, Sergey Kitaev, and Artem Pyatkin

    Magn´ us M. Halld´ orsson, Sergey Kitaev, and Artem Pyatkin. Semi-transitive orientations and word- representable graphs.Discrete Applied Mathematics, 201:164–171, 2016. 5

    work page 2016

  5. [5]

    On semi-transitivity of (extended) mycielski graphs.Discrete Applied Mathemat- ics, 359:83–88, 2024

    Humaira Hameed. On semi-transitivity of (extended) mycielski graphs.Discrete Applied Mathemat- ics, 359:83–88, 2024

    work page 2024

  6. [6]

    An embedding technique in the study of word- representability of graphs.Discrete Applied Mathematics, 346:170–182, 2024

    Sumin Huang, Sergey Kitaev, and Artem Pyatkin. An embedding technique in the study of word- representability of graphs.Discrete Applied Mathematics, 346:170–182, 2024

    work page 2024

  7. [7]

    A comprehensive introduction to the theory of word-representable graphs

    Sergey Kitaev. A comprehensive introduction to the theory of word-representable graphs. InInter- national Conference on Developments in Language Theory, pages 36–67. Springer, 2017

    work page 2017

  8. [8]

    Springer, 2015

    Sergey Kitaev and Vadim Lozin.Words and graphs. Springer, 2015

    work page 2015

  9. [9]

    A note on hameed’s conjecture on the semi-transitivity of my- cielski graphs.Discussiones Mathematicae Graph Theory, 2025

    Sergey Kitaev and Artem Pyatkin. A note on hameed’s conjecture on the semi-transitivity of my- cielski graphs.Discussiones Mathematicae Graph Theory, 2025

    work page 2025

  10. [10]

    Word-representability of line graphs.Open Journal of Discrete Mathematics, 1(2):96–101, 2011

    Sergey Kitaev, Pavel Salimov, Christopher Severs, and Henning Ulfarsson. Word-representability of line graphs.Open Journal of Discrete Mathematics, 1(2):96–101, 2011

    work page 2011

  11. [11]

    Word problem of the perkins semigroup via directed acyclic graphs

    Sergey Kitaev and Steve Seif. Word problem of the perkins semigroup via directed acyclic graphs. Order, 25(3):177–194, 2008

    work page 2008

  12. [12]

    On word-representability of simplified de bruijn graphs.arXiv preprint arXiv:2210.14762, 2022

    Anthony V Petyuk. On word-representability of simplified de bruijn graphs.arXiv preprint arXiv:2210.14762, 2022

    work page arXiv 2022