Infinite grids in digraphs
Matthias Hamann †, Karl Heuer · 2024
Read Infinite grids in digraphs by Matthias Hamann †, Karl Heuer (2024) 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-2412-03302.txt.
Introduction
Matthias Hamann and Karl Heuer present a 2024 mathematics paper on infinite directed graphs. In ordinary graphs, a classic result by Halin says that an end holding endlessly many separate rays must contain a copy of an infinite quarter grid. The pair ask whether the same holds when every edge has a direction.
They prove that it does: any directed graph with an end rich in disjoint directed rays contains a subdivided grid-like pattern whose rays all belong to that end. The proof extends a well-known tool from graph theory into the directed setting. Results like this help mathematicians map the large-scale shape of infinite networks and understand how their far ends are built.
Catalog record
| CREATOR | Matthias Hamann †, Karl Heuer |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-03302
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Infinite grids in digraphs Thanks: † Funded by the Deutsche Forschungsgemeinschaft (DFG) - Project No. 549406527. Matthias Hamann †, Karl Heuer Abstract . Halin proved that every graph with an end ω \omega containing infinitely many pairwise disjoint rays admits a subdivision of the infinite quarter-grid as a subgraph where all rays from that subgraph belong to ω \omega . We will prove a corresponding statement for digraphs, that is, we will prove that every digraph that has an end with infinitely many pairwise disjoint directed rays contains a subdivision of a grid-like digraph all of whose directed rays belong to that end. 2020 Mathematics Subject Classification 05C63, 05C20 (primary); 05C38 (secondary) 1. Introduction Halin’s grid theorem [ 4 ] *Satz 4 ′ characterizes ends of graphs that contain infinitely many pairwise disjoint rays , i. e. one-way infinite paths. For this, an end is an equivalence class of rays, where two rays are equivalent if there are infinitely many pairwise disjoint paths between them. A subdivision of a graph G is a graph obtained from G by replacing edges by new paths between the incident vertices of that edge such that the new paths are internally disjoint and have no inner vertex in the vertex set of G . The hexagonal quarter-grid , denoted by H^{\infty} , is the graph in Figure 1.1 . Figure 1.1 . The hexagonal quarter-grid H^{\infty} . Now we are able to state Halin’s theorem. Theorem 1.1 . [ 4 ] *Satz 4 ′ Whenever an undirected graph contains infinitely many pairwise disjoint and equivalent rays, then it contains a subdivision of H^{\infty} . As a first attempt to obtain an analogous result for directed graphs, digraphs for short, Zuther [ 11 ] *Theorem 3.1 proved that, if a digraph has an infinite increasing sequence of distinct ends, each of which contains a ray, then it contains a subdivision of the digraph obtained from H^{\infty} by orienting the horizontal edges to the right and the vertical ones upwards. Here, the ends of digraphs are defined by Zuther [ 10 , 11 ] analogously as equivalence classes of rays and anti-rays, where a ( anti- ) ray is an orientation of a one-way infinite path such that each edge is oriented towards (resp. away from) infinity. (We refer to Section 2 for a precise definition and for the definition of an order on the ends). Our main theorem is the following result, where the bidirected quarter-grid is the digraph in Figure 1.2 and the reversed bidirected quarter-grid is obtained from the bidirected quarter-grid by reversing the direction of all edges. R_{1} R_{2} R_{3} R_{4} Figure 1.2 . The bidirected quarter-grid. Theorem 1.2 . If D is a digraph that contains an end \omega with infinitely many disjoint (anti-)rays, then there exists a subdivision of the (reversed) bidirected quarter-grid in D with all its (anti-)rays in \omega . This theorem follows from a more detailed result (Theorem 4.2 ), which classifies ends containing infinitely many disjoint rays into three different types. The classification will be in terms of recurring auxiliary digraphs which are defined on rays within such a fixed end and encode how these rays are connected to each other. Each classifying term is characterising for the existence of a subdivision of a certain digraph; namely for the bidirected quarter-grid, for a cyclically directed quarter-grid and for a complete ray digraph (see Section 4 for precise definitions of these digraphs). From this point of view, Theorem 4.2 can be seen as an analogous result to [ 2 ] *Theorem 1.2 where a similar classification is proved for ends of undirected graphs. We note that our result is stronger than Zuther’s theorem, since it is possible to find bidirected quarter-grids in Zuther’s grid-like digraphs. (We refer to the end of Section 4 for a discussion how to find bidirected quarter-grids in Zuther’s grid-like digraphs.) Independently, Reich [ 7 ] recently obtained Theorem 1.2 with a slightly different notion of bidirected quarter-grid, which turns out to be equivalent in that his bidirected quarter-grid contains ours as a subdivision and vice versa. Whereas Reich’s proof relies on a detailed analysis of an infinite, strongly connected auxiliary digraph allowing to prescribe a set of rays among which all vertical ones are chosen, ours looks at a sequence of finite, strongly connected digraphs and uses ideas similar to those in [ 6 , 2 ] . In order to investigate that sequence, we prove a result for finite, strongly connected digraphs (Theorem 3.4 ), which might be considered interesting in its own. It can be seen as a directed analogue of the fact that every large enough finite, connected graph contains either a vertex of high degree or a long path. In Section 5 , we will apply Theorem 3.4 also in order to find grid-like structures in ends that only contain finitely many pairwise disjoint rays (anti-rays), see Theorem 5.1 . This paper is structured as follows. After introducing some terminology in Section 2 , we prove the structural result for finite, strongly connected digraphs in Section 3 . In Section 4 , we will prove Theorem 1.2 and, in Section 5 , we will prove the result on ends with only finitely many pairwise disjoint rays or anti-rays. We finish in Section 6 with a discussion of the situation when considering pairwise edge-disjoint rays or anti-rays. 2. Preliminaries For general facts and notation regarding graphs we refer the reader to [ 3 ] , regarding digraphs in particular to [ 1 ] . A digraph D is called strongly connected if for every two vertices u,v\in V(D) there exists a path directed from u to v in D . For the sake of brevity, we call a digraph D strong if it is strongly connected, a directed cycle just a dicycle and a directed path just a dipath . For a dipath P containing two vertices a and b in this order, i. e. such that b is reached from a via P , we denote by aPb the subdipath of P starting at a and ending at b . For two vertex sets A and B , a dipath P is an A – B dipath if P starts in A , ends in B and is internally disjoint from A\cup B . In case A or B is a singleton set, we may omit the set brackets with respect to this notation. A digraph R is called a ray if it has precisely one vertex v with out-degree 1 and in-degree 0 , there exists a dipath from v to each vertex of R , and each vertex distinct from v has out-degree 1 and in-degree 1 . An anti-ray is obtained from a ray by reversing all its edges. The vertex v is called the starting vertex (resp. end vertex ) of the ray (resp. anti-ray). We say that a ray (or anti-ray) starts (ends) in a vertex set A if it has its starting vertex (end vertex) in A . For a ray R with starting vertex v and some x\in V(R) we denote by Rx the subdipath vRx of R . A tail