# Graphs containing finite induced paths of unbounded length

Maurice Pouzet, Imed Zaguia

► To cite this version:

Maurice Pouzet, Imed Zaguia. Graphs containing finite induced paths of unbounded length. "Alge-
bras, graphs and ordered sets" (ALGOS 2020), Aug 2020, Vandoeuvre-lès-Nancy, France. pp.37-40.
hal-04762432

HAL Id: hal-04762432

https://hal.science/hal-04762432v1

Submitted on 31 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
GRAPHS CONTAINING FINITE INDUCED PATHS OF UNBOUNDED
LENGTH

Maurice Pouzet

Univ. Lyon, Université Claude-Bernard Lyon1
CNRS UMR 5208, Institut Camille Jordan
43, Bd. du 11 Novembre 1918, 69622
Villeurbanne, France
et

Department of Mathematics and Statistics
University of Calgary, Calgary, Alberta, Canada
pouzet@univ-lyon1.fr

Imed Zaguia*

*Department of Mathematics & Computer Science
Royal Military College of Canada
P.O.Box 17000, Station Forces
Kingston, Ontario, Canada K7K 7B4 zaguia@rmc.ca

ABSTRACT

The age $\mathcal{A}(G)$ of a graph $G$ (undirected and without loops) is the collection of finite induced subgraphs of $G$, considered up to isomorphy and ordered by embeddability. It is well-quasi-ordered (wqo) for this order if it contains no infinite antichain. A graph is *path-minimal* if it contains finite induced paths of unbounded length and every induced subgraph $G'$ with the same property admits an embedding of $G$. We construct $2^{\mathbb{N}_0}$ path-minimal graphs whose ages are pairwise incomparable with set inclusion and which are wqo. Our construction is based on uniformly recurrent sequences and lexicographical sums of labeled graphs.

**Keywords** (partially) ordered set · incomparability graph · graphical distance · isometric subgraph · paths · well quasi order · symbolic dynamic · sturmian words · uniformly recurrent sequences

# 1 Introduction and presentation of the results

