The edit distance of word-representable and comparability graphs
Sergey Kitaev, Ryan R. Martin · 2026
Read The edit distance of word-representable and comparability graphs by Sergey Kitaev, Ryan R. Martin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18308.txt.
Introduction
In their 2026 paper, Sergey Kitaev and Ryan Martin determine how far an arbitrary graph can sit from two hereditary families, word-representable graphs and poset comparability graphs. The maximum edit distance reaches one eighth of n squared for word-representable graphs and five thirty-seconds of n squared for comparability graphs, ignoring lower-order terms. They also map the full edit-distance function across all edge densities, including k-word-representable graphs.
Catalog record
| CREATOR | Sergey Kitaev, Ryan R. Martin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 74946 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.18308
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The edit distance of word-representable and comparability graphs Sergey Kitaev, Ryan R. Martin Abstract . In this paper, we establish that the maximum edit distance of an n n -vertex graph from the hereditary property of word-representable graphs is n 2 / 8 − o ( n 2 ) n^{2}/8-o(n^{2}) . In addition, we establish that the maximum edit distance of an n n -vertex graph from the hereditary property of poset comparability graphs is 5 n 2 / 32 − o ( n 2 ) 5n^{2}/32-o(n^{2}) . In fact, we determine the edit distance function over all edge densities p ∈ [ 0 , 1 ] p\in[0,1] for the property of word-representable graphs, for the property of k k -word-representable graphs for each k ≥ 2 k\geq 2 , and for the property comparability graphs. The latter has a peculiar structure that requires an infinite sequence of colored regularity graphs. 2020 Mathematics Subject Classification 05C35,05C62 1. Introduction 1.1. Word representation of graphs Word representations of graphs enable one to encode a graph as a string and were introduced by Pyatkin and the first author [ 14 ] . A word-representation of a graph G=(V,E) is a word over the alphabet V such that vertices v_{1} and v_{2} are adjacent in G if and only if they alternate in the word. A graph G is said to be k -word-representable if there exists a word representing G that contains exactly k copies of each letter, that is, a k -uniform word. It was shown in [ 14 ] that a graph is word-representable if and only if it is k -word-representable for some positive integer k . This allows one to define the representation number of a word-representable graph G , denoted by {\mathcal{R}}(G) , as the smallest positive integer k such that G is k -word-representable. By definition, {\mathcal{R}}(G)=\infty for any non-word-representable graph. 1.2. Comparability graphs The comparability digraph of a finite poset P , denoted D_{P} is a directed graph where the vertex set is the elements of P and x\rightarrow_{D_{P}}y is a directed edge if and only if x<_{P}y . The comparability graph of a finite poset P is simply the underlying graph of its comparability digraph. There is a strong connection between comparability graphs and word-representable graphs, as indicated in [ 14 ] . Namely, if a graph is word-representable, then the neighbourhood of any vertex in it must be a comparability graph. The converse of this statement is not true [ 16 ] . It is known [ 15 ] that every comparability graph can be represented by a concatenation of permutations. 1.3. Hereditary properties of graphs A property of graphs is hereditary if it is closed under isomorphism and deleting vertices. That is, if H is in a hereditary property {\mathcal{H}} , then every induced subgraph of H is also in {\mathcal{H}} . For a graph F , let {\rm Forb}(F) denote the hereditary property of graphs with no induced copy of F . For a set of graphs {\mathcal{F}} , let {\rm Forb}({\mathcal{F}}) denote the hereditary property of graphs with no induced copy of F for any F\in{\mathcal{F}} . That is, {\rm Forb}({\mathcal{F}})=\bigcap_{F\in{\mathcal{F}}}{\rm Forb}(F) . In fact, for every hereditary property {\mathcal{H}} , there exists a (possibly infinite) set {\mathcal{F}}({\mathcal{H}}) such that {\mathcal{H}}=\bigcap_{F\in{\mathcal{F}}({\mathcal{H}})}{\rm Forb}(F) . A hereditary property is trivial if it is finite, otherwise it is nontrivial . By Ramsey theory, a hereditary property {\mathcal{H}} is trivial if and only if there are positive integers a and b such that {\mathcal{H}}\subseteq{\rm Forb}\bigl(K_{a}\bigr)\cap{\rm Forb}\bigl(\overline{K_{b}}\bigr) . 1.4. The edit distance in graphs The edit distance between graphs G and H on the same labeled vertex set of size n is {\rm dist}(G,H)\stackrel{{\scriptstyle\rm def}}{{=}}\bigl|E(G)\triangle E(H)\bigr|/{\textstyle\binom{n}{2}}, where, in this case the \triangle notation denotes the symmetric difference. The edit distance between a graph G and hereditary property {\mathcal{H}} is {\rm dist}(G,{\mathcal{H}})\stackrel{{\scriptstyle\rm def}}{{=}}\min\bigl\{{\rm dist}(G,H):H\in{\mathcal{H}},V(H)=V(G)\bigr\}. The edit distance of a hereditary property {\mathcal{H}} is {\rm dist}(n,{\mathcal{H}})\stackrel{{\scriptstyle\rm def}}{{=}}\max\bigl\{{\rm dist}(G,{\mathcal{H}}):|V(G)|=n\bigr\}. The study of the edit distance in graphs was developed simultaneously by Axenovich, Kézdy and the second author [ 3 ] , by Alon and Stav [ 2 ] , and (in a different context) by Marchant and Thomason [ 17 ] . The edit distance function was introduced by Balogh and the second author [ 5 ] . Definition 1 (Balogh-M. [ 5 ] ) . The edit distance function of a hereditary property {\mathcal{H}} is a function of p\in[0,1] , is denoted {\rm ed}_{{\mathcal{H}}}(p) , and is defined to be {\rm ed}_{{\mathcal{H}}}(p)=\lim_{n\rightarrow\infty}\max\bigl\{{\rm dist}\bigl(G,{\mathcal{H}}\bigr):\bigl|V(G)]\bigr|=n,\bigl|E(G)\bigr|=\bigl\lfloor p{\textstyle\binom{n}{2}}\bigr\rfloor\bigr\}. The limit was proven to exist in [ 5 ] . Theorem 2 (Balogh–M. [ 5 ] ) . Let {\mathcal{H}} be a nontrivial hereditary property. If G(n,p) denotes the binomial Erdős–Rényi random graph [ 7 ] 1 1 1 In fact, this binomial model of the random graph is due to Gilbert [ 9 ] . , then {\rm ed}_{{\mathcal{H}}}(p)=\lim_{n\rightarrow\infty}\mathbb{E}\bigl[{\rm dist}\bigl(G(n,p),{\mathcal{H}}\bigr)\bigr]. Furthermore, for every p\in[0,1] , the quantity {\rm dist}\bigl(G(n,p),{\mathcal{H}}\bigr) is concentrated around its mean. That is, for every \epsilon>0 , \mathbb{P}\Bigl(\bigl|{\rm dist}\bigl(G(n,p),{\mathcal{H}}\bigr)-\mathbb{E}\bigl[{\rm dist}\bigl(G(n,p),{\mathcal{H}}\bigr)\bigr]\bigr|>\epsilon\Bigr)\rightarrow 0 as n\rightarrow\infty . Let {\mathcal{H}}_{\rm word} denote the hereditary property of word-representable graphs. For a positive integer k , let {\mathcal{H}}_{k{\rm-word}} denote the hereditary property of k -word-representable graphs. Note that, according to the way the term is defined, an induced subgraph of a k -word-representable graph also has a k -representation, thus {\mathcal{H}}_{k{\rm-word}} is, indeed, a hereditary property. Let {\mathcal{H}}_{\rm comp} denote the hereditary property of comparability graphs. Hefty, Horn, Muir, and Owens [ 12 ] established that {\rm dist}\bigl(n,{\mathcal{H}}_{\rm word}\bigr)=\Omega\bigl(n^{2}\bigr) . In this paper, we asymptotically resolve the value of {\rm dist}\bigl(n,{\mathcal{H}}_{\rm word}\bigr) by proving the following: Theorem 3 . For all p\in[0,1] , {\rm ed}_{{\mathcal{H}}_{\rm word}}(p)=\min\bigl\{p/3,1-p\bigr\} . Consequently, {\rm dist}\bigl(n,{\mathcal{H}}_{\rm word}\bigr)=\tfrac{1}{4}{\textstyle\binom{n}{2}}-o\bigl(n^{2}\bigr) . Moreover, if {\rm dist}\bigl(G,{\mathcal{H}}_{\rm word})\geq\bigl(\tfrac{1}{4}-\epsilon\bigr){\textstyle\binom{n}{2}} , then \bigl|E(G)\bigr|/{\textstyle\binom{n}{2}}\in\bigl[\tfrac{3}{4}-3\epsilon,\tfrac{3}{4}+\epsilon\bigr] . We also know the edit distance function for {\mathcal{H}}_{k{\rm-word}} , the property of being k -word-representable. Theorem 4 . Let k\geq 2 . For all p\in[0,1] , {\rm ed}_{{\mathcal{H}}_{k{\rm-word}}}(p)=\min\bigl\{p,1-p\bigr\} . Consequently, \displaystyle{\rm dist}\bigl(n,{\mathcal{H}}_{k{\rm-word}}\bigr)=\tfrac{1}{2}{\textstyle\binom{n}{2}}-o\bigl(n^{2}\bigr) . Moreover, if {\rm dist}\bigl(G,{\mathcal{H}}_{k{\rm-word}})\geq\bigl(\tfrac{1}{2}-\epsilon\bigr){\textstyle\binom{n}{2}} , then \bigl|E(G)\bigr|/{\textstyle\binom{n}{2}}\in\bigl[\tfrac{1}{2}-\epsilon,\tfrac{1}{2}+\epsilon\bigr] . We note that the result is the same for any k\geq 2 . As far as {\mathcal{H}}_{1{\rm-word}} , the only 1-word-representable graphs are complete graphs and so {\rm dist}\bigl(G,{\mathcal{H}}_{1{\rm-word}}\bigr)=\binom{n}{2}-|E(G)| for any graph G on n vertices. Finally, we address the hereditary property of comparability graphs, denoted {\mathcal{H}}_{\rm comp} . Definition 5 . For every integer k\geq 2 , let p_{k} satisfy \frac{2p_{k}-1}{1-p_{k}}=2\cos\bigl(\frac{2\pi}{k+1}\bigr) . Equivalently, p_{k}=1-1/\bigl(2\cos\bigl(\frac{2\pi}{k+1}\bigr)+2\bigr) . Observe that p_{2}=0 , p_{3}=1/2=0.5 , p_{4}=\bigl(\sqrt{5}-1\bigr)/2\approx 0.618 , p_{5}=2/3\approx 0.667 , p_{6}\approx 0.692 , p_{7}=\sqrt{2}/2\approx 0.707 and so on. Furthermore the sequence \{p_{k}\}_{k\geq 2} increases to a limit of 3/4 . Theorem 6 . There is a sequence of functions g_{2}(p)=p/2,g_{3}(p)=\frac{p}{1+2p},g_{4}(p)=\frac{-1+3p-p^{2}}{6p-2},g_{5}(p)=\frac{-2+4p-p^{3}}{-4+6p+3p^{2}},g_{6}(p),g_{7}(p),\ldots such that for all p\in[0,1] , \textstyle{\rm ed}_{{\mathcal{H}}_{\rm comp}}(p)=\min\bigl\{\frac{p}{2},\frac{p}{1+2p},\frac{-1+3p-p^{2}}{6p-2},\frac{-2+4p-p^{3}}{-4+6p+3p^{2}},g_{6}(p),g_{7}(p),\ldots,1-p\bigr\}. Furthermore, for each k\geq 2 , {\rm ed}_{{\mathcal{H}}_{\rm comp}}(p)=g_{k}(p) for p\in\bigl(p_{k},p_{k+1}\bigr] and {\rm ed}_{{\mathcal{H}}_{\rm comp}}(p)=1-p for p\in\bigl[3/4,1\bigr] . Consequently, {\rm dist}\bigl(n,{\mathcal{H}}_{\rm comp}\bigr)=\tfrac{5}{18}{\textstyle\binom{n}{2}}-o\bigl(n^{2}\bigr) and the maximum of {\rm ed}_{{\mathcal{H}}_{\rm comp}}(p) occurs at p=p_{5}=2/3 . Moreover, if \epsilon\in(0,0.001) and {\rm dist}\bigl(G,{\mathcal{H}}_{\rm comp})\geq\bigl(\tfrac{5}{18}-\epsilon\bigr){\textstyle\binom{n}{2}} , then \bigl|E(G)\bigr|/{\textstyle\binom{n}{2}}\in\bigl(\tfrac{2}{3}-\sqrt{2\epsilon},\tfrac{2}{3}+12\epsilon\bigr) . 2. Techniques for computing the edit distance function The key objects in computing the edit distance function were called colored regularity graphs (CRGs) by Alon and Stav [