Induced subdivisions of $K_{d+1}$ in graphs of high girth

The paper proves that every graph with a minimum degree of at least $10^8$and a girth of at least$10^8$contains an induced subdivision of a complete graph$K_{k+1}$, thereby resolving a long-standing problem posed by Kühn and Osthus.

The Gist

Imagine you are a city planner looking at a map of a very strange, sprawling city. This city has two main rules:

1. Every neighborhood is busy: Every single house (vertex) is connected to at least $k$ other houses (edges). The city is dense with connections.
2. No short loops: If you try to drive a car around a block and get back to where you started without turning around, you have to drive a very long way. There are no small circles (triangles, squares, etc.) in the city layout. In math terms, this is called having a "high girth."

The big question mathematicians have been asking for years is: If a city is this busy and has no small loops, does it secretly contain a specific, complex "super-structure" hidden inside it?

Specifically, they wanted to know if you can always find a "perfectly isolated" version of a giant hub (a complete graph, or $K_{k+1}$) where the connections between the hubs are long, winding roads that don't accidentally touch any other parts of the city.

This paper, by António Girão and Zach Hunter, says YES. They proved that if your city is busy enough (minimum degree $k$) and has no small loops (girth at least 108), you can always find this hidden super-structure.

The Analogy: The "Tree Forest" and the "Hidden Web"

To understand how they proved this, let's use a metaphor.

1. The Problem: Finding a "Star" in a Jungle

Imagine you are looking for a specific shape: a giant starfish ($K_{k+1}$) where the center is a hub, and the arms are long, winding paths.

• The Catch: These paths must be "induced." This means the paths can't have any extra branches sticking out to the side that connect to other parts of the starfish. They must be clean, isolated tunnels.
• The Difficulty: In a normal city, if you try to build these long paths, they might accidentally cross each other or hit a random building, ruining the "clean" look.

2. The Strategy: "Pruning the Jungle"

The authors realized that because the city has no small loops, the local area around any house looks like a tree (a branching structure with no circles). If you zoom in close, it's very orderly.

They used a strategy called "Pruning and Random Sampling":

• Step 1: The Random Filter. Imagine you have a giant net. You throw it over the city and randomly keep only a few houses. Because the city has no small loops, if you pick your houses carefully, the ones you keep are far apart from each other.
• Step 2: Building the Bridges. Between the houses you kept, you look for long, winding roads that connect them. Because the city is so busy (high degree), there are many roads to choose from.
• Step 3: The "Good" Houses. They proved that if you pick the right random houses, you will find a special group of "Good Houses." Each Good House is connected to exactly two of your "Bridge Houses" via a long, clean road.
• Step 4: The Magic Web. If you have enough Good Houses, you can arrange them so that they form a perfect web. The "Good Houses" act as the corners of your starfish, and the "Bridge Houses" act as the long, clean arms.

3. Why "High Girth" is the Hero

Why did they need the "no small loops" rule?
Think of it like a crowded party. If everyone is standing in a tight circle (a small loop), it's impossible to walk from one side of the room to the other without bumping into someone.
But if everyone is spread out in a huge, open field with no small circles (high girth), you can draw long, winding paths between people without them ever crossing or touching the wrong people. The "high girth" guarantees that the city is locally sparse, giving the authors enough room to weave their clean, isolated paths.

The "Magic Number" (108)

You might notice the number 108 appears everywhere in the paper (108 connections, 108 loop size).

• Is 108 the perfect number? No. The authors admit they didn't try to find the smallest possible number. They picked 108 because it made the math work without getting too messy to read.
• The Real Takeaway: The exact number doesn't matter as much as the fact that a constant number exists. Before this paper, we didn't know if you needed a loop size of 108, or 1,000,000, or infinity. They proved that you only need a fixed amount of "space" (girth) to guarantee this structure exists, no matter how big the graph gets.

Summary in Plain English

