Induced subgraphs and tree decompositions XIX. Thetas and forests

This paper proves that for any forest $H$ and any hereditary class of theta-free graphs excluding $H$ and the line graphs of all subdivisions of some wall, the treewidth is bounded by a polynomial function of the clique number, a result shown to be optimal as both exclusion conditions are necessary.

The Gist

Imagine you are an architect trying to build a massive, complex city (a graph). In this city, the "streets" are connections between buildings (vertices), and the "blocks" are groups of buildings all connected to each other (cliques).

Your goal is to understand how "twisty" or "complicated" this city can be. In math, we call this complexity treewidth.

• A city with low treewidth is like a simple tree or a straight road: easy to navigate, easy to plan, and easy to break down into small, manageable pieces.
• A city with high treewidth is like a giant, tangled web of highways, tunnels, and overpasses. It's a nightmare to navigate, and you can't easily break it down.

The Big Question

Mathematicians have long known that if you forbid certain "bad shapes" (like a giant grid), the city must stay simple (low treewidth). This is a famous rule called the Grid Theorem.

But what if you only forbid shapes that appear as induced subgraphs? This means you can't have a specific pattern of buildings and streets, even if they are hidden deep inside the city.

The paper asks: What specific patterns must we ban to guarantee the city stays simple?

The Villains: Thetas and Forests

The authors focus on two specific types of "bad guys" in our city:

1. The Theta ($\theta$): Imagine a "theta" as a traffic jam where three different roads start at one intersection, wind around, and all meet at another intersection without crossing each other in the middle. It's a specific, messy loop.
   • The Problem: If you just ban the "Theta," the city can still become incredibly complex (high treewidth). You can build a city with no Thetas that is still a tangled mess.
2. The Forest: A "forest" is just a collection of trees (no loops at all).
   • The Twist: The authors discovered that if you ban any specific tree shape (like a specific branching pattern) AND you ban the Thetas, something magical happens.

The Main Discovery (The "Aha!" Moment)

The paper proves a powerful rule:

If your city has no Thetas AND no specific tree shapes, then the complexity of the city is strictly limited by how many buildings are packed tightly together (the "clique number").

The Analogy:
Imagine you are trying to build a skyscraper (high treewidth).

• If you allow Thetas, you can build a skyscraper that looks like a tangled ball of yarn.
• If you allow any tree shape, you can build a skyscraper that looks like a giant, branching coral reef.
• BUT, if you ban both the tangled yarn (Thetas) and the coral reef (Forests), the only way to make a skyscraper is to stack blocks on top of each other in a very orderly, predictable way. You can't make it infinitely complex. The height of your building is now mathematically tied to how wide the base is.

Why is this a Big Deal?

The authors show that this rule is the best possible.

• If you don't ban Thetas, you can build a mess.
• If you don't ban Forests, you can build a mess.
• You need both bans to force the city to be simple.

They also prove that the relationship between the "messiness" (treewidth) and the "crowdedness" (clique number) isn't just a limit; it's a polynomial limit.

• Simple terms: If you double the crowdedness, the messiness doesn't explode into infinity; it grows in a predictable, manageable way (like squaring the number, rather than raising it to the power of a million).

The "Layered Wheels" Mystery

In the past, mathematicians found a class of weird, complex cities called "Layered Wheels" that were hard to understand. These cities were incredibly complex but didn't contain the usual "bad guys" (like big grids).

• The authors realized that these "Layered Wheels" are actually the only way to build a complex city if you allow Thetas and Trees.
• By banning Trees (specifically forests), they effectively "cracked the code" on these Layered Wheels. They showed that once you ban trees, these complex wheels can't exist anymore. The city collapses back into something simple.

What Does This Mean for the Real World?

This isn't just abstract math. Graphs are used to model everything:

• Computer Networks: How data flows.
• Social Media: How people connect.
• Biology: How proteins interact.

Many problems on these networks are "NP-hard," meaning they are computationally impossible to solve for huge, messy networks.

