pith. sign in

arxiv: 1907.09152 · v1 · pith:AWIWHVIXnew · submitted 2019-07-22 · 🧮 math.CO

Word-representability of Toeplitz graphs

Gi-Sang Cheon , Jinha Kim , Minki Kim , Sergey Kitaev This is my paper

Pith reviewed 2026-05-24 18:19 UTC · model grok-4.3

classification 🧮 math.CO
keywords word-representable graphsToeplitz graphsRiordan graphsAppell typeadjacency patternsinfinite graphsalternating words
0
0 comments X

The pith

Toeplitz graphs defined by constant diagonal patterns are word-representable for several general classes, with constructions for non-representable cases and infinite examples.

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

The paper proves that several families of Toeplitz graphs admit words over their vertices where two letters alternate if and only if they are adjacent. It also constructs Toeplitz graphs that are not word-representable and extends the definition to infinite Riordan graphs of Appell type with general examples. This merges the theories of Riordan matrices and word-representable graphs through pattern-based adjacency matrices and provides the first systematic study of such graphs, including infinite cases.

Core claim

Word-representable Toeplitz graphs exist in several general classes where explicit words can be built to satisfy the alternation condition exactly on the edges determined by the constant diagonal patterns; non-word-representable Toeplitz graphs can be constructed similarly, and infinite word-representable Riordan graphs are introduced with examples.

What carries the argument

The definition of word-representability via alternation of letters in a word matching the edges of the graph, applied to the Toeplitz structure of Riordan graphs of Appell type.

Load-bearing premise

The constant-diagonal patterns allow explicit word constructions that realize the exact alternation condition without internal contradictions in the periodic adjacency.

What would settle it

Finding a Toeplitz graph in one of the general classes claimed to be word-representable for which no such alternating word exists, or showing that a constructed non-representable example actually admits one.

Figures

Figures reproduced from arXiv: 1907.09152 by Gi-Sang Cheon, Jinha Kim, Minki Kim, Sergey Kitaev.