We consider graphs that are undirected, simple and have no loops. Let $H = (X, F)$ be a graph and let $(G_x = (V_x, E_x))_{x \in X}$ be a family of graphs whose vertex sets are pairwise disjoint. The *lexicographical sum of* $(G_x)_{x \in X}$ (over the graph $H$) is the graph $H[G_x, x \in X]$ whose vertex set is $\cup_{x \in X} V_x$ and two vertices $u_x$ and $v_{x'}$ are adjacent if $x = x'$ and $\{u_x, v_{x'}\} \in E_x$ or $x \neq x'$ and $\{x, x'\} \in F$. If $H$ is empty i.e. $F = \emptyset$, the lexicographical sum is called a *direct sum*. Else if $H$ is a complete graph, then the lexicographical sum is called the *complete sum*.

Among those graphs with finite induced paths of unbounded length, we ask which one are unavoidable. If a graph is an infinite path, it can be avoided: it contains a direct sum of finite paths of unbounded length. This latter one, on the other hand, cannot be avoided. Indeed, two direct sums of finite paths of unbounded length embed in each other. Similarly, two complete sums of finite paths of unbounded length embed in each other. Hence, the direct sum, respectively the complete sum of finite paths of unbounded length are, in our sense, unavoidable. Are there other examples? This question is the motivation behind this article.

We recall that the *age* of a graph *G* is the collection *Age*(*G*) of finite induced subgraphs of *G*, considered up to isomorphy and ordered by embeddability (cf. [7]). It is *well-quasi-ordered* (wqo) for this order if it contains no infinite antichain. A *path* is a graph *P* such that there exists a one-to-one map *f* from the set *V*(*P*) of its vertices into an interval *I* of the chain *Z* of integers in such a way that {*u*, *v*} belongs to *E*(*P*), the set of edges of *P*, if and only if |*f*(*u*) − *f*(*v*)| = 1 for every *u*, *v* ∈ *V*(*P*). If *I* = {1, ..., *n*}, then we denote that path by *P*<sub>*n*</sub>; its *length* is *n* − 1, so, if *n* = 2, *P*<sub>2</sub> is made of a single edge, whereas if *n* = 1, *P*<sub>1</sub> is a single vertex. We denote by *P*<sub>∞</sub> the path on N. The *detour* of a graph *G* [4] is the supremum of the length of induced paths included in *G*. Our aim is to give a structural

<footnote>*Corresponding author. Supported by Canadian Defence Academy Research Program (CDARP) and NSERC DDG-2018-00011.
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).</footnote>
result on graphs with infinite detour (for the existence of infinite paths we refer to [14, 19, 27]). We say that a graph $G$ is path-minimal if its detour is infinite end every induced subgraph $G'$ with infinite detour embeds admits an embedding of $G$. Let $\oplus_n P_n$ respectively $\sum_n P_n$ be the direct sum, respectively the complete sum of paths $P_n$. These graphs are path-minimal graphs. There are others. Our main result is this.

**Theorem 1** *There are $2^{\aleph_0}$ path-minimal graphs whose ages are pairwise incomparable and wqo.*

Our construction uses uniformly recurrent sequences, and in fact Sturmian sequences (or billiard sequences) [17, 6], and lexicographical sums of labelled graphs. The existence of $2^{\aleph_0}$ wqo ages is a non trivial fact. It was obtained for binary relations in [21] and for undirected graphs in [24] and in [25]. The proofs were based on uniformly recurrent sequences. These sequences were also used in [15].

We leave open the following:

**Problems 1** [(i)]

*If a graph admits an embedding of finite induced path of unbounded length, does it embed a path-minimal graph?*

2. If a graph is path-minimal, is its age wqo?

3. If a graph $G$ is path-minimal, can $G$ be equipped with an equivalence relation $\equiv$ whose blocks are paths in such a way that $(G, \equiv)$ is path-minimal?

In some situations there are only two path-minimal graphs (up to equimorphy).

**Theorem 2** *If the incomparability graph of a poset admits an embedding of finite induced paths of unbounded length, then it admits an embedding of the direct sum or the complete sum of finite induced paths of unbounded length.*

If $G := (V, E)$ is a graph, and $x, y$ are two vertices of $G$, we denote by $d_G(x, y)$ the length of the shortest path joining $x$ and $y$ if any, and $d_G(x, y) := +\infty$ otherwise. This defines a distance on $V$ with values in the completion $\overline{N}^+ := N^+ \cup \{+\infty\}$ of non-negative integers. This distance is the *graphic distance*. If $A$ is a subset of $V$, the graph $G'$ induced by $G$ on $A$ is an *isometric subgraph* of $G$ if $d_{G'}(x, y) = d_G(x, y)$ for all $x, y \in A$.

If instead of induced path we consider isometric paths, then

**Theorem 3** *If a graph admits an embedding of isometric finite paths of unbounded length, then it admits an embedding of a direct sum of such paths.*

We examine the primality of the graphs we obtain. Prime (or indecomposable) graphs are the building blocks of the construction of graphs ([2, 8, 9, 11, 12, 23, 26]). Direct and complete sums of finite paths of unbounded length are not prime and not equimorphic to prime graphs. We construct $2^{\aleph_0}$ examples, none of them being equimorphic to a prime one. We construct also $2^{\aleph_0}$ which are prime. These examples are minimal in the sense of [22], but not in the sense of [23] nor in the sense of [18] p. 92.

We conclude this introduction with:

**1.0.1 An outline of the proof of Theorem 1**

It uses two main ingredients. One is the so called uniformly recurrent sequences (or words).

A *uniformly recurrent* word with domain $\mathbb{N}$ is a sequence $u := (u(n))_{n \in \mathbb{N}}$ of letters such that for any given integer $n$ there is some integer $m(u, n)$ such that every factor $v$ of $u$ of length at most $n$ appears as a factor of every factor of $u$ of length at least $m(u, n)$. [1, 3, 16, 6]. To a uniformly recurrent word $u$ on the alphabet $\{0, 1\}$ we associate $P_u$, the path on $\mathbb{N}$ with a loop at every vertex $n$ for which $u(n) = 1$ and no loop at vertices for which $u(n) = 0$. Next comes the second ingredient.

Fix a binary operation $\star$ on $\{0, 1\}$. Define the lexicographical sum of copies of $P_u$ over the chain $\omega$, denoted by $P_{u, \omega} \star \omega$, and made of pairs $(i, v) \in \omega \times P_u$, with an edge between two vertices $(i, n)$ and $(j, m)$ of $P_{u, \omega} \star \omega$, such that $i < j$, if $u(n) \star u(m) = 1$. Since $u$ is uniformly recurrent, the set $\text{Fac}(u)$ of finite factors of $u$ is wqo w.r.t the factor ordering, hence by a theorem of Higman [10] (see also [20]), the ages of $P_u$ and of $G_{(u, \star)} := P_{u, \star} \omega$ are wqo. Deleting the loops, we get a graph that we denote $\hat{G}_{(u, \star)}$ and whose age is also wqo. Let $\hat{Q}_{(u, \star)}$ be the restriction of $\hat{G}_{(u, \star)}$ to the set $\{(m, n) : n < m + 4\}$ of $V := \mathbb{N} \times \mathbb{N}$. This restriction has the same age as $\hat{G}_{(u, \star)}$ and it is path-minimal. If the
operation ⋆ is constant and equal to 0, respectively equal to 1, $\hat{Q}_{(u,\star)}$ is a direct sum, respectively a complete sum of paths. To conclude the proof of the theorem, we need to prove that there is some operation ⋆ and $2^{\mathbb{N}_0}$ words $u$ such that the ages of $\hat{G}_{(u,\star)}$ are incomparable. This is the substantial part of the proof. For that, we prove that if ⋆ is the Boolean sum or a projection and $u$ is uniformly recurrent then every long enough path in $\hat{G}_{(u,\star)}$ is contained in some projection (subset of the form $\{i\} \times \mathbb{N}$). This is a rather technical fact. We think that it holds for any operation. We deduce that if $\mathrm{Fac}(u)$ and $\mathrm{Fac}(u')$ are not equal up to reversal or to addition (mod 2) of the constant word 1 the ages of $\hat{G}_{(u,\star)}$ and $\hat{G}_{(u',\star)}$ are incomparable w.r.t. set inclusion. To complete the proof of Theorem 1 we then use the fact that there are $2^{\mathbb{N}_0}$ uniformly recurrent words $u_\alpha$ on the two-letter alphabet $\{0,1\}$ such that for $\alpha \neq \beta$ the collections $\mathrm{Fac}(u_\alpha)$ and $\mathrm{Fac}(u_\beta)$ of their finite factors are distinct, and in fact incomparable with respect to set inclusion (this is a well-known fact of symbolic dynamic, e.g. Sturmian words with different slopes will do [6], Chapter 6 page 143).

The proofs will appear in the full version of the paper.

## References

[1] J-P. Allouche and J. Shallit, *Automatic Sequences: Theory, Applications, Generalizations*. Cambridge University Press, 2003; ISBN: 0-521-82332-3

[2] R. Assous, M. Pouzet, *Jónsson posets*, Algebra Universalis, 79 (2018) no. 3, Art. 74, 26 pp.

[3] V. Berthé and M. Rigo eds. *Combinatorics, automata, and number theory*. Encyclopedia of Mathematics and its Applications. 135. 2010, Cambridge: Cambridge University Press. ISBN 978-0-521-51597-9.

[4] F. Buckley and F. Harary, *On longest induced paths in graphs*. Chinese Quart. J. Math., **3** (3), (1968) 61–65.

[5] A. Ehrenfeucht, T. Harju, G. Rozenberg, *The theory of 2-structures. A framework for decomposition and transformation of graphs*. World Scientific Publishing Co., Inc., River Edge, NJ, 1999.

[6] N. Pytheas Fogg, *Substitutions in dynamics, arithmetics and combinatorics*, Valérie Berthé, Sébastien Ferenczi, Christian Mauduit and Anne Siegel, eds., Lecture Notes in Mathematics. 1794. Berlin: Springer-Verlag, 2002.

[7] R. Fraïssé, *Theory of relations*. Revised edition. With an appendix by Norbert Sauer. Studies in Logic and the Foundations of Mathematics, 145. North-Holland Publishing Co., Amsterdam, 2000. ii+451.

[8] R. Fraïssé, *L'intervalle en théorie des relations, ses généralisations, filtre intervallaires et clôture d'une relation*, In "Orders, description and roles", M. Pouzet and D. Richard(éd), Annals of Discrete Math., **23** (1984), 343–358.

[9] T. Gallai, *Transitiv orientierbare Graphen*, Acta Math. Acad. Sci. Hungar., **18** (1967), 25–66 (English translation by F. Maffray and M. Preissmann in J.J. Ramirez-Alfonsin and B. Reed (Eds), *Perfect graphs*, Wiley 2001, pp. 25–66).

[10] G. Higman, *Ordering by divisibility in abstract algebras*. Proc. London Math. Soc. **3** (1952), 326–336.

[11] P. Ille, *A characterization of the indecomposable and infinite graphs*, Glob. J. Pure Appl. Math., **3**, (2005) 272–285.

[12] D. Kelly, *Comparability graphs*, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., **147** (1985), 3–40.

[13] K. Kearnes, G. Oman, *Jónsson posets and unary Jónsson algebras*, Algebra Universalis **69** (2013), no. 2, 101–112.

[14] D. Kőnig, *Über eine Schlussweise aus dem Endlichen ins Unendliche*, Acta Sci. Math. (Szeged) (in German) (3(2-3)): (1927), 121–130.

[15] C. Laflamme, M. Pouzet, N. Sauer, I. Zaguia, *Orthogonal countable ordinals*, Discrete Math. **335**(2014) 35-44.

[16] M. Lothaire, *Finite and Infinite Words*. In Algebraic Combinatorics on Words (Encyclopedia of Mathematics and its Applications, pp. 1-44). Cambridge: Cambridge University Press, 2002. doi:10.1017/CBO9781107326019.002

[17] M. Morse and G. A. Hedlund, *Symbolic Dynamics II. Sturmian Trajectories*. American Journal of Mathematics. **62** (1940): 1–42.

[18] D. Oudrar, *Sur l'énumération de structures discrètes: une approche par la théorie des relations*. Thèse de doctorat, Université d'Alger USTHB à Bab Ezzouar, 28 sept. 2015, ArXiv:1604.05839.

[19] N. Polat, *Graphs Without Isometric Rays and Invariant Subgraph Properties, I*, Journal of Graph Theory, Volume 27, Issue 2, (1998), 99–109.

[20] M. Pouzet, *Un belordre d'abritement et ses rapports avec les bornes d'une multirelation. Comptes rendus Acad. Sci. Paris **274**(A) (1972), pp. 1677–1680.*

[21] M. Pouzet, *Sur la théorie des relations*, Thèse de doctorat d'État, Université Claude-Bernard, Lyon, 23 Janvier 1978.
[22] M. Pouzet, *Relation minimale pour son âge*, Zeitsch. f. math. Logik und Grundlag d. Math. Bd. 25, S. 315-344 (1979).

[23] M. Pouzet and I. Zaguia, *On Minimal Prime Graphs and Posets*, Order **16** (2009), 357-375.

[24] M. Sobrani, *Structure d'ordre de la collection des âges de relations*, Thèse de doctorat, Université Claude-Bernard, Lyon, 18 déc. 1992.

[25] M. Sobrani, *Sur les âges de relations et quelques aspects homologiques des constructions D+M*, Thèse de doctorat d'état, Université S.M.Ben Abdallah-Fez, Fez, January 2002.

[26] D.P. Sumner, *Graphs indecomposable with respect to the X-join*, Discrete Math., **6** (1973), 281-298.

[27] M.E. Watkins, *Infinite paths that contain only shortest paths*, Journal of Combinatorial Theory, Series B Volume 41, Issue 3, December 1986, 341-355.