If you have a graph (a network) that is:

1. Busy enough (everyone has many friends), and
2. Loopy-free enough (no short circles),

Then, deep inside that network, there is guaranteed to be a perfectly isolated, giant hub made of long, clean paths. It's like finding a secret, pristine garden inside a chaotic, overgrown jungle.

This solves a puzzle that mathematicians had been trying to crack for decades, proving that "local sparsity" (no small loops) combined with "global density" (high connections) forces the existence of these complex, beautiful structures.

Technical Summary

Here is a detailed technical summary of the paper "Induced Subdivisions of $K_{d+1}$ in Graphs of High Girth" by António Girão and Zach Hunter.

1. Problem Statement and Context

The Core Problem:
The paper addresses a fundamental question in extremal graph theory regarding the existence of induced subdivisions of large complete graphs ($K_t$) in graphs with high minimum degree and high girth.

• Background: Classical results (Komlós–Szemerédi, Bollobás–Thomason) establish that graphs with average degree $\Theta(t^2)$ contain a subdivision (topological minor) of $K_t$.
• Refinement: Mader and later Kühn and Osthus showed that for graphs with high girth, the minimum degree condition can be significantly lowered to guarantee a subdivision of $K_t$. Specifically, a minimum degree of $t-1$ is sufficient for large enough girth.
• The Open Question: Kühn and Osthus (attributing to Shi) asked if this holds for induced subdivisions. That is, does there exist a function $h(r)$ such that every graph with minimum degree $r$ and girth at least $h(r)$ contains an induced subdivision of $K_{r+1}$?
• Significance: An induced subdivision is a much stronger condition than a standard subdivision because it forbids any "chords" (extra edges) between the vertices of the subdivision paths. High girth is a natural hypothesis to force local sparsity, but ensuring the induced property globally is highly non-trivial.

The Main Result:
The authors provide a positive answer to this problem, proving that $h(r)$ is bounded by an absolute constant.

Theorem 1.1: Let $G$ be a graph with minimum degree $d \ge 10^8$ and girth at least $10^8$. Then$G$contains an induced subdivision of$K_{d+1}$.

Note: The authors explicitly state that the constants ($10^8$) are not optimized for readability but believe much lower constants are achievable with the same techniques.

---

2. Methodology and Technical Framework

The proof is a sophisticated combination of probabilistic methods, structural graph theory, and iterative reduction. The strategy can be broken down into the following key components:

A. Structural Decomposition and Degeneracy

The proof relies on the concept of degeneracy. The authors first reduce the graph to a $(d+1)$-degenerate subgraph. This allows them to order vertices such that each vertex has few "right-neighbors" (neighbors appearing later in the order), which is crucial for controlling dependencies in probabilistic arguments.

B. The "Branchable" Structure (The Core Mechanism)

The central technical innovation is the construction of a specific structure (Lemma 4.1, Claim 4.2) that guarantees an induced subdivision.

1. Auxiliary Graph $H$: The authors construct an auxiliary graph $H$ on a subset of vertices $S$.
2. Paths: For every edge in $H$, they associate an induced path $P_e$ in the original graph $G$ of length at most 300.
3. Branchable Vertices: A vertex $v \in S$ is called branchable if it has $d$ neighbors in $H$ such that the corresponding paths in $G$ form an induced star (a subdivision of a star graph) centered at $v$.
4. Connectivity: If $H$ is sufficiently connected (specifically $11d^2$-connected) and contains$d+1$branchable vertices that are pairwise far apart, then$G$contains an induced subdivision of$K_{d+1}$.
   • Why this works: The high connectivity of $H$ allows the authors to find disjoint paths between the branchable vertices. The "branchable" property ensures that the connections to the "leaves" of the subdivision are induced (no extra edges). The high girth of $G$ ensures that the paths themselves do not create unwanted cycles or chords.

C. Probabilistic Construction via Lovász Local Lemma

