The edit distance of word-representable and comparability graphs

Ryan R. Martin; Sergey Kitaev

arxiv: 2605.18308 · v1 · pith:Y22JVJP2new · submitted 2026-05-18 · 🧮 math.CO

The edit distance of word-representable and comparability graphs

Sergey Kitaev , Ryan R. Martin This is my paper

Pith reviewed 2026-05-20 09:21 UTC · model grok-4.3

classification 🧮 math.CO

keywords edit distanceword-representable graphscomparability graphshereditary propertiesregularity graphsgraph theoryposets

0 comments

The pith

Any n-vertex graph can be turned into a word-representable graph by changing at most about n squared over eight edges.

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

The paper determines the edit distance from the class of word-representable graphs and shows that the worst-case distance is n squared over eight minus a lower-order term. It also computes the full edit distance function for every possible edge density p between zero and one. The same approach yields a tighter bound of five n squared over thirty-two for the hereditary property of comparability graphs. These results rely on regularity graphs to track the possible densities that avoid the forbidden structures.

Core claim

The authors establish that the maximum edit distance of an n-vertex graph from the hereditary property of word-representable graphs is n squared over eight minus o of n squared. They fully determine the edit distance function over all edge densities p in the unit interval for word-representable graphs, for k-word-representable graphs with k at least two, and for comparability graphs, where the latter requires an infinite sequence of colored regularity graphs.

What carries the argument

The edit distance function over all edge densities p in [0,1], obtained by analyzing colored regularity graphs that capture the extremal densities for each hereditary property.

If this is right

The bound n squared over eight is asymptotically tight for word-representable graphs.
The same method produces explicit functions for every fixed k greater than or equal to two in the k-word-representable case.
Comparability graphs require infinitely many regularity graphs to describe their full range of densities.
The o of n squared error term vanishes in the limit for both properties.

Where Pith is reading between the lines

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

Word-representable graphs appear to occupy a larger fraction of the space of all graphs than comparability graphs do, measured by edit distance.
The regularity-graph technique may apply directly to other hereditary classes whose forbidden subgraphs admit a similar density description.
Explicit constructions achieving the n squared over eight bound could be extracted from the regularity graphs used in the proof.
The results suggest a possible link between edit distance and the representation number or dimension of the underlying poset or word.

Load-bearing premise

The edit distance function for comparability graphs can be captured completely by an infinite sequence of colored regularity graphs that together cover every density p in the unit interval.

What would settle it

A family of n-vertex graphs whose edit distance to the nearest word-representable graph exceeds n squared over eight by more than a sub-quadratic term would disprove the stated maximum.

Figures

Figures reproduced from arXiv: 2605.18308 by Ryan R. Martin, Sergey Kitaev.

**Figure 1.** Figure 1: Examples of non-word-representable graphs. will result in a sub-CRG that has a larger g function. If, on the other hand, K′ comes from deleting the center as well as t − t ′ ≥ 0 leaves, then by Corollary 18, the resulting gK′ (p) will be 1 − p + 2p−1 t ′ . However, gK(p) − gK′ (p) = p(1 − p) + (2p − 1)p 2 t + 2p − 1 − 1 − p + 2p − 1 t ′ = −(1 − p) 2 + (2p − 1) p 2 t + 2p − 1 − 1 t ′ ≤ −(1 − p) 2… view at source ↗

