GRAPHS CONTAINING FINITE INDUCED PATHS OF UNBOUNDED

Abstract

The age 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 G0 with the same property admits an embedding of G. We construct 2@ 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

-

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 G0 with infinite detour embeds admits an embedding of G. Let nPn respectively Pn Pn be the direct sum, respectively the complete sum of paths Pn. These graphs are path-minimal graphs. There are others. Our main result is this.

Theorem 1 There are 2@ 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@ 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? 21. 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 ⌘ whose blocks are paths in such a way that (G, ⌘ ) 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 dG(x, y) the length of the shortest path joining x and y if any, and dG(x, y) := +1 otherwise. This defines a distance on V with values in the completion N+ := N+ [ { +1} of non-negative integers. This distance is the graphic distance. If A is a subset of V , the graph G0 induced by G on A is an isometric subgraph of G if dG0 (x, y) = dG(x, y) for all x, y 2 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@ 0 examples, none of them being equimorphic to a prime one. We construct also 2@ 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 N is a sequence u := (u(n))n2 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 Pu, the path on 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 ? on {0, 1}. Define the lexicographical sum of copies of Pu over the chain ! , denoted by Pu ·? ! , and made of pairs (i, v) 2 ! ⇥ Pu, with an edge between two vertices (i, n) and (j, m) of Pu↵ ·? ! , such that i < j, if u(n) ? u(m) = 1. Since u is uniformly recurrent, the set F ac(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 Pu and of G(u,?) := Pu ·? ! are wqo. Deleting the loops, we get a graph that we denote Gb(u,?) and whose age is also wqo. Let Qb(u,?) be the restriction of Gb(u,?) to the set {(m, n) : n < m + 4} of V := N ⇥ N. This restriction has the same age as Gb(u,?) and it is path-minimal. If the operation ? is constant and equal to 0, respectively equal to 1, Qb(u,?) 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@ 0 words u such that the ages of Gb(u,?) 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 Gb(u,?) is contained in some projection (subset of the form {i} ⇥ N). This is a rather technical fact. We think that it holds for any operation. We deduce that if F ac(u) and F ac(u0) are not equal up to reversal or to addition (mod 2) of the constant word 1 the ages of Gb(u,?) and Gb(u0,?) are incomparable w.r.t. set inclusion. To complete the proof of Theorem 1, we then use the fact that there are 2@ 0 uniformly recurrent words u↵ on the two-letter alphabet {0, 1} such that for ↵ 6= the collections F ac(u↵ ) and F ac(u ) 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. Ko ˝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 .