Antidirected trees in directed graphs

George Kontogeorgiou, Giovanne Santos, Maya Stein · 2025

Read Antidirected trees in directed graphs by George Kontogeorgiou, Giovanne Santos, Maya Stein (2025) 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-2501-11726.txt.

Introduction

George Kontogeorgiou, Giovanne Santos, and Maya Stein prove an embedding theorem for directed graphs in this two thousand twenty-five combinatorics paper. A classic theorem of Komlós, Sárközy, and Szemerédi says dense enough graphs contain every bounded-degree tree of the same order. Later variants shrank the tree relative to the host and added maximum degree conditions, and the theorem was extended to directed graphs. This paper merges those two directions.

The result concerns balanced antidirected trees, oriented trees whose edges alternate direction in a balanced way, with bounded total degree. Under stated conditions on outdegree, indegree, and minimum semidegree of the host digraph, every such tree of the given smaller order must appear inside it. The degree bounds are expressed in terms of the tree's arc count and a level parameter. The work extends extremal graph theory further into the directed setting.

Catalog record

CREATORGeorge Kontogeorgiou, Giovanne Santos, Maya Stein
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-11726

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Antidirected trees in directed graphs Thanks: George Kontogeorgiou was supported by ANID grant CMM Basal FB210005. Giovanne Santos was supported by ANID Becas/Doctorado Nacional 21221049. Maya Stein was supported by ANID Regular Grant 1221905 and by ANID grant CMM Basal FB210005. George Kontogeorgiou, Giovanne Santos, Maya Stein Abstract . By the well-known Komlós-Sárközy-Szemerédi (KSS) theorem, any n n -vertex graph of minimum degree n / 2 + o ⁡ ( n ) n/2+o(n) contains all bounded degree trees of order n n . Several variants of this result have been put forward recently, where the tree is allowed to be of smaller order than the host graph. In these results, the host graph also obeys a maximum degree condition, which is necessary. In a different vein, the KSS theorem was generalised to digraphs. We bring these two directions together by establishing minimum and maximum degree bounds for digraphs that ensure the containment of oriented trees of smaller order. Our result, Theorem 1.5 , is restricted to balanced antidirected trees of bounded degree but may hold for other oriented trees as well. The full statement of Theorem 1.5 can be found below, we will limit ourselves here to state three important implications. First, the result implies that, asymptotically, every large digraph of minimum semidegree above 2 ​ k / 3 2k/3 having vertices of out-degree and in-degree above k k contains each large balanced antidirected bounded-degree tree with k k arcs. These semidegree bounds are essentially best possible, and are identical to bounds in corresponding results for graphs. Second, Theorem 1.5 implies that asymptotically, every large digraph of minimum semidegree above 3 ​ k / 5 3k/5 having vertices of out-degree and in-degree above 2 ​ k 2k contains each large balanced antidirected bounded-degree tree with k k arcs. A bound of k / 2 k/2 instead of 3 ​ k / 5 3k/5 on the minimum semidegree would be tight and is known to be sufficient in corresponding results for graphs and for oriented graphs. Thirdly, our result gives a version of the digraph KSS theorem for smaller trees. We prove that for all k k and ε \varepsilon there is a C C such that every large digraph of minimum semidegree above ( 1 + ε ) ​ k / 2 (1+\varepsilon)k/2 having vertices of out-degree and in-degree above C ​ k Ck contains each large balanced antidirected bounded-degree tree with k k arcs. An exact version of our result for graphs and trees of any maximum degree has been proved recently by Hyde and Reed. 2020 Mathematics Subject Classification 05C20 (primary), 05C07, 05C35 (secondary) 1. Introduction Subgraph containment problems lie at the heart of extremal graph theory. In order to ensure containment of a given subgraph, one of the most widely used conditions on the host graph is a bound on its minimum degree. A famous example is Dirac’s theorem on Hamilton cycles. In this paper we focus on tree subgraphs. One of the best-known theorems in this direction is the Komlós–Sárközy–Szemerédi theorem on spanning trees of bounded maximum degree. Theorem 1.1 (Komlós, Sárközy and Szemerédi [ 7 ] ) . For every \gamma>0 , there exist n_{0}\in\mathbb{N} and c>0 such that every graph G on n\geq n_{0} vertices with \delta(G)\geq(1+\gamma)\frac{n}{2} contains every n -vertex tree T with \Delta(T)\leq c\frac{n}{\log n} . The bounds in Theorem 1.1 are essentially best possible. In particular, the bound on \Delta(T) in Theorem 1.1 is best possible up to the constant c [ 7 ] . If we wish to find all trees T on n -vertices as spanning trees of G , then clearly, G needs to have a vertex of degree at least n-1 , because T could be a star. The existence of just one such vertex is indeed sufficient if we also change the bound on \delta(G) from Theorem 1.1 to about 2n/3 . This is the content of the following result due to Reed and the last author. Theorem 1.2 (Reed and Stein [ 9 , 10 ] ) . There is n_{0}\in\mathbb{N} such that for every n\geq n_{0} , every n -vertex graph with \delta(G)\geq\lfloor{2(n-1)/3}\rfloor and \Delta(G)\geq n-1 contains every n -vertex tree. We are interested in finding smaller trees with corresponding weaker bounds on \delta(G) . One of our motivations is the following conjecture. Conjecture 1.1 (Havet, Reed, Wood and Stein [ 3 ] ) . Every graph of minimum degree at least {\lfloor 2k/3\rfloor} and maximum degree at least k contains every k -edge tree. The bound on \delta(G) in Conjecture 1.1 is best possible, as witnessed by the following example: let T be any k -edge tree having a vertex v such that T-v has three components of exactly the same size. Let G be obtained by taking two cliques of size 2k/3-1 and adding a new vertex adjacent to all vertices of both cliques. Then T is not a subgraph of G . An approximate version of Conjecture 1.1 for large bounded degree trees was proved by Besomi, Pavez-Signé and the last author in [ 2 ] . More generally, these authors proved the following. Theorem 1.3 (Besomi, Pavez-Signé and Stein [ 2 ] ) . For every \gamma>0 there is n_{0}\in\mathbb{N} such that for all n\geq n_{0} and all k\geq\gamma n every n -vertex graph G fulfilling (1) \delta(G)\geq(1+\gamma){k}/{2} and \Delta(G)\geq 2(1+\gamma)k ; or (2) \delta(G)\geq(1+\gamma){2k}/{3} and \Delta(G)\geq(1+\gamma)k contains every k -edge tree T with \Delta(T)\leq k^{{1}/{67}} as a subgraph. The bounds on \delta(G) and on \Delta(G) in Theorem 1.3 are essentially best possible. In view of Theorem 1.3 (a) and in analogy to Conjecture 1.1 , one might suspect that every graph of minimum degree exceeding k/2 and maximum degree at least 2k contains every k -edge tree. This was conjectured 1 1 1 A version with \geq k/2 replacing >k/2 had been conjectured earlier [ 2 ] , but was disproved by Hyde and Reed [ 4 ] . in [ 11 ] . Even if it is false, replacing 2k with another function of k will make it correct: Theorem 1.4 (Hyde and Reed [ 4 ] ) . There is a function f such that every graph with \delta(G)\geq k/2 and \Delta(G)\geq f(k) contains every k -edge tree. Let us now turn our attention to digraphs. Kathapurkar and Montgomery [ 5 ] recently extended Theorem 1.1 verbatim to digraphs, allowing the tree to have any orientation, and replacing the minimum degree \delta(G) with the minimum semidegree \delta^{0}(D) . Similarly to graphs, if we wish to find a variant of their theorem for trees of smaller order, we need to add the condition that the host digraph D has vertices of large outdegree and vertices of large indegree. Define \Delta(D) as the largest integer m such that D has a vertex of outdegree at least m and a vertex of indegree at least m . Our main result is a version of Theorem 1.3 for digraphs and balanced antidirected trees (where a balanced antidirected tree is an oriented tree without 2-directed paths and with the same number of vertices in each partition class). It reads as follows. Theorem 1.5 . For every \gamma>0 , c\in\mathbb{R} and \ell\in\mathbb{N} with

Read the complete text