Figure 1
Figure 1. Figure 1: G6 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: G6  1− √ 1−4z 2z , 1− √ 1−4z 2  , the Catalan graph of order 6 See [8] and references therein for examples of results in the literature on Toeplitz graphs. Throughout this paper, we denote by Gn(a1a2 · · · am) the Toeplitz graph on n vertices which is defined by Gn  b1 + b2z + · · · + bmz m−1 1 − zm , z , where ai ≡ bi (mod 2). For instance, the Fibonacci graph Gn [PITH_FULL_IMAGE:figures/full_fig_p00… view at source ↗
read the original abstract

Distinct letters $x$ and $y$ alternate in a word $w$ if after deleting in $w$ all letters but the copies of $x$ and $y$ we either obtain a word of the form $xyxy\cdots$ (of even or odd length) or a word of the form $yxyx\cdots$ (of even or odd length). 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$ is an edge in $E$. In this paper we initiate the study of word-representable Toeplitz graphs, which are Riordan graphs of the Appell type. We prove that several general classes of Toeplitz graphs are word-representable, and we also provide a way to construct non-word-representable Toeplitz graphs. Our work not only merges the theories of Riordan matrices and word-representable graphs via the notion of a Riordan graph, but also it provides the first systematic study of word-representability of graphs defined via patterns in adjacency matrices. Moreover, our paper introduces the notion of an infinite word-representable Riordan graph and gives several general examples of such graphs. It is the first time in the literature when the word-representability of infinite graphs is discussed.

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 initiates the study of word-representability for Toeplitz graphs (Riordan graphs of Appell type). It proves word-representability for several general classes via explicit constructions realizing the required alternation condition exactly on the constant diagonals, provides a separate construction for non-word-representable Toeplitz graphs, and introduces infinite word-representable Riordan graphs with general examples.

Significance. If the constructions hold, this merges the theories of Riordan matrices and word-representable graphs and provides the first systematic study of word-representability for graphs defined via adjacency matrix patterns. The explicit constructions for the classes and the extension to infinite graphs are strengths. The stress-test concern about compatibility of the alternation condition with the Toeplitz constant-diagonal pattern does not land on the manuscript; the definitions are standard and no internal inconsistency is apparent.

minor comments (2)
  1. The abstract states that 'several general classes' are shown to be word-representable but does not name them; adding a brief enumeration or reference to the relevant theorem numbers would improve clarity for readers.
  2. Notation for the infinite case (e.g., how alternation is defined for infinite words) should be introduced explicitly in the main text rather than left implicit from the finite case.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's claims rest on explicit combinatorial constructions that realize the alternation condition for word-representability on the constant-diagonal patterns of Toeplitz/Riordan graphs of Appell type, together with separate constructions for non-representable examples and infinite cases. These are direct proofs from the standard definitions of alternation and the matrix patterns; no equations reduce a claimed result to a fitted parameter or self-referential definition, and no load-bearing step is justified solely by a self-citation chain. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the standard definitions of word-representability and of Riordan graphs of Appell type; no free parameters, invented entities, or non-standard axioms are introduced.

axioms (1)
  • domain assumption Standard definitions of word-representability via alternation and of Toeplitz graphs as Riordan graphs of Appell type are assumed to hold without additional constraints.
    All claims about existence of representing words or non-representable constructions presuppose these combinatorial definitions.

pith-pipeline@v0.9.0 · 5796 in / 1341 out tokens · 27907 ms · 2026-05-24T18:19:11.714861+00:00 · methodology

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

18 extracted references · 18 canonical work pages

  1. [1]

    Beigel, D

    R. Beigel, D. Eppstein. 3-coloring in time O(1.3289n). J. Algorithms 54 (2) (2005) 168–204

    work page 2005

  2. [2]

    E. J. L. Bell. Word-graph theory. PhD thesis, Lancaster Univer sity, 2011

    work page 2011

  3. [3]

    The maximum cliq ue problem

    I. M. Bomze, M. Budinich, P. M. Pardalos, M. Pelillo. “The maximum cliq ue problem”, Handbook of Combinatorial Optimization, 4, Kluwer Academic Publishe rs (1999) 1–74

    work page 1999

  4. [4]

    R. L. Brooks. On colouring the nodes of a network. Proc. Cambridge Philos. Soc. 37 (1941) 194–197

    work page 1941

  5. [5]

    ˘Cern´ y

    J. ˘Cern´ y. Coloring circle graphs.Electronic Notes in Discr. Math. 29 (2007) 457–461

    work page 2007

  6. [6]

    Cheon, J

    G.-S. Cheon, J. Jung, S. Kitaev, S. A. Mojallal. Riordan graphs I: Structural properties, Linear Algebra and its Appl. 579 (2019) 89–135

    work page 2019

  7. [7]

    Collins, S

    A. Collins, S. Kitaev, V. Lozin. New results on word-representab le graphs, Discrete Appl. Math. 216P1 (2017) 136–141. 16

    work page 2017

  8. [8]

    S. H. Ghorban, Toeplitz graph decomposition , Transactions on Combinatorics 1(4) (2012), 35–41

    work page 2012

  9. [9]

    M. Glen. Software to work with word-representable graphs. Av ailable at https://personal.cis.strath.ac.uk/sergey.kitaev/word-representable-graphs.html

    work page

  10. [10]

    Graham, N

    R. Graham, N. Zang. Enumerating split-pair arrangements, J. Combin. Theory, Series A 115, Issue 2 (2008), 293–303

    work page 2008

  11. [11]

    Halld´ orsson, S

    M. Halld´ orsson, S. Kitaev, A. Pyatkin. Semi-transitive orienta tions and word- representable graphs. Discr. Appl. Math. 201 (2016) 164–171

    work page 2016

  12. [12]

    Kitaev (2017) A Comprehensive introduction to the theory o f word-representable graphs

    S. Kitaev (2017) A Comprehensive introduction to the theory o f word-representable graphs. In: ´E. Charlier, J. Leroy, M. Rigo (eds), Developments in Language The ory. DLT 2017. Lecture Notes Comp. Sci. 10396, Springer, 36–67

    work page 2017

  13. [13]

    Kitaev, V

    S. Kitaev, V. Lozin. Words and graphs. Springer, 2015

    work page 2015

  14. [14]

    Kitaev, A

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

    work page 2008

  15. [15]

    Kitaev, S

    S. Kitaev, S. Seif. Word problem of the Perkins semigroup via dire cted acyclic graphs. Order 25 (2008) 3, 177–194

    work page 2008

  16. [16]

    M. Koebe. On a new class of intersection graphs. In Jaroslav Ne ˘ set˘ ril and Miroslav Fiedler, editors, Fourth Czechoslovakian Symposium on Combinator ics, Graphs and Complexity (Prachatice, 1990), volume 51 of Ann. Discrete Math., p ages 141–143. North-Holland, Amsterdam, 1992

    work page 1990

  17. [17]

    Lov´ asz

    L. Lov´ asz. Perfect graphs. Selected Topics in Graph Theory, 2, London: Academic Press (1983) 55–87

    work page 1983

  18. [18]

    S. Seif. The Perkins Semigroup has Co-NP-complete term-equiv alence problem. Int. J. Alg. Comp. (IJAC) 15(2) (2005) 317–326. 17

    work page 2005