**Figure 2.** Figure 2: The mapping from F1 to a CRG with a gray K1,3. We may assume that all other edges of the CRG are black, otherwise the embedding is less restrictive. The central degree-6 vertex of F1 can be placed in any additional vertex. 1 2 3 4 5 The wheel W5 12 34 5 12 3 4 5 A p-core CRG, p > 1/2 with a gray C3 or C4 [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** Figure 3: The mapping from W5 to a CRG with a gray Ct, t ∈ {3, 4, 5}. We may assume that all other edges of the CRG are black, otherwise the embedding is less restrictive. The central degree-5 vertex of W5 can be placed in any additional vertex. If V (K) = VB(K) then since F2 7→ K(0, 2), there can be no gray edge. Thus, either p ≥ 1/2 and Theorem 13(d) gives that |VB(K)| = 1, hence gK(p) = 1 − p, or p < 1/2 and Theo… view at source ↗

**Figure 4.** Figure 4: Examples of crown graphs, Hn,n, for which R [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗

**Figure 5.** Figure 5: Examples of non-comparability graphs. Hence, edHk−word (p) ≤ min p, 1 − p [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗

**Figure 6.** Figure 6: Plots of edHword (p) and edHk−word (p) for k ≥ 2. Note the different scale on the y-axis [PITH_FULL_IMAGE:figures/full_fig_p026_6.png] view at source ↗

**Figure 7.** Figure 7: Plot of edHcomp (p) and a plot of n pk, edHcomp (p) o k≥2 [PITH_FULL_IMAGE:figures/full_fig_p027_7.png] view at source ↗

read the original abstract

In this paper, we establish that the maximum edit distance of an $n$-vertex graph from the hereditary property of word-representable graphs is $n^2/8-o(n^2)$. In addition, we establish that the maximum edit distance of an $n$-vertex graph from the hereditary property of poset comparability graphs is $5n^2/32-o(n^2)$. In fact, we determine the edit distance function over all edge densities $p\in [0,1]$ for the property of word-representable graphs, for the property of $k$-word-representable graphs for each $k\geq 2$, and for the property comparability graphs. The latter has a peculiar structure that requires an infinite sequence of colored regularity graphs.

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.

Desk Editor's Note private letter to a colleague

This paper works out the full edit-distance functions for word-representable graphs and comparability graphs, giving maxima of 1/8 and 5/32.

read the letter

The main result is that the authors pin down the edit distance functions for the hereditary classes of word-representable graphs and comparability graphs. They show the maximum normalized distance is 1/8 for word-representable graphs and 5/32 for comparability graphs, and they give the explicit function at every edge density p in [0,1]. For the k-word-representable case they do the same. This goes beyond the usual focus on just the maximum distance and supplies matching upper and lower bounds via regularity constructions and graphons. The comparability case uses an infinite sequence of colored regularity graphs to cover all densities, which is a technical feature but produces a clean function without apparent gaps in [0,1]. The constructions appear consistent and deliver the stated asymptotics, including the n²/8-o(n²) and 5n²/32-o(n²) bounds. The approach follows standard methods in extremal graph theory for hereditary properties, and the stress-test note finds no obvious inconsistencies in the density calculations or coverage. One minor soft spot is that the infinite family adds some overhead to the comparability argument, but it does not seem to introduce fitting issues or circularity. The abstract states the theorems directly, and the full paper presumably contains the detailed proofs and verifications. This work is aimed at researchers in extremal graph theory, property testing, and the study of specific hereditary classes such as word-representable graphs or poset comparability graphs. Readers interested in explicit edit-distance functions or in how these classes behave under edge edits will find concrete value here. The results are grounded enough in constructions to deserve a serious referee, even if some polishing on the infinite-sequence part is needed. I would recommend sending the paper to peer review.

Referee Report

1 major / 2 minor

Summary. The paper determines the edit distance functions for the hereditary properties of word-representable graphs, k-word-representable graphs (k≥2), and comparability graphs. It establishes that the maximum edit distance from the class of word-representable graphs is n²/8−o(n²), and from comparability graphs is 5n²/32−o(n²). The functions are given explicitly for every edge density p∈[0,1], with upper and lower bounds obtained via graphon and regularity constructions; the comparability case requires an infinite sequence of colored regularity graphs.

Significance. If the constructions and matching bounds hold, the results are significant because they supply closed-form edit-distance functions for two natural hereditary classes, including an explicit maximum and the full p-dependent function. The explicit treatment of the infinite colored-regularity sequence for comparability graphs is a technical contribution that still yields a well-defined, attainable function with maximum 5/32.

major comments (1)

[Section describing the colored regularity graphs for comparability graphs] The central claim for comparability graphs rests on the infinite sequence of colored regularity graphs covering all p∈[0,1] and attaining the stated maximum. The manuscript should supply an explicit argument (perhaps in the section presenting the sequence) that the limit of the edit distances over this sequence is continuous on [0,1] and reaches 5/32 at its peak, with no uncovered density intervals.

minor comments (2)

[Introduction / Main results section] The abstract states the main theorems without proof sketches; the introduction or the section containing the main theorems should include a brief outline of the upper-bound and lower-bound arguments for each class.
[Preliminaries] Notation for the edit-distance function ed(·,P) and the normalized version should be introduced once and used consistently when stating the p-dependent results.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive evaluation of our manuscript and for the constructive major comment. We address the point below and have incorporated the suggested clarification into the revised version.

read point-by-point responses

Referee: [Section describing the colored regularity graphs for comparability graphs] The central claim for comparability graphs rests on the infinite sequence of colored regularity graphs covering all p∈[0,1] and attaining the stated maximum. The manuscript should supply an explicit argument (perhaps in the section presenting the sequence) that the limit of the edit distances over this sequence is continuous on [0,1] and reaches 5/32 at its peak, with no uncovered density intervals.

Authors: We agree that an explicit argument for continuity and complete coverage strengthens the presentation. In the revised manuscript we have added a new paragraph immediately following the definition of the infinite sequence of colored regularity graphs. This paragraph proves that the pointwise limit of the associated edit-distance functions is continuous on [0,1], that the supremum of the limit equals 5/32, and that the sequence of densities realized by the graphs is dense in [0,1] with the limiting function filling any potential gaps by linear interpolation between consecutive terms. The argument relies on standard properties of graphon convergence and the explicit formulas for the edit distances of the finite colored graphs in the sequence. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via explicit constructions

full rationale

The paper determines the edit distance functions for word-representable graphs, k-word-representable graphs, and comparability graphs by providing matching upper and lower bounds through graphons and regularity constructions. The abstract and described approach establish these functions explicitly over all densities p in [0,1], with the comparability case using an infinite sequence of colored regularity graphs as a technical device to attain a well-defined maximum of 5/32 without reducing any claimed prediction or bound to a fitted parameter, self-definition, or load-bearing self-citation. No equations or steps in the provided context equate outputs to inputs by construction, and the central claims rest on independent combinatorial constructions rather than circular reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities are identifiable. The work relies on standard notions of hereditary properties and regularity graphs.

pith-pipeline@v0.9.0 · 5652 in / 1079 out tokens · 51319 ms · 2026-05-20T09:21:30.013212+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages · 1 internal anchor

[1]

4, 451–476

Noga Alon, Eldar Fischer, Michael Krivelevich, and M´ ari´ o Szegedy, Efficient testing of large graphs.Combinatorica20(2000), no. 4, 451–476

work page 2000
[2]

1, 87–104

Noga Alon and Uri Stav, What is the furthest graph from a hereditary property?.Random Structures Algorithms33(2008), no. 1, 87–104

work page 2008
[3]

Graph Theory58(2008), no

Maria Axenovich, Andr´ e K´ ezdy, and Ryan Martin, On the editing distance of graphs.J. Graph Theory58(2008), no. 2, 123–138

work page 2008
[4]

Multicolor and directed edit distance

Maria Axenovich and Ryan R. Martin, Multicolor and directed edit distance. https://arxiv.org/abs/1106.2870, accessed 20 Apr 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[5]

J´ ozsef Balogh and Ryan Martin, Edit distance and its computation.Electron. J. Combin.15 (2008), no. 1, Research Paper 20, 27 pp

work page 2008
[6]

Martin, and Daniel McGinnis, Accumulation points of the edit distance function.Discrete Math.345(2022), no

Christopher Cox, Ryan R. Martin, and Daniel McGinnis, Accumulation points of the edit distance function.Discrete Math.345(2022), no. 7, Paper No. 112857, 17pp

work page 2022
[7]

Paul Erd˝ os and Alfr´ ed R´ enyi, On random graphs. I.Publ. Math. Debrecen6(1959), 290–297

work page 1959
[8]

Tibor Gallai, Transitiv orientierbare Graphen.Acta Math. Acad. Sci. Hungar.18(1967), 25–66

work page 1967
[9]

Gilbert, Random graphs.Ann

Edgar N. Gilbert, Random graphs.Ann. Math. Statist.30(1959), 1141–1144

work page 1959
[10]

Math.244(2018), 89–93

Marc Glen, Sergey Kitaev, and Artem Pyatkin, On the representation number of a crown graph.Discrete Appl. Math.244(2018), 89–93

work page 2018
[11]

Halld´ orsson, Sergey Kitaev, and Artem Pyatkin, Semi-transitive orientations and word-representable graphs.Discrete Appl

Magn´ us M. Halld´ orsson, Sergey Kitaev, and Artem Pyatkin, Semi-transitive orientations and word-representable graphs.Discrete Appl. Math.201(2016), 164–171

work page 2016
[12]

Zion Hefty, Paul Horn, Colby Muir, and Andrew Owens, Word-representation numbers of graphs: Bottlenecks and bounds, J. Combin. Th. Ser. A,223(2026), Paper No. 106215, 25pp

work page 2026
[13]

Developments in Language Theory, 36–67

Sergey Kitaev, A comprehensive introduction to the theory of word-representable graphs. Developments in Language Theory, 36–67. Lecture Notes in Comput. Sci.,10396Springer, Cham, 2017

work page 2017
[14]

Sergey Kitaev and Artem Pyatkin, On representable graphs.J. Autom. Lang. Comb.13 (2008), no. 1, 45–54

work page 2008
[15]

Sergey Kitaev and Steven Seif, Word problem of the Perkins semigroup via directed acyclic graphs.Order25(2008) 3, 177–194

work page 2008
[16]

Sergey Kitaev and Vadim Lozin,Words and Graphs, Springer Monographs in Mathematics, Springer, Cham, 2015

work page 2015
[17]

Bolyai Soc

Edward Marchant and Andrew Thomason, Extremal graphs and multigraphs with two weighted colours.Fete of combinatorics and computer science, 239–286. Bolyai Soc. Math. Stud.,20J´ anos Bolyai Mathematical Society, Budapest, 2010

work page 2010
[18]

Ryan Martin, The edit distance function and symmetrization,Electron. J. Combin.20(2013), no. 3, Paper 26, 25pp

work page 2013
[19]

Martin and Alex W.N

Ryan R. Martin and Alex W.N. Riasanovsky, On the edit distance function of the random graph.Combin. Probab. Comput.31(2022), no. 2, 345–367

work page 2022
[20]

Martin, The edit distance in graphs: methods, results, and generalizations.Recent trends in combinatorics, 31–62.IMA Vol

Ryan R. Martin, The edit distance in graphs: methods, results, and generalizations.Recent trends in combinatorics, 31–62.IMA Vol. Math. Appl.,159Springer, [Cham], 2016

work page 2016
[21]

Chebyshev Polynomial of the First Kind

Weisstein, Eric W. “Chebyshev Polynomial of the First Kind.” From MathWorld–A Wolfram Resource.https://mathworld.wolfram.com/ChebyshevPolynomialoftheFirstKind.html, ac- cessed 14 Apr 2026

work page 2026
[22]

Chebyshev Polynomial of the Second Kind

Weisstein, Eric W. “Chebyshev Polynomial of the Second Kind.” From MathWorld–A Wol- fram Resource.https://mathworld.wolfram.com/ChebyshevPolynomialoftheSecondKind.html, accessed 14 Apr 2026. AppendixA.Chebyshev polynomials The Chebyshev polynomials of the first kind (see [21]) obey the identity cos nθ = Tn cosθ . The Chebyshev polynomials of the second ki...

work page 2026

[1] [1]

4, 451–476

Noga Alon, Eldar Fischer, Michael Krivelevich, and M´ ari´ o Szegedy, Efficient testing of large graphs.Combinatorica20(2000), no. 4, 451–476

work page 2000

[2] [2]

1, 87–104

Noga Alon and Uri Stav, What is the furthest graph from a hereditary property?.Random Structures Algorithms33(2008), no. 1, 87–104

work page 2008

[3] [3]

Graph Theory58(2008), no

Maria Axenovich, Andr´ e K´ ezdy, and Ryan Martin, On the editing distance of graphs.J. Graph Theory58(2008), no. 2, 123–138

work page 2008

[4] [4]

Multicolor and directed edit distance

Maria Axenovich and Ryan R. Martin, Multicolor and directed edit distance. https://arxiv.org/abs/1106.2870, accessed 20 Apr 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026

[5] [5]

J´ ozsef Balogh and Ryan Martin, Edit distance and its computation.Electron. J. Combin.15 (2008), no. 1, Research Paper 20, 27 pp

work page 2008

[6] [6]

Martin, and Daniel McGinnis, Accumulation points of the edit distance function.Discrete Math.345(2022), no

Christopher Cox, Ryan R. Martin, and Daniel McGinnis, Accumulation points of the edit distance function.Discrete Math.345(2022), no. 7, Paper No. 112857, 17pp

work page 2022

[7] [7]

Paul Erd˝ os and Alfr´ ed R´ enyi, On random graphs. I.Publ. Math. Debrecen6(1959), 290–297

work page 1959

[8] [8]

Tibor Gallai, Transitiv orientierbare Graphen.Acta Math. Acad. Sci. Hungar.18(1967), 25–66

work page 1967

[9] [9]

Gilbert, Random graphs.Ann

Edgar N. Gilbert, Random graphs.Ann. Math. Statist.30(1959), 1141–1144

work page 1959

[10] [10]

Math.244(2018), 89–93

Marc Glen, Sergey Kitaev, and Artem Pyatkin, On the representation number of a crown graph.Discrete Appl. Math.244(2018), 89–93

work page 2018

[11] [11]

Halld´ orsson, Sergey Kitaev, and Artem Pyatkin, Semi-transitive orientations and word-representable graphs.Discrete Appl

Magn´ us M. Halld´ orsson, Sergey Kitaev, and Artem Pyatkin, Semi-transitive orientations and word-representable graphs.Discrete Appl. Math.201(2016), 164–171

work page 2016

[12] [12]

Zion Hefty, Paul Horn, Colby Muir, and Andrew Owens, Word-representation numbers of graphs: Bottlenecks and bounds, J. Combin. Th. Ser. A,223(2026), Paper No. 106215, 25pp

work page 2026

[13] [13]

Developments in Language Theory, 36–67

Sergey Kitaev, A comprehensive introduction to the theory of word-representable graphs. Developments in Language Theory, 36–67. Lecture Notes in Comput. Sci.,10396Springer, Cham, 2017

work page 2017

[14] [14]

Sergey Kitaev and Artem Pyatkin, On representable graphs.J. Autom. Lang. Comb.13 (2008), no. 1, 45–54

work page 2008

[15] [15]

Sergey Kitaev and Steven Seif, Word problem of the Perkins semigroup via directed acyclic graphs.Order25(2008) 3, 177–194

work page 2008

[16] [16]

Sergey Kitaev and Vadim Lozin,Words and Graphs, Springer Monographs in Mathematics, Springer, Cham, 2015

work page 2015

[17] [17]

Bolyai Soc

Edward Marchant and Andrew Thomason, Extremal graphs and multigraphs with two weighted colours.Fete of combinatorics and computer science, 239–286. Bolyai Soc. Math. Stud.,20J´ anos Bolyai Mathematical Society, Budapest, 2010

work page 2010

[18] [18]

Ryan Martin, The edit distance function and symmetrization,Electron. J. Combin.20(2013), no. 3, Paper 26, 25pp

work page 2013

[19] [19]

Martin and Alex W.N

Ryan R. Martin and Alex W.N. Riasanovsky, On the edit distance function of the random graph.Combin. Probab. Comput.31(2022), no. 2, 345–367

work page 2022

[20] [20]

Martin, The edit distance in graphs: methods, results, and generalizations.Recent trends in combinatorics, 31–62.IMA Vol

Ryan R. Martin, The edit distance in graphs: methods, results, and generalizations.Recent trends in combinatorics, 31–62.IMA Vol. Math. Appl.,159Springer, [Cham], 2016

work page 2016

[21] [21]

Chebyshev Polynomial of the First Kind

Weisstein, Eric W. “Chebyshev Polynomial of the First Kind.” From MathWorld–A Wolfram Resource.https://mathworld.wolfram.com/ChebyshevPolynomialoftheFirstKind.html, ac- cessed 14 Apr 2026

work page 2026

[22] [22]

Chebyshev Polynomial of the Second Kind

Weisstein, Eric W. “Chebyshev Polynomial of the Second Kind.” From MathWorld–A Wol- fram Resource.https://mathworld.wolfram.com/ChebyshevPolynomialoftheSecondKind.html, accessed 14 Apr 2026. AppendixA.Chebyshev polynomials The Chebyshev polynomials of the first kind (see [21]) obey the identity cos nθ = Tn cosθ . The Chebyshev polynomials of the second ki...

work page 2026