• The Good News: Because this paper proves that these specific types of networks (Theta-free + Forest-free) are actually "simple" (low treewidth), we can now use fast algorithms to solve problems that were previously impossible.
• The Result: We can now find the "Maximum Weight Independent Set" (a fancy way of finding the best group of non-conflicting items) in these networks very quickly, almost as fast as reading a book.

Summary

Think of this paper as a new Zoning Law for graph cities.

• Old Law: "No giant grids allowed." (Too weak; cities were still messy).
• New Law: "No Thetas AND no specific tree shapes allowed."
• Result: The city is forced to be simple, predictable, and easy to solve. The authors proved this is the perfect balance: remove either rule, and the chaos returns.

Technical Summary

Here is a detailed technical summary of the paper "Induced Subgraphs and Tree Decompositions XIX. Thetas and Forests" by Chudnovsky, Codsi, Hajebi, and Spirkl.

1. Problem Statement and Motivation

The paper addresses a fundamental question in structural graph theory: Which induced subgraphs must be excluded to guarantee that a graph class has bounded treewidth?

• Context: The Robertson-Seymour Grid Theorem (Theorem 1.1) establishes that for minors, excluding subdivisions of a fixed wall ($W_{t \times t}$) is sufficient to bound treewidth. However, for induced subgraphs, this is not true.
• The Challenge: Even excluding subdivided walls as induced subgraphs does not bound treewidth. Furthermore, excluding thetas (induced subdivisions of $K_{2,3}$) is insufficient, as there exist theta-free graphs with arbitrarily large treewidth (e.g., complete graphs and line graphs of subdivided walls).
• The Gap: Previous work (Sintiari and Trotignon) showed that even restricting to triangle-free theta-free graphs does not bound treewidth. The remaining "obstructions" to bounded treewidth in theta-free graphs are complex structures known as layered wheels.
• The Specific Question: If we exclude a specific forest $H$ and the line graphs of subdivided walls, does the treewidth become bounded in theta-free graphs? The authors aim to prove that the answer is yes, and specifically, that the treewidth is bounded by a polynomial function of the clique number.

2. Key Definitions

• Theta: A graph isomorphic to a subdivision of $K_{2,3}$. A graph is theta-free if it contains no induced theta.
• Wall ($W_{t \times t}$): A $t \times t$ hexagonal grid.
• Line Graph of a Subdivided Wall: A known class of theta-free graphs with unbounded treewidth.
• $(H, K_t)$-free: A graph containing no induced subgraph isomorphic to $H$ and no clique of size $t$.
• $\lambda$-separable: A graph $G$ is $\lambda$-separable if for any two non-adjacent vertices $x, y$, there are no $\lambda$ pairwise internally disjoint paths between them.

3. Main Results

The paper's primary contribution is Theorem 1.4, which establishes a polynomial bound on treewidth for a specific class of theta-free graphs.

Theorem 1.4:
For every integer $r$ and every forest $H$, there exists a constant $d_{1.4}(H, r)$ such that for every integer $t$, every theta-free graph $G$ that is $(H, K_t)$-free and contains no induced subgraph isomorphic to the line graph of any subdivision of $W_{r \times r}$ satisfies:
$$tw(G) \le t^{d_{1.4}}$$

Corollary 1.5 (Characterization):
Let $H$ be a forest and $\mathcal{C}$ be a hereditary class of theta-free graphs such that $H \notin \mathcal{C}$. The following are equivalent:

1. $\mathcal{C}$ excludes the line graphs of all subdivisions of some wall $W_{r \times r}$.
2. There exists a function $f$ such that $tw(G) \le f(\omega(G))$ for all $G \in \mathcal{C}$.
3. There exists a polynomial function $f$ such that $tw(G) \le f(\omega(G))$ for all $G \in \mathcal{C}$.