To find the structure described above, the authors use the Lovász Local Lemma (LLL).

• They define a random subset $S$ of vertices.
• They define "bad events" where a vertex fails to be branchable or the connectivity of $H$ drops.
• By carefully analyzing the dependencies (using the degeneracy and girth constraints), they show that the probability of avoiding all bad events is positive. This proves the existence of a subset $S$ and a subgraph $H$ with the required properties (high minimum degree and many branchable vertices).

D. Handling Maximum Degree

The proof splits into two main cases based on the maximum degree ($\Delta(G)$) of the graph:

1. Bounded Maximum Degree ($\Delta(G) \le d^{35}$):

   • This is the primary technical case handled by Lemma 4.1.
   • The authors use the probabilistic method (LLL) to find the "branchable" structure directly.
   • They utilize Lemma 3.3 (a result on finding highly connected subgraphs with small boundaries) to refine the auxiliary graph $H$ into a highly connected subgraph $H'$ that preserves the branchable property.

2. Unbounded Maximum Degree:

   • If the graph has vertices with very high degree, the authors use a reduction strategy.
   • They identify a set of high-degree vertices $B$ and a set of low-degree vertices $A$.
   • Case 1 (Large Independent Set): If there is a large independent set $Y$ connected to $B$ in a specific way, they use Lemma 3.1 (finding induced subdivisions in unbalanced bipartite graphs) to solve the problem directly.
   • Case 2 (Small Independent Set): If the independent set is small, they iteratively delete low-degree vertices (similar to the proof of Lemma 3.3) to obtain a subgraph $G''$ where the maximum degree is effectively bounded (polynomial in $d$) and the minimum degree is still high. This reduced graph $G''$ then falls under the scope of Lemma 4.1.

---

3. Key Contributions

1. Resolution of the Shi/Kühn-Osthus Problem: The paper definitively answers the question of whether high girth forces induced subdivisions of large cliques. The answer is yes, provided the girth is a sufficiently large absolute constant.
2. Absolute Constant Bound: Unlike previous results where the required girth might depend on the clique size, this paper shows that a fixed girth (e.g., $10^8$) suffices for *any* minimum degree$d$(provided$d$ is large enough).
3. New Structural Lemma (Branchability): The introduction of the "branchable" vertex concept within a probabilistic framework provides a powerful new tool for constructing induced subdivisions. It bridges the gap between finding a topological minor and ensuring the induced property.
4. Integration of Tools: The paper successfully integrates:
   • Lovász Local Lemma for existence proofs in sparse random settings.
   • Mader-type results for finding highly connected subgraphs.
   • Degeneracy arguments to control edge density and dependencies.
   • Chernoff bounds to ensure concentration of measure in the random selection of vertices.

---

4. Results and Significance

Primary Result:
Every graph with minimum degree $d \ge 10^8$ and girth $\ge 10^8$ contains an induced subdivision of $K_{d+1}$.

Significance:

• Theoretical Impact: This result strengthens the understanding of the relationship between local sparsity (girth) and global structure (cliques). It demonstrates that high girth is a potent enough condition to force not just the existence of a subdivision, but an induced one, which is a much stricter requirement.
• Methodological Advancement: The techniques developed, particularly the "branchable" structure and the specific application of the Local Lemma to preserve induced properties, are likely to be applicable to other problems in extremal graph theory involving induced subgraphs.
• Optimality: The minimum degree condition ($d$) is tight (one cannot guarantee a $K_{d+1}$ subdivision with minimum degree $d-1$). The paper leaves open the optimization of the girth constant, suggesting that $10^8$ is likely far from the true threshold, but the existence of some constant is the critical breakthrough.

In summary, Girão and Hunter have solved a long-standing open problem by proving that high girth is sufficient to force the existence of large induced clique subdivisions, utilizing a novel probabilistic-structural approach that combines connectivity, degeneracy, and the Lovász Local Lemma.