Typical T T -free graphs

Bruce Reed, Yelena Yuditsky · 2025

Read Typical T T -free graphs by Bruce Reed, Yelena Yuditsky (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-2506-01067.txt.

Introduction

Bruce Reed and Yelena Yuditsky describe what a typical graph looks like when one fixed tree pattern is banned as an induced subgraph. For every tree except the single edge, they prove that almost all graphs avoiding the tree split into a set number of parts that certify the avoidance. Each part is free of a small four-vertex path and carries extra structure set by the tree. The result yields strong counts of how many such graphs exist.

Catalog record

CREATORBruce Reed, Yelena Yuditsky
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE116 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-01067

Browse the full library · About the Tower of Babel

Full text

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

Typical T T -free graphs Bruce Reed, Yelena Yuditsky Abstract We prove that for every tree T T which is not an edge, for almost every graph G G which does not contain T T as an induced subgraph, V ⁡ ( G ) V(G) has a partition into α ⁡ ( T ) − 1 \alpha(T)-1 parts certifying this fact. Each part induces a graph which is P 4 P_{4} -free and has further properties which depend on T T . As a consequence we obtain good bounds (often tight up to a constant factor) on the number of T T -free graphs and show in a follow-up paper [ RY ] that almost every T T -free graph G G has chromatic number equal to the size of its largest clique. 1 Overview In this paper we focus on the class of graphs 1 1 1 We assume our readers are familiar with the definition of a graph and the basic notation of graph theory. For notation which is used without being defined see [ BMbook ] . which do not contain some tree T as an induced subgraph, such graphs are called T -free . We show that the vertex set of almost every 2 2 2 a property holds for almost every graph in a family if the proportion of graphs of size n in the family for which it fails goes to zero as n goes to infinity. T -free graph has a certain kind of partition which certifies that it is T -free. Results of the same flavor were previously obtained for a triangle ( [ EKR76 ] ), a cycle of length 4 or 5 [ PS91 , PSBerge ] , longer odd cycles and larger cliques( [ BB11 , KPR87 ] ), and longer even cycles [ R ] , [ KKOT15 ] . We start by giving some intuition behind our results. Letting \alpha(T) be the size of the largest stable set in T , we know T cannot be partitioned into \alpha(T)-1 cliques. Hence any graph G whose vertex set can be partitioned into \alpha(T)-1 cliques is T -free. For every T such that \alpha(T)>\frac{|V(T)|+1}{2} , almost every T -free graph has such a partition which certifies it is T -free. We will give a very short and very straightforward proof that this result follows from the main result in [ BB11 ] . If T has a near perfect matching then almost every T -free graph has such a partition unless T is a subdivided star. If T is a subdivided star, then almost every T_{4} graph has either such a partition or a partition into a stable set and \alpha-2 cliques certifying it is T -free. Again we give a very short and very straightforward proof that these result follows from the main result in [ BB11 ] . If T has a perfect matching (and hence \alpha(T)=\frac{|V(T)|}{2} ) then it is not true that almost every T -free graph has such partition. Consider, for example the tree M_{6} of Figure 1 . We note, \alpha(M_{6})=3 . Now there are at most 2^{n}2^{n^{2}/4} graphs on n vertices whose vertex set can be partitioned into two cliques. However, V(M_{6}) cannot be partitioned into two sets each of which either is an induced subgraph of P_{3} or contains a triangle. So, if V(G) can be partitioned into two sets each inducing the complement of a matching then it is M_{6} -free. For even k , there are \frac{k!}{2^{k/2}(\frac{k}{2})!}=2^{\omega(k)} matchings within a set of k vertices. So considering a single partition of V(M_{6}) into X_{1},X_{2} with |X_{1}-X_{2}|\leq 1 we see that there are 2^{\omega(n)}2^{n^{2}/4} M_{6} - free graphs for which X_{1} and X_{2} both induce complements of matchings. Hence it is not true that almost every M_{6} free graph can be partitioned into two cliques. It turns out however that the vertex set of almost every M_{6} -free graph has a partition into two sets each inducing a complement of a matching which certifies that it is M_{6} -free. Figure 1 : The graph M_{6} . We prove that for every tree T which is not an edge 3 3 3 An edge is the unique tree with \omega(T)>\alpha(T) which explains its unique behaviour. If T is an edge every T -free graph has a partition into \omega(T)-1=1 sets each of which is a stable set , almost every T -free graph has a partition into \alpha(T)-1 parts which certifies that it is T -free, to wit: Definition . For a tree T , a T -freeness witnessing partition of a graph G is a partition of V(G) into \alpha(T)-1 parts X_{1},...,X_{\alpha(T)-1} such that for any partition of V(T) into \alpha(T)-1 parts Y_{1},...,Y_{\alpha(T)-1} there is an i\in[\alpha(T)-1] such that T[Y_{i}] is not an induced subgraph of G[X_{i}] . Remark . If G has a T -freeness witnessing partition then it is T -free. Every T -free graph G has a trivial such partition where all but 1 part is empty. We focus on partitions such that each part has size at least 4^{|V(T)|} . Ramsey’s Theorem [ R30 ] implies that for such a partition every part contains either a clique or or a stable set of size |V(T)| . We note Claim 1.1 . Let T be a tree with at least four vertices, then T can be partitioned into (a) 2 stable sets, (b) \alpha(T) cliques, (c) a stable set of size at most 2 and \alpha(T)-1 cliques, (d) an induced subgraph of P_{4} and \alpha(T)-2 cliques, (e) if \alpha(T)>2 , an induced subgraph of P_{4} , \alpha(T)-3 cliques, and a stable set of size at most 2. Proof. T is bipartite so (a) holds, and for any minimum vertex cover C in T , there is a partition of T into \alpha(T)=|V(T)|-|C| cliques, |C| are edges with exactly one endpoint in C and the rest of which form a stable set S . Hence (b) holds as do (c) and (d) unless T has a perfect matching. If T has a perfect matching then two of the cliques in the partition are joined by an edge and hence span a P_{4} . We can partition this P_{4} into a stable set and an edge so (c) and (d) hold. To prove (e), we consider a minimal counterexample. We root T and take a deepest node l . We see that l is a leaf whose parent p has only leaf children. If p has two children, we delete two of them to obtain a tree T^{\prime} with \alpha(T^{\prime})\leq\alpha(T)-1 . Applying (d) to T^{\prime} yields the desired result. Otherwise, \alpha(T-p-l)=\alpha(T)-1 . If \alpha(T)-1>2 , adding pl to the partition showing (e) holds for T^{\prime} shows (e) holds for T . If T is a P_{5} or P_{6} then deleting the endpoints of the path shows (e) holds. Otherwise, deleting two leaves other than l from T yields a P_{3} or P_{4} , so (e) holds. ∎ Applying our claim we see that we can reorder the partition elements of any T -freeness witnessing partition in which each part has size at least 4^{|V(T)|} as (X_{1},\ldots X_{\alpha(T)-1} ) so that

Read the complete text