The set of all positive integers is denoted by N, and for every integer n, we write N n for the set of all positive integers less than or equal to n (so N n = ∅ if n ≤ 0). Graphs in this paper have finite vertex sets, no loops and no parallel edges. Let G = (V (G), E(G)) be a graph. An induced subgraph of G is the graph G \ X for some X ⊆ V (G), that is, the graph obtained from G by removing the vertices in X. For X ⊆ V (G), we use both X and G[X] to denote the subgraph of G induced on X, which is the same as G\(V (G)\X). We say G contains a graph H if H is isomorphic to an induced subgraph of G; otherwise, we say G is H-free. We also say G is H-free for a family H of graphs if G is H-free for all H ∈ H. The treewidth of a graph G (denoted by tw(G)) is the smallest w ∈ N for which G can be represented as (a subgraph of) an intersection graph of subtrees of a tree, such that each vertex of the underlying tree appears in at most w + 1 subtrees. For instance, the "Helly property of subtrees" [8] implies that for every t ∈ N, the complete graph K t+1 and the complete bipartite graph K t,t both have treewidth t.
There are also sparse graphs with arbitrarily large treewidth, the most well-known example of which is the hexagonal grid (see Figure 1). For every t ∈ N, the t-by-t hexagonal grid, also called the t-by-t wall, denoted W t×t , has treewidth t [14], and the same remains true for all subdivisions of W t×t , as well. Indeed, Robertson and Seymour proved in 1986 [14] that containing a hexagonal grid as a minor (or a subdivided one as a subgraph) is qualitatively the only reason why a graph may have large treewidth: Theorem 1.1 (Robertson and Seymour [14]). For every t ∈ N, every graph of sufficiently large treewidth contains a subdivision of W t×t as a subgraph.
For induced subgraphs, however, excluding just the walls is not enough to guarantee bounded treewidth: note that complete graphs, complete bipartite graphs and subdivided walls are three pairwise "independent" types of graphs with arbitrarily large treewidth, in the sense that no graph from one type contains an induced subgraph of another type with large treewidth. There is also a fourth example, namely the line-graphs of subdivided walls, where the line-graph L(F ) of a graph F is the graph with vertex set E(F ), such that two vertices of L(F ) are adjacent if the corresponding edges of F share an end.
It is useful to group all these graphs together: given t ∈ N, we say a graph H is a t-basic obstruction if G is isomorphic to one the following: the complete graph K t+1 , the complete bipartite graph K t,t , a subdivision of W t×t , or the line-graph of a subdivision of W t×t (see Figure 2). For every t ∈ N, every t-basic obstruction has treewidth t, and each induced subgraph of large treewidth in a basic obstruction of a given type contains a basic obstruction of the same type and of (relatively) large treewidth. Let us say a graph G is t-clean if G contains no t-basic obstruction. It follows that every graph of treewidth less than t is t-clean.
One may hope for the basic obstructions to be the only induced subgraph obstructions to bounded treewidth. In other words, the neatest possible analog of Theorem 1.1 for induced subgraphs would be the following: for every t ∈ N, there is a constant n = n(t) ∈ N such that every t-clean graph has treewidth less than n. However, there are now several counterexamples to this statement [3,6,12,17]. The simplest construction is due (middle) and its line-graph (right). to Pohoata and Davies (independently) [6,12], consisting of 3-clean graphs of arbitrarily large treewidth. We call these graphs arrays. Specifically, for n ∈ N, an n-array is a graph consisting of n pairwise disjoint paths L 1 , . . . , L n with no edges between them as well as n pairwise non-adjacent vertices x 1 , . . . , x n , such that for every i ∈ N n :
• each of x 1 , . . . , x n has at least one neighbor in L i ; and • for every j ∈ N n-1 , all neighbors of x j in L i appear before all neighbors of x j+1 in L i (in particular, each vertex of L i is adjacent to at most one of x 1 , . . . , x n ).
See Figure 3. As mentioned earlier, arrays are 3-clean graphs with unbounded treewidth:
Theorem 1.2 (Pohoata [12], Davies [6]; see also Theorem 3.1 in [2]). For every n ∈ N, every n-array is a 3-clean graph of treewidth at least n.
This motivates the following definition: A graph class G is said to be clean if the only induced subgraph obstructions to bounded treewidth in G are in fact the basic ones, that is, for every t ∈ N, there is a constant n = n(t) ∈ N such that every t-clean graph in G has treewidth less than n. An exact analog of Theorem 1.1 for induced subgraphs is therefore equivalent to a characterization of all families H of graphs for which the class of all H-free graphs is clean. This appears to be out of reach of the current techniques, and even formulating a conjecture seems rather difficult. Nevertheless, the known "non-basic" obstructions may provide some insight into the structural properties of a family H with the above property. For example, from Theorem 1.2 combined with the definition of a clean class, we deduce that: Observation 1.3. Let H be a family of graphs such that the class of H-free graphs is clean. Then there exists n 0 ∈ N such that for every n ≥ n 0 and every n-array A, there is a graph H ∈ H which is isomorphic to an induced subgraph of A.
The converse to Observation 1.3 is not true in general; indeed, all other non-basic obstructions discovered so far [3,17] are counterexamples to this converse:
• Let H be the family of all graphs which are the disjoint unions of two cycles.
Then every n-array with n ≥ 4 contains a graph in H, while it is proved in [3] that there are 3-clean H-free graphs of arbitrarily large treewidth. • Let H be the family of all subdivisions of K 2,3 , also known as the thetas. Then it is readily observed that every n-array with n ≥ 3 contains a theta, whereas it is proved in [17] that the class of theta-free graphs is not clean. It turns out that what allows these counterexamples to occur is the fact that the corresponding family H of graphs that we are forbidding is infinite. Our main result in this paper shows for a finite set H of graphs, the necessary condition from Observation 1.3 is in fact sufficient: Theorem 1.4. Let H be a finite set of graphs. Then the class of all H-free graphs is clean if and only if there are only finitely many n ∈ N for which there is an H-free n-array.
This may also be regarded as a natural strengthening of the main result from [1], which handles the special case where H is a singleton: Theorem 1.5 (Abrishami, Alecu, Chudnovsky, Hajebi and Spirkl [1]). Let H be a graph. Then the class of all H-free graphs is clean if and only if every component of H is a subdivided star, that is, a tree with at most one vertex of degree more than two.
1.1. Tassels and tasselled families. Note that by Observation 1.3, we only need to prove the "if" implication of Theorem 1.4. To that end, we find it technically most convenient to reformulate the "if" implication in terms of "the columns of the arrays," which we refer to as "tassels."
Let us make this precise. A strand is a graph F obtained from a path P by adding a new vertex x with at least one neighbor in P , and we say F is a c-strand, for c ∈ N, if x is not adjacent to the first and last c vertices of P . We call x and P the neck of F and the path of F , respectively. For c ∈ N, by a c-tassel we mean a graph T obtained from at least c pairwise disjoint copies of a c-strand F by identifying their necks into a single vertex, called the neck of T . We also refer to each copy of F in T as a strand of T , and to the path of each copy of F as a path of T (see Figure 4).
We say that a family H of graphs is tasselled if there is a constant c = c(H) ∈ N with the property that for every c-tassel T there is H ∈ H such that T contains each component of H. Also, if H is finite, we define ||H|| = H∈H |V (H)|. It follows that: Theorem 1.6. Let H be a finite set of graphs such that there is no H-free n-array except possibly for finitely many n ∈ N. Then H is tasselled.
Proof. By the assumption, there exists n 0 ∈ N such that there is no H-free n-array for any n ≥ n 0 . Let c = max{n 0 , ||H||}. In order to prove that H is tasselled, we show that for every c-tassel T , there is a graph H ∈ H such that T contains each component of H.
Let d ≥ c be the number of paths of T . Construct an d-array A as follows. Start with d pairwise disjoint copies T 1 , . . . , T d of T . For each i ∈ N d , let x i be the neck of T i and fix an enumeration P i 1 , . . . , P i d of the paths of T i . For every i, j ∈ N d , fix a labelling u i j , v i x 1 x 2 x 3 P 2 1 P 2 2 P 2 3 P 1 1 P 1 2 P 1 3 P 3 1 P 3 2 P 3 3 T 1 T 2 T 3 Figure 5. The 3-array A as described in the proof of Theorem 1.6, obtained from three copies T 1 , T 2 , T 3 of the 3-tassel T in Figure 4.
of the ends of P i j . Then, for every i ∈ N d-1 and every j ∈ N d , add an edge between u i j and v i+1 j (see Figure 5). Since A is an d-array with d ≥ c ≥ n 0 , it follows that A is not H-free, and so we may choose a graph H ∈ H which is contained in A.
Let K be a component of H. Our goal is to show that K is contained in T . This is immediate if K is a path, because |K| ≤ ||H|| ≤ c and T is a c-tassel. Thus, we may assume that K is not a path. Since H is contained in A, it follows that some induced subgraph K ′ of A is isomorphic to K. In particular, K ′ is a connected graph on at most ||H|| vertices which is not a path. Also, from the construction of A, it is readily observed that the necks x 1 , . . . , x d of T 1 , . . . , T d are pairwise at distance at least 2c+3 > ||H|| ≥ |K ′ | in G. Consequently, there exists exactly one i ∈ N d for which x i belongs to V (K ′ ). Now, since K ′ is connected, it follows that for every component P of K ′ \ {x i }, we have P ⊆ V (A) \ {x 1 , . . . , x d } and x i has a neighbor in P . This, along with the fact that P is connected and
In view of Theorem 1.6, in order to prove Theorem 1.4, it suffices to show that:
Theorem 1.7. Let H be a finite set of graphs which is tasselled. Then the class of H-free graphs is clean.
The rest of the paper is devoted to the proof of Theorem 1.7, which is completed in Section 7. Note also that Theorems 1.6 and 1.7 combined with Observation 1.3 imply the following (see also Figure 6).
Corollary 1.8. The following are equivalent for every finite set H of graphs.
There is no H-free graphs is clean H -free n-array except possibly for finitely may values of n ≥ 1 • There is no H-free n-array except possibly for finitely many n ∈ N.
• H is tasselled.
• The class of all H-free graphs is clean.
Outline. To prove the Theorem 1.7, we proceed as follows. First, in Section 2, we show that a finite family is tasselled if and only if it is "hassled," which is described by containment not in a c-tassel, but in a less restricted c-hassle: while similar to a tassel, the paths are replaced by walks such that any short stretch is an induced path, the adjacency from the neck to the walks need not be the same, and we may have edges between walks.
Then, our goal is to show that t-clean graphs of large treewidth contain c-hassles. To do so, we start with some preliminary Ramsey-type results in Section 3. In Section 4, we show that in "blocks," which are sets of vertices with pairwise many paths between them, we can arrange that those paths are long. This is useful for getting many long induced paths, which will form part of our c-hassles.
In Section 5, we get a structure of large treewidth consisting of one of the following:
• A large set of paths, and a large set of vertices, each with a neighbor in every path; or • Two large sets of paths such that each path in one set has an edge to each path in the other, but no vertex has neighbors in many paths. In Section 6, we show how each of these configurations leads to a c-hassle. In the former case, this is almost immediate, whereas the latter case is more involved: we find a block whose vertex set is contained in the union of the paths, and leverage the interaction between the two structures, along with the fact that blocks are long, to find our c-hassle.
In Section 7, we put everything together and prove our main result.
In this section, we introduce the notion of a "hassled family" as a variant of tasselled families, and show that for finite families of graphs, these two properties are in fact equivalent. This in turn reduces Theorem 1.7 to: for every finite and hassled family H of graphs, the class of all H-free graphs is clean. The remainder of this paper is then occupied with a proof of the latter statement, which will appear as Theorem 7.1 in Section 7. In order to define hassled families, first we need another notion, that of a "c-hassle," which is similar to a c-tassel except its paths are replaced by walks that are "locally" isomorphic to a path, and, up to sparsity, there may be additional edges between these walks. Let us define all this formally. Let n ∈ N and let P be an n-vertex path (as a graph). Then we write P = p 1 -• • • -p n to mean that V (P ) = {p 1 , . . . , p n } and p i is adjacent to p j if and only if |i -j| = 1. We call the vertices p 1 and p n the ends of P , and refer to P \ {p 1 , p n } as the interior of P , denoted P * . For vertices u, v ∈ V (P ), we denote by u-P -v the subpath of P from u to v. Recall that the length of a path is the number of edges in it.
Let G be a graph. A path in G is an induced subgraph of G which is a path. For X, Y ⊆ V (G). We say X is complete to Y in G if every vertex of X is adjacent to every vertex in Y , and we say X and Y are anticomplete in G if there is no edge in G with an end in X and an end in Y . If x ∈ V (G), we say x is complete (anticomplete) to Y if {x} and Y are complete (anticomplete) in G.
For n ∈ N ∪ {0}, by an n-segment we mean a set S of at most n consecutive integers; in particular, N n is an n-segment. A graph W is a walk if there is n W ∈ N and a surjective map φ W : N n W → V (W ) such that for every i ∈ N n W -1 , we have φ W (i)φ W (i + 1) ∈ E(W ) (one may in fact observe that a graph W is a walk if and only if it is connected). Given a walk W along with choices of n W and ϕ W , for c ∈ N, we refer to φ W (N c ) and φ W (N n W \ N n W -c ) as the first c vertices of W and the last c vertices of W , respectively. We also say W is c-stretched if φ W (S) is a path in W for every c-segment S ⊆ N n W (see Figure 7 -intuitively, this means a snake of length c -1 traversing through W can never see/hit itself).
We now define a c-hassle, where c ∈ N, to be a graph Ξ obtained from at least c pairwise disjoint c-stretched walks, called the walks of Ξ, by adding edges arbitrarily between the walks, and then adding a vertex x, called the neck of Ξ, which has a neighbor in each walk and which is anticomplete to the first and last c vertices of each walk (see Figure 8).
For a family H of graphs, we say H is hassled if for every t ∈ N, there is c = c(H, t) ∈ N with the property that for every (K t+1 , K t,t )-free c-hassle T there exists H ∈ H such that T contains every component of H. In particular, observe that every c-tassel is a (K 4 , K 3,3 )-free c-hassle, and so every hassled family is tasselled. More importantly, for finite families, the converse is also true: Theorem 2.1. Let H be a finite set of graphs. Then H is tasselled if and only if H is hassled. The goal of this section is to prove Theorem 2.1, beginning with two lemmas:
Lemma 2.2. Let b, c, k ∈ N, let T be a family of c-tassels, each with exactly c paths, such that |T | ≥ bkc k . For each T ∈ T , let x T be the neck of T and fix an enumeration P T 1 , . . . , P T c of the paths of T . Let K be a connected graph on at most k vertices which is not a path, and assume that for every T ∈ T , there is an isomorphism f T from K to an induced subgraph of T ; in particular, T contains K. Then there exist x ′ ∈ V (K) and T ′ ⊆ T with |T ′ | = b for which the following hold.
(a) For every T ∈ T ′ , we have f T (x ′ ) = x T .
(b) For every component L of K \ {x ′ }, there exists i(L) ∈ {1, . . . , c} such that for every T ∈ T ′ , we have f T (L) ⊆ P T i(L) . Proof. For each T ∈ T , since K is not a path and f T is an isomorphism, it follows that there is a unique vertex x ′ T ∈ V (K) such that f T (x ′ T ) = x T . Also, since K has at most k vertices, it follows that:
(1) There exist x ′ ∈ V (K) and
By (1), for each T ∈ T 1 and every component L of K \ {x ′ }, we have f T (L) ⊆ T \ {x T }, which in turn implies that there exists i(L, T ) ∈ N c for which we have f T (L) ⊆ P T i(L,T ) . Now, since K \ {x ′ } has at most k components and since |T 1 | ≥ bc k , it follows that there exists
Moreover, from (1), it follows that x ′ and T ′ satisfy 2.2(a), as desired. ■ Lemma 2.3. For every finite and tasselled set H of graphs, there is a constant ξ = ξ(H) ∈ N with the following property. For every ξ-hassle Ξ with neck x, there is a graph H ∈ H such that for every component K of H, one of the following holds.
(a) K is a path. (b) There exists x ′ ∈ V (K) and a map f :
Proof. Since H is tasselled, it follows that there is a constant c = c(H) ∈ N with the property that for every c-tassel T there is H ∈ H such that T contains every component i (p j ) = j for all j ∈ N 11 . Observe that for every j ∈ N 11 , we have φ W (g W i (p j )) = w j , and x W is adjacent to
||H||+1 satisfies the lemma. To see this, let Ξ be a ξ-hassle with neck x, and let W be the collection of all walks of Ξ. Recall that each walk in Ξ is ξ-stretched.
For each W ∈ W, let n W and φ W be as in the definition of a walk, and construct a c-tassel T W as follows. Let P W 1 , . . . , P W c be c pairwise disjoint and anticomplete paths, each on n W vertices, and for every i ∈ N c , choose a bijection g W i :
(note that there are only two such bijections). Let T W be the graph obtained from P W 1 , . . . , P W c by adding a vertex x W such that for every i ∈ N c and every p ∈ V (P W i ), the vertex x W is adjacent to p in T W if and only if x is adjacent to φ W (g W i (p)) in Ξ (see Figure 9). Note that for every W ∈ W, in the graph Ξ, the vertex x has a neighbor in W and no neighbor among the first and last ξ vertices of W . In particular, from the construction and the fact that ξ ≥ c, it follows that for every i ∈ N c , x has a neighbor in P W i and no neighbor among the first and last c vertices of P W i . Thus, for every W ∈ W, the graph T W is a c-tassel with neck x W and paths P W 1 , . . . , P W c . Also, since H is tasselled, it follows from the choice of c that for every W ∈ W there exists H ∈ H such that the c-tassel T W contains every component of H. Consequently, since |W| ≥ ξ and |H| ≤ ||H||, it follows that there exists H ∈ H and W ′ ⊆ W with |W ′ | = ||H||c ||H||+1 such that for every W ∈ W ′ , the c-tassel T W contains every component of H.
We now prove that H satisfies 2.3. Let K be a component of H which is not a path. We wish to show that K satisfies 2.3(b). Note that for every W ∈ W ′ , the c-tassel T W contains K, and so there is an isomorphism f W from K to an induced subgraph of T W . This allows for an application of Lemma 2.2 to
Henceforth, for each j ∈ N c , we write
Also, for i, j ∈ N c , we write P i,j = P
i . The outcomes of Lemma 2.2 can now be rewritten as:
(2) The following hold.
• For every j ∈ N c , we have f j (x ′ ) = x j .
• For every component L of K \ {x ′ }, there exists i(L) ∈ {1, . . . , c} such that for every j ∈ N c , we have f j (L) ⊆ P i(L),j .
On the other hand, since |K| ≤ |H| ≤ ||H|| ≤ ξ, it follows that every component of K \ {x ′ } is a path on less than ξ vertices. This, combined with the second bullet of (2), yields the following:
(3) For every j ∈ N c and every component L of K \ {x ′ }, there exists a ξ-segment S j,L ⊆ N n j for which we have f j (L) = g -1 i(L),j (S j,L ) ⊆ P i(L),j . Let us now finish the proof. Define a map f : V (K) → V (Ξ) as follows. Let f (x ′ ) = x, and for every component L of K \ {x ′ } and every y ∈ L, let
See Figure 10. We prove that f satisfies Lemma 2.3(b). Let L be a component of
\ {x}, and so we have f -1 ({x}) = {x ′ }. This, along with the assumption that W i(L) is a ξ-stretched walk, implies that f (L) is a path in W i(L) . In particular, the restriction of
It remains to show that for every y ∈ L, the vertices x ′ , y are adjacent in K if and only if x, f (y) are adjacent in Ξ. To that end, note that since f i(L) is an isomorphism from K to an induced subgraph of T i(L) , it follows from the first bullet of (2) that x ′ is adjacent to y in K if and only if
We also need the following well-known result.
Lemma 2.4 (See Lemma 2 in [11]). For all q, r, t ∈ N there is a constant ∆ = ∆(q, r, t) ∈ N with the following property. Let G be a (K t+1 , K t,t )-free graph. Let X be a collection of pairwise disjoint subsets of V (G), each of cardinality at most r, with |X | ≥ ∆. Then there are q distinct sets X 1 , . . . , X q ∈ X which are pairwise anticomplete in G.
We can now prove Theorem 2.1, which we restate:
Theorem 2.1. Let H be a finite set of graphs. Then H is tasselled if and only if H is hassled.
Proof. The "if" implication is clear as discussed at the beginning of this section. To prove the "only if" implication, assume that H is a finite set of graphs which is tasselled. Let ξ = ξ(H) ∈ N be as in Lemma 2.3. For every t ∈ N, let ∆ = ∆(||H||, ||H||, t) be as in Lemma 2.4, and let c = c(H, t) = ξ∆||H|| 2 1 . We prove that for every (K t+1 , K t,t )-free c-hassle Ξ, there exists a graph H ∈ H such that Ξ contains each component of H. This will show that H is hassled.
Let x be the neck of Ξ. By the choice of c, we may choose a set W of ∆||H|| 2 1 pairwise disjoint families of walks of Ξ, each of cardinality ξ. It follows that for every W ∈ W, the graph
] is a ξ-hassle with neck x, and with W as its set of walks.
Since H is tasselled, and by the choice of ξ, for each W ∈ W, we can apply Lemma 2.3 to H and Ξ W , and obtain a graph H W ∈ H satisfying Lemma 2.3(a) and (b). Moreover, since |H| ≤ ||H|| and |W| = ∆||H|| 2 , it follows that there exist H ∈ H and X ⊆ W with |X| = ∆||H|| such that for every W ∈ X, we have H W = H. More explicitly, for every component K of H, one of the following holds.
• K is a path.
• For every W ∈ X, there exists x ′ W ∈ V (K) and an injective map
To conclude the proof, it suffices to show that Ξ contains every component K of H. Assume that K is a path. Since Ξ is a c-hassle, it follows that Ξ contains a path on c vertices. But now we are done because |K| ≤ ||H|| ≤ c. Consequently, we may assume that K is not a path, and so the second bullet above holds for K and every W ∈ X. In addition, from |K| ≤ ||H|| and |X| = ∆||H||, it follows that there exist x ′ ∈ V (K) and Y ⊆ X with |Y| = ∆ such that for every W ∈ Y, we have x ′ W = x ′ . On the other hand, {f W (K\{x ′ }) : W ∈ Y} is a collection of ∆ pairwise disjoint subsets of Ξ \ {x}, each of cardinality less than |K| ≤ ||H||. This, along with the choice of ∆ and the assumption that Ξ is (K t+1 , K t,t )-free, allows for an application of Lemma 2.4. We deduce that: (4). By the second bullet above, for each i ∈ N k , the restriction of
This completes the proof of Theorem 2.1. ■
We now begin to make our way to the proof of Theorem 7.1. In particular, here we prove a Ramsey-type result that we will use several times later. We need the following product version of Ramsey's Theorem. Theorem 3.1 (Graham, Rothschild and Spencer [9]). For all n, q, r ∈ N, there is a constant ν(n, q, r) ∈ N with the following property. Let U 1 , . . . , U n be n sets, each of cardinality at least ν(n, q, r) and let W be a non-empty set of cardinality at most r. Let Φ be a map from the Cartesian product
For an induced subgraph H of a graph G and a vertex x ∈ V (G), we denote by N H (x) the set of all neighbors of x in H, and write
with the following property. Let G be a graph. Let B 1 , . . . , B m be collections of pairwise disjoint a-pairs over V (G), each of cardinality at least Υ. Then for every i ∈ N m , there exists
Let M be the set of all m-by-m matrices whose entries are subsets of N a ; so we have
It follows that for every z ∈ Π, M 1 (z), M 2 (z) are unique, and so the map Φ : Π → M 2 with Φ(z) = (M 1 (z), M 2 (z)) is well-defined. This, along with the choice of Υ and Theorem 3.1, implies that there exists
Moreover, we deduce:
(5) Let i, j ∈ N m be distinct. Then we have
Suppose for a contradiction that there are distinct i, j ∈ N m such that for some
is non-empty. But then B j ∩ B ′ j ̸ = ∅, a contradiction with the assumption that (A j , B j ), (A ′ j , B ′ j ) ∈ B ′ j ⊆ B j are disjoint. This proves (5).
(6) Let i, j ∈ N m be distinct. Then either A i is anticomplete to B j in G for all (A i , B i ) ∈ B ′ i and (A j , B j ) ∈ B ′ j , or for every (A i , B i ) ∈ B ′ i , there exists x i ∈ A i such that x i has a neighbor in B j for every (A j , B j ) ∈ B ′ j .
and so for each
A i ∈ A i has a neighbor in B j for every (A j , B j ) ∈ B ′ j . This proves (6). Now the result follows from ( 5) and ( 6). This completes the proof of Lemma 3.2. ■
This section collects several results from the literature about "blocks" in t-clean graphs of large treewidth. We begin with a couple of definitions. Given a set X and q ∈ N ∪ {0}, we denote by 2 X the power set of X and by X q the set of all q-subsets of X. Let G be a graph. For a collection P of paths in G, we adopt the notation V (P) = P ∈P V (P ) and P * = P ∈P P * . Let k ∈ N. A k-block in G is a set B of at least k vertices in G such that for every 2-subset {x, y} of B, there exists a collection P {x,y} of k pairwise internally disjoint paths in G from x to y. In addition, we say B is strong if the collections {P {x,y} : {x, y} ⊆ B} can be chosen such that for all distinct 2-subsets {x, y}, {x ′ , y ′ } of B, we have V (P * {x,y} ) ∩ V (P {x ′ ,y ′ } ) = ∅. In [1], with Abrishami we proved the following:
Theorem 4.1 (Abrishami, Alecu, Chudnovsky, Hajebi and Spirkl [1]). For all k, t ∈ N, there is a constant κ = κ(k, t) ∈ N such that every t-clean graph of treewidth more than κ contains a strong k-block.
Given a graph G and d, k ∈ N, we say a (strong) k-block B in G is d-short if for every 2-subset {x, y} ⊆ B of G, every path P ∈ P {x,y} is of length at most d. The following shows that large enough short blocks contain strong (and short) "sub-blocks." Theorem 4.2. For all d, k ∈ N, there is a constant υ = υ(d, k) with the following property. Let G be a graph and let B be a d-short υ-block in G.
, where Υ(•, •, •) is as in Lemma 3.2. Let B 0 be a d-short υ-block in G, and let B ⊆ B 0 with |B| = k. It follows that for every 2-subset {x, y} of B, there is a collection P {x,y} of υ pairwise internally disjoint paths in G, each of length at most d. Let B {x,y} = {(P, P * ) : P ∈ P {x,y} }. Then B {x,y} is a collection of υ pairwise disjoint (d + 1)-pairs over V (G). Thus, the choice of υ allows for an application of Lemma 3.2 to the collections {B {x,y} : {x, y} ∈ B 2 }. We deduce that for every {x, y} ∈ B 2 , there exists Q {x,y} ⊆ P {x,y} with |Q {x,y} | ≥ k, such that for all distinct {x, y}, {x ′ , y ′ } ∈ B 2 , the collections B ′ {x,y} = {(P, P * ) :
satisfy the outcomes of Lemma 3.2. In particular, for all distinct {x, y}, {x ′ , y ′ } ∈ B 2 , it follows from Lemma 3.2(a) that for every P ∈ Q {x,y} and every P ′ ∈ Q {x ′ ,y ′ } , we have P * ∩ P ′ = ∅. Equivalently, we have
2 }}. This completes the proof of Theorem 4.
Recall that a subdivision of a graph H is a graph H ′ obtained from H by replacing the edges of H with pairwise internally disjoint paths of non-zero lengths between the corresponding ends. Let r ∈ N ∪ {0}. An (≤ r)-subdivision of H is a subdivision of H in which the path replacing each edge has length at most r + 1. Also, a proper subdivision of H is a subdivision of H in which the path replacing each edge has length at least two. We need the following immediate corollary of a result of [7]: Theorem 4.3 (Dvořák [7]). For every graph H and all d ∈ N ∪ {0} and t ∈ N, there is a constant m = m(H, d, t) ∈ N with the following property. Let G be a graph with no induced subgraph isomorphic to a subdivision of H. Assume that G contains a (≤ d)subdivision of K m as a subgraph. Then G contains either K t+1 or K t,t .
From Theorems 4.2 and 4.3 together, we deduce that: Theorem 4.4. For all d, t ∈ N, there is a constant η = η(d, t) ∈ N with the following property. Let G be a t-clean graph. Then there is no d-short η-block in G.
Proof. Let m = m(W t×t , d, t) ∈ N be as in Theorem 4.3. We show that η = η(d, t) = max{υ(d, m), m} satisfies the theorem, where υ(•, •) is as in Theorem 4.2. Let G be a tclean graph; that is, G has no induced subgraph isomorphic to a t-basic obstruction, and in particular a subdivision of W t×t . Suppose for a contradiction that there is a d-short η-block B in G. Since |B| ≥ m, we may choose B ′ ⊆ B with |B ′ | = m. It follows from Theorem 4.2 that B ′ is a d-short strong m-block in G. For every 2-subset {x, y} of B ′ , let P {x,y} be a collection of m ∈ N pairwise internally disjoint paths in G from x to y as in the definition of a strong m-block, and fix a path P {x,y} ∈ P {x,y} . Now the union of the paths P {x,y} for all {x, y} ∈ B ′ 2 forms a subgraph of G isomorphic to a (≤ d)-subdivision of K m . This, together with the choice of m and the assumption that G is t-clean, violates Theorem 4.3. This contradiction completes the proof of Theorem 4.4. ■
The main result of this section, Theorem 5.1, shows that t-clean graphs of sufficiently large treewidth contain large complete bipartite minor models in which every "branch set" is a path, such that for every branch set P on at least two vertices, each vertex in P has neighbors in only a small number of branch sets in the "opposite side" of the bipartition. The exact statement of 5.1 is somewhat technical and involves a number of definitions which we give below.
Let G be a graph. For w ∈ N, a w-polypath in G is a set W of w pairwise disjoint paths in G. Let W be a w-polypath in G. For d ∈ N, we say W is d-loose if for every W ∈ W, each vertex v ∈ W has neighbors (in G) in fewer than d paths in W \ {W } (this is particular implies that a vertex of "large degree" has "most" of its neighbors on just one path; we will use this property extensively in Section 6). Also, for w ′ ∈ N w , we say W is w ′ -fancy if there exists W ′ ⊆ W with |W ′ | = w ′ such that for every W ′ ∈ W ′ and every Figure 11).
For s, l ∈ N, an (s, l)-cluster in G is a pair (S, L) where S ⊆ V (G) with |S| = s and L is an l-polypath in G \ S, such that every vertex x ∈ S has at least one neighbor in every path L ∈ L. If l = 1, say L = {L}, we also denote the (s, 1)-cluster (S, L) by the pair (S, L). For d ∈ N, we say (S, L) is d-meager if every vertex in V (L) has fewer than d neighbors in S. Again, it is easily seen that if (S, L) is an (s, l)-cluster in G, then G[S ∪ V (L)] has a K s,l -minor (see Figure 11).
Our goal is to prove: Theorem 5.1. For all c, l, s, t, w ∈ N, there is a constant γ = γ(c, l, s, t, w) ∈ N with the following property. Let G be a t-clean graph of treewidth more than γ. Then one of the following holds.
(a) There exists a t t -meager (s, l)-cluster in G.
(b) There exists a 2w-polypath in G which is both w-fancy and (l + t t s t t )-loose.
The proof of Theorem 5.1 is split into a number of lemmas. To begin with, we need the following multicolor version of Ramsey's Theorem for (uniform) hypergraphs.
(b) There exists L ⊆ L 0 with |L| = l such that (S, L) is a t t -meager (s, l)-cluster in G.
Proof. Suppose that 5.5(a) does not hold. For every L ∈ L 0 , let t L be the largest integer in N s for which there exists a vertex u L ∈ L with at least t L neighbors in S. It follows that:
(8) We have |{L ∈ L 0 : t L ≥ t t }| < t t s t t .
Suppose not. Let S ⊆ {L ∈ L 0 : t L ≥ t t } with |S| = t t s t t . Then for every L ∈ S, we may choose u L ∈ L and T L ⊆ S such that |T L | = t t and u L is complete to T L in G. Since |S| = s, it follows that there exist T ⊆ S and T ⊆ S such that |T | = |T | = t t , and for every L ∈ T , we have T L = T . Let U = {u L : L ∈ T }. Then T is disjoint from and complete to U in G. Also, since G is K t+1 -free and |T | = |U | = t t , it follows from Theorem 5.3 that there are two stable sets T ′ ⊆ T and
a contradiction. This proves (8). Now the result is immediate from ( 8) and the fact that |L 0 | = l + t t s t t . This completes the proof of Lemma 5.5. ■ Lemma 5.6. Let l, s, w ∈ N, let G be a graph and let Q, Q ′ be ((s + 1)
Then one of the following holds.
(a) There exists an (s, l)-cluster
has neighbors in fewer than l paths in W ′ , and every vertex in V (W ′ ) has neighbors in fewer than l paths in W.
Proof. Suppose 5.6(a) does not hold. Let r = sw l + w. Then we have (s + 1) l+1 w l 2 = (s + 1)((s + 1)w l ) l = s(sw l + w l ) l + (s + 1) l w l 2 ≥ sr l + w ≥ r.
In particular, one may choose R ′ ⊆ Q ′ with |R ′ | = r. For every Q ∈ Q, let r Q be the largest integer in N r for which there exists a vertex p Q ∈ Q which has neighbors in at least r Q paths in R ′ . It follows that:
Suppose not. Let P ⊆ {Q ∈ Q : r Q ≥ l} with |P| = sr l . Then for every Q ∈ P, we may choose
it follows that there exist L ⊆ R ′ and S ⊆ P such that |L| = l, |S| = s, and for every Q ∈ S, we have
contrary to the assumption that 5.6(a) does not hold. This proves (9). By (9) and since |Q| ≥ sr l + w, we may choose W ⊆ Q with |W| = w such that every vertex in V (W) has neighbors in fewer than l paths in R ′ .
Next, for every R ∈ R ′ , let w R be the largest integer in N w for which there exists a vertex q R ∈ R which has neighbors in at least w R paths in W. (10) We have |{R ∈ R ′ : w R ≥ l}| < sw l .
Suppose not. Let P ⊆ {R ∈ R ′ : w R ≥ l} with |P| = sw l . Then for every R ∈ P, we may choose p R ∈ R and L R ⊆ W such that |L R | = l and p R has a neighbor in every path in L R . Since |W| = w, it follows that there exist L ⊆ W and S ⊆ P such that |L| = l, |S| = s, and for every R ∈ S, we have L R = L. Let S = {q R : R ∈ S}; so we have |S| = s. But then (S, L) is an (s, l)-cluster in G with S ⊆ V (S) ⊆ V (P) ⊆ V (R ′ ) ⊆ V (Q ′ ) and L ⊆ W ⊆ Q, contrary to the assumption that 5.6(a) does not hold. This proves (10).
In view of (10) and since |R ′ | = r = sw l + w, we may choose W ′ ⊆ R ′ ⊆ Q ′ with |W ′ | = w such that every vertex in V (W ′ ) has neighbors in fewer than l paths in W. Now W, W ′ satisfy 5.6(b). This completes the proof of Lemma 5.6.
■
The last tool we need is a recent result from [10], the statement of which requires another definition. Let G be a graph and let w ∈ N. By a w-web in G we mean a pair (W, Λ) where
is a map such that for every 2-subset {x, y} of W , Λ({x, y}) = Λ {x,y} is a path in G with ends x, y; and (W3) for all distinct 2-subsets {x, y}, {x ′ , y ′ } of W , we Λ {x,y} ∩ Λ {x ′ ,y ′ } = {x, y} ∩ {x ′ , y ′ }. It follows that G has a subgraph isomorphic to a subdivision of K w if and only if there is a w-web in G. It is proved in [10] that: Theorem 5.7 (Hajebi [10]). For all a, b, c, s ∈ N, there is a constant θ = θ(a, b, c, s) ∈ N with the following property. Let G be a graph and let (W, Λ) be a θ-web in G. Then one of the following holds. -S is a stable set in G; -for any three vertices x, y, z ∈ S, x is anticomplete to Λ * y,z ; and -for all distinct 2-subsets {x, y}, {x ′ , y ′ } of S, Λ * {x,y} is anticomplete to Λ * {x ′ ,y ′ } . We are now in a position to prove our main result in this section, which we restate: Theorem 5.1. For all c, l, s, t, w ∈ N, there is a constant γ = γ(c, l, s, t, w) ∈ N with the following property. Let G be a t-clean graph of treewidth more than γ. Then one of the following holds.
(a) There exists a t t -meager (s, l)-cluster in G.
(b) There exists a 2w-polypath in G which is both w-fancy and (l + t t s t t )-loose.
Proof. Let b = l + t t s t t , let σ = σ(b, (s + 1) b+1 w b 2 , s) be as in Lemma 5.4 and let θ = θ(s, b, σ, 2t 2 ) be as in Theorem 5.7. We claim that γ = γ(c, l, s, t, w) = κ(θ, t)
satisfies the theorem, where κ(•, •) is as in Theorem 4.1.
Let G be a t-clean graph of treewidth more than γ. Suppose 5.1(a) does not hold. This, along with the choice of b, the assumption that G is t-clean, and Lemma 5.5, implies that: (11) There is no (s, b)-cluster in G.
From the choice of γ and Theorem 4.1, we obtain a strong θ-block B in G. In particular, for every 2-subset {x, y} of B, we may choose a path Λ {x,y} in G from x to y, such that for all distinct 2-subsets {x, y}, {x ′ , y ′ } of B, we have Λ {x,y} ∩ Λ {x ′ ,y ′ } = {x, y} ∩ {x ′ , y ′ }. It follows that (B, Λ) is a θ-web in G, and so we can apply Theorem 5.7 to (B, Λ). Note that Theorem 5.7(a) yields an (s, b)-cluster in G, which violates (11). Also, Theorem 5.7(c) implies that G contains a proper subdivision of K 2t 2 (as an induced subgraph), which in turn contains a proper subdivision of every graph on 2t 2 vertices. But this violates the assumption that
We conclude that Theorem 5.7(b) holds. In particular, there are two σ-polypaths C, C ′ in G such that for every L ∈ C and every L ′ ∈ C ′ , L is not anticomplete to L ′ in G. Now, from (11), the choice of σ and Lemma 5.4, it follows that there are two b-loose (11) and Lemma 5.6, it follows that there exist W ⊆ Q and W ′ ⊆ Q ′ with |W| = |W ′ | = w such that every vertex in V (W) has neighbors in fewer than b paths in W ′ , and every vertex in V (W ′ ) has neighbors in fewer than b paths in W. But now W ∪ W ′ is a 2w-polypath in G which is both w-fancy and b-loose, and so 5.1(b) holds. This completes the proof of Theorem 5.1. ■
Here we take the penultimate step of our proof by showing that: Theorem 6.1. For all c, t ∈ N, there is a constant Γ = Γ(c, t) such that every t-clean graph G of treewidth more than Γ contains a c-hassle.
From Theorem 5.1, we know that every t-clean graph of sufficiently large treewidth contains, omitting the corresponding parameters, either a meager cluster or a polypath which is both loose and fancy. So it suffices to prove Theorem 6.1 separately in each of these two cases. First, we show: Theorem 6.2. Let c, d ∈ N and let G be a graph. Assume that there is a d-meager (2cd, 2c 2 d)-cluster in G. Then G contains a c-hassle.
Proof. Let (S, L) be a d-meager (2cd, 2c 2 d)-cluster in G. For every path P in G[V (L)], let S P be the set of all vertices in S with a neighbor in P . For every L ∈ L and each end u of L, let L u be the longest path in L containing u such that |S Lu | < cd; then u is an end of L u . It follows that: From (12), it follows that for every L ∈ L, there are fewer than 2cd vertices in S with a neighbor among the first or last c vertices of L. This, along with |S| = 2cd and the fact that every vertex in S has a neighbor in every path in L, implies that for every L ∈ L, there is a vertex x L ∈ S with a neighbor in L and no neighbor among the first and last c vertices of L. On the other hand, we have |L| = c|S|. Thus, there exist x ∈ S and W ⊆ L with |W| = c such that for every L ∈ W, the vertex x has a neighbor in L and no neighbor among the first and last c vertices of L. But now Ξ = G[{x} ∪ V (W)] is a c-hassle in G with neck x and with W as its set of walks (each of which is a path in Ξ). This completes the proof of Theorem 6.2. ■
Handling the second outcome of Theorem 5.1 is more demanding. We prove: Theorem 6.3. For all c, d, t ∈ N, there is a constant Ω = Ω(c, d, t) ∈ N with the following property. Let G be a t-clean graph. Assume that there exists a 2Ω-polypath in G which is both Ω-fancy and d-loose. Then G contains a c-hassle.
We need to prepare for the proof of Theorem 6.3. Let G be a graph, let x, y ∈ V (G) be distinct and non-adjacent, and let P be a collection of pairwise internally disjoint paths in G from x to y. An x-slash for P in G is a path W in G \ {x, y} such that for every P ∈ P, the unique neighbor of x in P belongs to W . Our first lemma says that: Lemma 6.4. Let c, p, q ∈ N. Let G be a graph, let x, y ∈ V (G) be distinct and nonadjacent, and let P 0 be a collection of c(p + 1)q pairwise internally disjoint paths in G from x to y. Let W 0 be an x-slash for P 0 in G. Then one of the following holds.
(a) There exists P ⊆ P 0 with |P| = p and a path W ⊆ W 0 , such that:
• W is an x-slash for P in G; and • there is no path Q of length at most c + 1 in V (P) ∪ W from x to y. (b) There exists a collection Q of q pairwise internally disjoint paths in G from x to y, each of length at most c + 1.
Proof. Let C be a maximal set of pairwise internally disjoint paths in G from x to y, each of length at most c + 1. In particular, for every Q ∈ C, Q * is a path in G on at most c vertices. Note that if |C| ≥ q, then 6.4(b) holds, as required. Thus, we may assume that |C| < q, and so |V (C * )| < cq. In particular, W 0 \C * has at most cq components, and since the paths in P 0 are pairwise internally disjoint, it follows that there are at most |V (C * )| < cq paths P in P 0 for which P ∩ C * ̸ = ∅. This, along with the assumption that |P 0 | = c(p + 1)q and W 0 is an x-slash for P 0 in G, implies that there exist P ⊆ P 0 with |P| = p and V (P) ∩ C * = ∅, as well as a component W of W 0 \ C * ⊆ G \ {x, y}, such that for every P ∈ P, the unique neighbor of x in P belongs to W . In other words, W is an x-slash for P. Moreover, we have (V (P) ∪ W ) ∩ C * = ∅, and so by the maximality of C, there is no path Q of length at most c + 1 in V (P) ∪ W from x to y. Now P and W satisfy 6.4(a), as desired. ■
The next lemma is the main step in the proof of Theorem 6.3.
Lemma 6.5. For all c, q, t ∈ N, there is a constant µ = µ(c, q, t) ∈ N with the following property. Let G be a graph, let x, y ∈ V (G) be distinct and non-adjacent, and let P 0 be a collection of µ pairwise internally disjoint paths in G from x to y. Assume that there is an x-slash for P 0 in G. Then one of the following holds.
(a) G contains K t+1 or K t,t .
(b) G contains a c-hassle.
(c) There is a collection Q of q pairwise internally disjoint paths in G from x to y, each of length at most c + 1.
•, •) be as in Lemma 3.2, and let
); be as in Lemma 3.2. We will show that µ = µ(c, q, t) = c((c + 2)mΥ 2 + 1)q satisfies the lemma. Let G be a graph, let x, y ∈ V (G) be distinct and non-adjacent, let P 0 be a collection of µ pairwise internally disjoint paths in G from x to y, and let W 0 be an x-slash for P 0 in G.
Assume that none of the three outcomes of 6.5 hold. We apply Lemma 6.4 to x, y, P 0 and W 0 . In particular, since 6.5(c) is equivalent to Lemma 6.4(b), it follows from the choice of µ that: (13) There exists P ⊆ P 0 with |P| = (c + 2)mΥ 2 and a path W ⊆ W 0 such that:
• W is an x-slash for P in G; and
• there is no path Q of length at most c + 1 in V (P) ∪ W from x to y.
From now on, let P and W be as in (13). For every vertex v ∈ N V (P) (x), we denote by P v the unique path in P for which v is the unique neighbor of x in P v . Since W is an x-slash for P, it follows that N V (P) (x) ⊆ W . Let w 1 and w 2 be the ends of W . Since |P| = cmΥ 2 + 2mΥ 2 , it follows that one may choose 3m pairwise disjoint Υ 2 -subsets {U 1,i , V i , U 2,i : i ∈ N m } of N V (P) (x) ⊆ W , such that the following hold.
• For each i ∈ N m , there are Υ 2 pairwise disjoint paths {A v : v ∈ V i } in W , each on c vertices, such that for every v ∈ V i :
-A v contains v; and -Traversing W from w 1 to w 2 , every vertex in U 1,i appears before every vertex in A v , and every vertex in A v appears before every vertex in U 2,i . In particular, traversing W from w 1 to w 2 , every vertex in U 1,i appears before every vertex in V i , and every vertex in V i appears before every vertex in U 2,i (see Figure 12). • For every i ∈ N m-1 , traversing W from w 1 to w 2 , every vertex in U 2,i appears before every vertex in U 1,i+1 (see Figure 13). We deduce that: (14) For every i ∈ N m , there exist u 1,i ∈ U 1,i , v i ∈ V i and u 2,i ∈ U 2,i , for which A v i is disjoint from P u 1,i ∪ P u 2,i and anticomplete to (P u 1,i ∪ P u 2,i ) \ {x}.
are three collections of pairwise disjoint c-pairs over V (G), each of cardinality Υ 2 . By the choice of Υ 2 , we can apply Lemma 3.2 to A i , B 1,i , B 2,i . It follows
,i } satisfy Lemma 3.2(a) and 3.2(b). In fact, Lemma 3.2(a) along with the assumption that x, y / ∈ W , implies that for every
,i , for which A v i is anticomplete to (P u 1,i ∪ P u 2,i ) \ {x}. Suppose not. Note that for every v ∈ V ′ i , since v ∈ A v is a neighbor of x, it follows from the second bullet of (13) that y is anticomplete to A v . Consequently, by Lemma 3.2(b), there exists j ∈ {1, 2} such that for every v ∈ V i , there exists a vertex x v ∈ A v which has a neighbor in P * u for every u ∈ U ′ j,i . On the other hand, since b ≥ 2ct t , it follows that there exists
This, combined with the choice of b, Lemma 5.5, and the assumption that G is (K t+1 , K t,t )-free, implies that there exists a t t -meager (2ct t , 2c 2 t t )-cluster in G. But then by Theorem 6.2, G contains a c-hassle. This violates the assumption that 6.5(b) does not hold, and so proves (14).
Henceforth, for each i ∈ N m , let u 1,i ∈ U 1,i , v i ∈ V i and u 2,i ∈ U 2,i be as in (14). We write A i = A v i , P 1,i = P u 1,i and P 2,i = P u 2,i . Also, we denote by a 1,i , a 2,i the ends of A i , such that W traverses the vertices w 1 , a 1,i , a 2,i , w 2 in this order. It follows that W traverses the vertices w 1 , u 1,i , a 1,i , a 2,i , u 2,i , w 2 in this order, and a 1,i , a 2,i are the only vertices among u 1,i , a 1,i , a 2,i , u 2,i which can be the same (only if c = 1).
Let i ∈ N m be fixed. For each j ∈ {1, 2}, traversing a j,i -W -u j,i starting at a j,i , let w ′ j,i be the first vertex in a j,i -W -u j,i with a neighbor in P j,i \ {x} (note that w ′ j,i exists because u j,i has a neighbor in P j,i \ {x}). From ( 14), we know that A i is disjoint from and anticomplete to (P 1,i ∪ P 2,i ) \ {x}; in particular, for every j ∈ {1, 2}, u j,i ∈ P j,i \ {x} has a neighbor in the interior of a j,i -W -u j,i . It follows that for every j ∈ {1, 2}, the vertex w ′ j,i belongs to the interior of a j,i -W -u j,i , and there is a path R j,i in G from w ′ j,i to y whose interior is contained in P * j,i . For every i ∈ N m and each j ∈ {1, 2}, let R ′ j,i be the longest path of length at most c + 1 in R j,i \ {y} containing w ′ j,i . It follows that: (15) For every i ∈ N m and each j ∈ {1, 2}, we have R ′ j,i \ {w ′ j,i } ⊆ P * j,i . Consequently, the sets
Observe that by the choice of R ′ j,i , either R ′ j,i = R j,i \ {y}, in which case (15) follows immediately from the fact that R * j,i ⊆ P * j,i , or R ′ j,i is a path on c + 2 vertices with R ′ j,i \ {w ′ j,i } ⊆ P * j,i . This proves (15). Now, for each i ∈ N m , let
] be the walk such that traversing W i from φ W i (1) to φ W i (n W i ), we first traverse the path R ′ 1,i starting at the end distinct from w ′ 1,i and stopping at w ′ 1,i , then we traverse the path W ′ i from w ′ 1,i to w ′ 2,i , and then we traverse R ′ 2,i starting at w ′ 2,i (so we have n
In particular, we have W i ⊆ V (P * ) ∪ W . We claim that: (16) The following hold.
• For all i ∈ m , the walk W i is c-stretched and x has a neighbor in W i .
• For all i ∈ N m , the vertex x has no neighbors among the first and last c vertices of W i .
The first bullet is immediate from |A i | = c and the observation that both R ′ 1,i -w ′ 1,i -W -a 2,i and R ′ 2,i -w ′ 1,i -W -a 1,i are paths in G containing A i . Also, the third bullet is trivial, and the fourth is immediate from (15). It remains to prove the second bullet. Note that by the definition of R ′ 1,i and R ′ 2,i , either y has a neighbor among the first or the last c vertices of W i , or the first c + 1 vertices of W i are contained in P * 1,i , and the last c + 1 vertices of W i are contained in P * 2,i . In the former case, the result follows directly from the second bullet of (13), and in the latter case, the result follows from the fact that x has exactly one neighbor in P * 1,i and exactly one neighbor in P * 2,i . This proves (16). We can now finish the proof. For every k ∈ N c , let
From the choice of m and the third bullet of ( 16), it follows that B 1 , . . . , B c are collections of pairwise disjoint (2c + 2)-pairs over V (G), each of cardinality Υ 1 . The choice of Υ 1 in turn allows for an application of Lemma 3.2 to B 1 , . . . , B c . In particular, Lemma 3.2 (a) implies that for every k ∈ N c , there exists i k ∈ I k such that W i k \ W ′ i k and W i l are disjoint for all distinct k, l ∈ N c . This, combined with the third and the fourth bullet of (16), implies that W i 1 , . . . , W ic are pairwise disjoint. But now by the first two bullets of ( 16), the subgraph of G induced on {x} ∪ W i 1 ∪ • • • ∪ W ic is a c-hassle with neck x and walks W i 1 , . . . , W ic , contradicting the assumption that 6.5(b) does not hold. This completes the proof of Lemma 6.5. ■ From Lemma 6.5, we deduce the following: Lemma 6.6. For all c, d, q, t ∈ N, there is a constant ζ = ζ(c, d, q, t) ∈ N with the following property. Let G be a graph and let W be a d-loose polypath in G. Let x, y ∈ V (W) be distinct and non-adjacent, and let P be a collection of ζ pairwise internally disjoint paths in G from x to y with V (P) ⊆ V (W). Then one of the following holds.
(a) G contains K t+1 or K t,t .
(b) G contains a c-hassle.
(c) There exists a collection Q of q pairwise internally disjoint paths in G from x to y, each of length at most c + 1.
Proof. Let µ = µ(c, q, t) ∈ N be as in Lemma 6.5. We show that ζ(c, d, q, t) = 2dµ satisfies the lemma. Let W ∈ W such that x ∈ W . Then x has at most two neighbors in W . Also, since W is d-loose, it follows that x has neighbors in at most d -1 paths in W \ {W }. This, along with the fact that |P| = ζ ≥ 2(d -1)µ + 2, implies that there exists P 1 ⊆ P with |P 1 | = 2µ and a path W 1 ∈ W \ {W }, such that for every P ∈ P 1 , the unique neighbor of x in P belongs to W 1 . In particular, we have x / ∈ W 1 because W, W 1 ∈ W are distinct (hence disjoint) and x ∈ W . Since W 1 \ {y} has one or two components (depending on whether y ∈ W * 1 or not), it follows that there exist P 0 ⊆ P 1 with |P 0 | = µ as well as a component W 0 of W 1 \ {y}, such that for every P ∈ P 0 , the unique neighbor of x in P belongs to W 0 . Therefore, P 0 is a collection of µ pairwise internally disjoint paths in G from x to y, and W 0 is an x-slash for P 0 in G. Now the result follows from Lemma 6.5 applied to P 0 . ■
We can now restate and prove Theorem 6.3: Theorem 6.3. For all c, d, t ∈ N, there is a constant Ω = Ω(c, d, t) ∈ N with the following property. Let G be a t-clean graph. Assume that there exists a 2Ω-polypath in G which is both Ω-fancy and d-loose. Then there is a c-hassle in G.
Proof. Let η = η(c + 1, t) be as in Theorem 4.4. Let ζ = ζ(c, d, η, t) be as in Lemma 6.6. We define Ω = Ω(c, d, t) = κ(max{t η , ζ}, t) + 1, where κ(•, •) is as in Theorem 4.1. Let G be a t-clean graph and let W be a 2Ω-polypath in G which is both Ω-fancy and d-loose. Suppose for a contradiction that G does not contain a c-hassle.
Let
Then H is a t-clean graph which has a K Ω,Ω -minor. It follows that H has treewidth at least Ω, which along with Theorem 4.1 implies that there is a strong max{t η , ζ}-block in G. In particular, we may choose a t η -subset B of V (H) such that for every 2-subset {x, y} of B, there exists a collection P {x,y} of ζ pairwise internally disjoint paths in H from x to y. Since |B| = t η and since G is K t+1 -free, it follows from Theorem 5.3 that there exists a stable set A ⊆ B in H of cardinality η. Now, fix a 2-subset {x, y} of A. Then x, y are non-adjacent in G, and so by the choice of ζ, we can apply Lemma 6.6 to W and P {x,y} . Note that Lemma 6.6(a) violates the assumption that G is t-clean, and Lemma 6.6(b) violates the assumption that G contains no c-hassle. Thus, Lemma 6.6(c) holds, that is, there exists a collection Q {x,y} of η pairwise internally disjoint paths in G from x to y, each of length at most c + 1. But now A is a (c + 1)-short (not necessarily strong) η-block in G. Combined with the choice of η and Theorem 4.4, this violates the assumption that G is t-clean, hence completing the proof of Theorem 6.3. ■ Combining Theorem 5.1, 6.2 and 6.3, we deduce Theorem 6.1, restated below.
Theorem 6.1. For all c, t ∈ N, there is a constant Γ = Γ(c, t) such that every t-clean graph G of treewidth more than Γ contains a c-hassle.
Proof. Let l = 2c 2 t t and let s = 2ct t . Let Ω = Ω(c, l + t t s t t , t) be as in Theorem 6.3. Let
where γ(•, •, •, •, •) is as in Theorem 5.1. Let G be a t-clean graph of treewidth more than Γ. It follows from Theorem 5.1 that either there exists a t t -meager (s, l)-cluster in G, or there is 2Ω-polypath in G which is both Ω-fancy and (l + t t s t t )-loose. In the former case, by Theorem 6.2, G contains a c-hassle. Also, in the latter case, the choice of Ω along with Theorem 6.3 implies that G contains a c-hassle. This completes the proof of Theorem 6.1. ■
Finally, let us bring everything together and prove Theorem 1.7. First, from Theorem 6.1, we deduce that: Theorem 7.1. Let H be a finite set of graphs which is hassled. Then the class of all H-free graphs is clean.
Proof. Let H be a finite set of graphs which is hassled. In order to show that the class of all H-free graphs is clean, it is enough to prove, for every t ∈ N, that there is a constant ℓ = ℓ(t, H) ∈ N such that every t-clean graph of treewidth more that ℓ contains some graph H ∈ H.
We begin with setting the value of ℓ. Since H is hassled, it follows that for every t ∈ N, there is a constant c = c(t, H) ∈ N such that every (K t+1 , K t,t )-free c-hassle contains all components of some graph in H. Let Γ = Γ(c, t) be as in Theorem 6.1, and let ∆ = ∆(||H||, ||H||, t) be as in Lemma 2.4. Define
Let G be a t-clean graph of treewidth more than ℓ. Since ℓ ≥ Γ, by Theorem 6.1, there is an induced subgraph Ξ of G which is a c-hassle. This, combined with the assumption that H is hassled and G is (K t+1 , K t,t )-free, implies that there exists
Let m ∈ N be maximum such that there are m pairwise disjoint subsets W 1 , . . . , W m of V (G), each of cardinality at most ||H||, such that for every i ∈ N m there exists H ∈ H such that W i contains every component of H. We claim that: 1 ∆ > Γ. Thus, by Theorem 6.1, there is an induced subgraph Ξ ′ of G ′ which is a c-hassle. Since H is hassled and G is (K t , K t,t )-free, it follows that there exists W ′ ⊆ V (Ξ ′ ) ⊆ V (G ′ ) with |W ′ | ≤ ||H|| and H ∈ H such that W ′ contains every component of H. But this violates the maximality of m, and so proves (17).
By (17), we can choose pairwise disjoint subsets W 1 , . . . , W ||H||∆ of V (G), each of cardinality at most ||H||, such that for every i ∈ N ||H||∆ , there exists H i ∈ H such that W i contains every component of H i . Since |H| ≤ ||H||, it follows that there exists a graph H ∈ H, as well as I ⊆ N ||H||∆ with |I| = ∆, such that for every i ∈ I, we have H i = H. Also, since G is (K t , K t,t )-free, from the choice of ∆, it follows that there exist i 1 , . . . , i ||H|| ∈ I such that W i 1 , . . . , W i ||H|| are pairwise anticomplete in G.
Let K 1 , . . . , K h be the components of H. Then h ≤ ||H||, and for every j ∈ N h , there exists X j ⊆ W i j such that G[X j ] is isomorphic to
Now Theorem 1.7 is immediate from Theorems 2.1 and 7.1.
We conclude the paper with a brief discussion around explicit constructions of tasselled families. There is one particularly nice example of tasselled families, described in the following corollary of Theorem 1.6 (we omit the proof as it is straightforward).
Corollary 8.1. Given a, b ∈ N, let H a,b be the set of all strands F such that the path of F has vertices v 1 , . . . , v a+b+1 in this order, and the neck x of F is non-adjacent to v 1 , . . . , v a and adjacent to v a+1 . (Thus, H a,b contains 2 b distinct graphs, corresponding to all possible ways for x to be adjacent to v a+2 , . . . , v a+b+1 .) Then H a,b is tasselled.
While a full description of all tasselled families remains unknown, a promising approach is to attempt to model the "tasselled" property word-combinatorially, and then use results from the literature on formal languages in order to gain insight into the graph problem.
One way to view a strand F is as a binary string denoting neighbors of the neck in the path. More explicitly, for a strand F with neck v and path P , if p 1 , . . . , p t are the vertices of P in order, then we can define the binary string S P,v = b 1 . . . b t where b i = 1 if p i ∈ N (v), and b i = 0 otherwise (note that the string S P,v is uniquely defined up to reversal). Moreover, every strand F of a c-tassel with neck v corresponds to a binary string (again, unique up to reversal) which starts and ends with at least c zeroes, but which is not an all-zero string; let us say such a string is c-padded.
For a graph K, we say a vertex v ∈ V (K) is a neck for K if every component of K \{v} is a path, and we denote by S K,v the set of all strings S P,v where P is a component of K \ {v}. It is easy to see that: Theorem 8.2. Let H be a set of graphs. Then H is tasselled if and only if there exists c such that, for every c-padded string S, there is a graph H ∈ H with the following property. For every component K of H, one may choose a neck v of K such that for every string S ′ ∈ S K,v , the string S contains either S ′ or its reverse as a consecutive substring.
There is an interesting special case of this where every graph in H is a c ′ -tassel for some c ′ ∈ N. Note that in this case, every H ∈ H is connected and the set S H,v has cardinality one for each neck v of H. So the question of whether H is tasselled translates into: Question 8.3. For which sets S of strings is it true that there is a constant c = c(S) ∈ N such that every c-padded string S contains either a string in S or the reverse of a string in S as a consecutive substring?
If the above holds for some fixed c, let us call such a set S a c-unavoidable language. In view of our aim, it is of particular interest to identify the minimal c-unavoidable languages (with respect to the inclusion). In particular, the only sets of cardinality one which are c-unavoidable for some c ∈ N are of the form S = {0 • • • 01} (up to reversal) and S = {0 • • • 0}, and one may observe that this matches the outcome of Theorem 1.5. However, in general, larger c-unavoidable languages seem harder to describe; for example, the following is 3-unavoidable: {00011, 0001000, 1010, 010010, 111, 110011, 11011, 110010011, 00010011001000}.
On the other hand, for a finite set S of strings, it is finitely testable if S is c-unavoidable for some c ∈ N. To see this, note that if there is a c-padded string S which does not contain any string in S nor the reversal of a string in S, then, assuming s to be the length of the longest string in S, one may choose S such that c ≤ s and S has length at most (s + 2)2 s (which follows by noticing that a repetition of a consecutive substring of length s in S not containing the first or last c bits can be used to shorten S).
The following, closely related question, has been studied before:
Question 8.4. For which sets S of strings is it true that every sufficiently long string contains a string in S as a consecutive substring?
These sets S are called unavoidable languages (see, for example [15,16]). In particular, in [4,5] it is shown that every minimal unavoidable language is finite. This is not the case for c-unavoidable languages; for example, S = {01 k 0 : k ∈ N} is 1-unavoidable. However, if we omit the string 01 k 0 for some k ∈ N, then 0 . . . 01 k 0 . . . 0 avoids S. It would be interesting to consider which results on unavoidable languages generalize to c-unavoidable languages.