Corollary 1.7 (Algorithmic Implication):
For the classes described above, the Tree Independence Number is poly-logarithmic in the number of vertices. Consequently, the Maximum Weight Independent Set problem (and other NP-hard problems) can be solved in quasi-polynomial time for these graph classes.

4. Methodology and Proof Strategy

The proof is divided into two main stages: reducing the problem to a separability property and then proving that property via a "growing tree" argument.

Step 1: Reduction to Separability (Section 2)

The authors reduce Theorem 1.4 to Theorem 2.1, which concerns the separability of the graph.

• Theorem 2.1: For every forest $H$ (on at most $h$ vertices) and integer $t$, every theta-free $(H, K_t)$-free graph is $t^{d_{2.1}}$-separable.
• Logic: If a graph is highly separable (low $\lambda$), and it excludes certain induced minors (specifically walls and large complete bipartite graphs), then its treewidth is bounded.
• Tools Used:
  • Theorem 2.2 (Hajebi): Bounded treewidth for $\lambda$-separable graphs excluding specific induced minors.
  • Theorem 2.3 & Lemma 2.4: Relate the existence of large induced minors (like $K_{s,s}$ or walls) to the existence of specific structures (constellations) or subdivisions.
  • The proof shows that if the graph is not separable, it must contain a structure (a large tree-like subgraph) that forces the presence of the forbidden forest $H$ or a forbidden induced minor, leading to a contradiction.

Step 2: Growing a Tree (Section 3)

The core of the proof is Lemma 3.1, which constructs a specific tree structure within the graph.

• Goal: Show that if there are many internally disjoint paths between two non-adjacent vertices $x$ and $y$, the graph must contain a large induced $(a, b)$-tree rooted at $x$.
• $(a, b)$-Tree: A tree where the root has degree $a$, non-leaf nodes have degree $a$, and leaves are at a specific distance from the root.
• Technique:
  1. Path Selection: Start with a large set of disjoint paths between $x$ and $y$.
  2. Stable Set Extraction: Use Ramsey-type theorems (Theorem 3.4, Lemma 3.5, Lemma 3.6) to find a large stable set of "entry points" on these paths.
  3. Digraph Analysis: Construct a digraph representing connections between paths. Use Lemma 3.3 to find either a large stable set or a dense structure.
  4. Constricted Sets: Apply Theorem 3.2 (Chudnovsky & Codsi), which limits the number of disjoint paths from a vertex to a "constricted" stable set in $K_{s,s}$-free graphs.
  5. Induction: The proof proceeds by induction on the depth $b$ of the tree. If the graph is not separable, one can recursively "grow" a larger tree structure.
  6. Contradiction: If the graph is not $t^d$-separable, Lemma 3.1 guarantees the existence of an $(h+1, h+1)$-tree. Since $H$ is a forest with $\le h$ vertices, this large tree must contain $H$ as an induced subgraph, contradicting the assumption that $G$ is $H$-free.

5. Significance and Impact

1. Resolution of a Conjecture: The paper provides a near-complete answer to the "induced subgraph" version of the Grid Theorem for theta-free graphs. It confirms that the only obstructions to bounded treewidth in theta-free graphs are the "layered wheels" (which contain large cliques or line graphs of walls).
2. Polynomial vs. Exponential: Previous results often yielded exponential bounds or required stronger exclusions (like prism-free). This paper proves a polynomial bound in terms of the clique number, which is a significant strengthening.
3. Algorithmic Consequences: By establishing a poly-logarithmic bound on the tree independence number, the paper implies that hard combinatorial optimization problems (like Maximum Independent Set) become tractable (quasi-polynomial time) for these broad classes of graphs.
4. Structural Insight: The paper characterizes the local structure of theta-free graphs with large treewidth, showing they are "locally canonical" (resembling layered wheels) but globally constrained by the exclusion of forests and wall-line-graphs.

In summary, this work bridges the gap between minor-based and induced-subgraph-based structural graph theory, proving that excluding a single forest and the line graphs of walls is sufficient to tame the treewidth of theta-free graphs.