Concentration of the largest induced tree size of $G_{n,p}$ around the standard expectation threshold

This paper extends the known concentration of the largest induced tree size in random graphs $G_{n,p}$ to all vanishing edge probabilities $p \gg n^{-1/2} \ln^{3/2} n$ and demonstrates that for sparser graphs where $n^{-1} \ll p \ll n^{-1/2}$, this size fails to concentrate around the standard expectation threshold.

The Gist

Imagine you are a city planner looking at a massive, randomly generated map of a city called $G_{n,p}$.

In this city:

• There are $n$ people (vertices).
• Every pair of people has a chance to become friends (an edge). The chance is $p$.
• If $p$ is high, everyone is friends with everyone. If $p$ is low, friendships are rare.

Your goal is to find the largest "Tree Party" in this city.
A Tree Party is a group of people who are all connected to each other in a specific way:

1. They form a single, connected group (no one is left out).
2. There are no loops (if A is friends with B, and B with C, A cannot be friends with C, or else it's a circle, not a tree).
3. Crucially: No one outside this party is friends with exactly one person inside the party. (If they were, that outsider could just join the party and make it bigger, so it wouldn't be the "largest" possible tree).

The paper asks: How big is the biggest Tree Party we can expect to find? And, more importantly, is the size of this party always very predictable, or does it jump around wildly?

The Big Question: Is the Size Predictable?

In math, we say a number is "concentrated" if, no matter how you roll the dice to build the city, the answer is almost always one of two very close numbers (like 100 or 101). It doesn't jump from 100 to 200.

For a long time, mathematicians knew that if the city is very "dense" (lots of friendships, high $p$), the size of the Tree Party is very predictable. It's always either $k$ or $k+1$.

What this paper does:
The author, Jakob Hofstad, pushes the boundaries. He asks: "What happens if the city gets very sparse? What if friendships are rare?"

He finds two main results:

1. The "Sweet Spot" (When $p$ is small, but not too small)

If the friendship probability $p$ is small, but still bigger than roughly $1/\sqrt{n}$ (think of it as a city where everyone has a few friends, but not a crowd), the answer is still predictable.

• The Analogy: Imagine you are looking for the biggest circle of friends in a large town. Even if the town is quiet, you will almost always find a circle that is either 50 people or 51 people. It never jumps to 40 or 60.
• The Math: The paper proves that for a wide range of sparse cities, the size of the largest tree is "concentrated" on two values. It's a very stable number.

2. The "Chaos Zone" (When $p$ is very, very small)

However, if the city gets extremely sparse (friendships are so rare that $p$ is less than $1/\sqrt{n}$), the predictability breaks down.

• The Analogy: Imagine a ghost town where people barely know each other. In this scenario, the size of the "Tree Party" becomes unpredictable. It doesn't settle on 50 or 51. Instead, it might be 40 in one version of the city, and 65 in another.
• The "Expectation Threshold": Usually, mathematicians guess the size of the biggest tree by calculating the "average" (expectation). They say, "On average, we expect a tree of size $k$."
  • In the "Sweet Spot," the actual biggest tree is very close to this average.
  • In the "Chaos Zone," the actual biggest tree is much smaller than the average suggests. The "average" is a lie because the rare, huge trees that pull the average up simply don't exist in the real world when the city is too sparse.

How Did They Prove This? (The Detective Work)

To solve this, the author used three different "counting tools" (random variables):

1. Tool X (The Simple Counter): Just counts every possible tree.

   • Result: Good for finding the upper limit (the maximum possible size), but it overestimates things because it counts trees that aren't "maximal" (trees that could easily grow bigger).

2. Tool Y (The Strict Counter): Counts trees where everyone outside the tree has at least 3 friends inside the tree.

   • Why? If someone outside has only 1 or 2 friends inside, they might be able to join. If they have 3, they are "locked out."
   • Result: This tool worked perfectly for the "Sweet Spot." It proved that the tree size is stable and predictable.

3. Tool W (The Maximal Counter): Counts trees where no one outside has exactly 1 friend inside.

   • Result: This tool was used for the "Chaos Zone." It showed that when the city is too sparse, the "Maximal" trees are actually much smaller than the simple average predicted. The "drift" (the gap between the average and reality) becomes huge.

The "Bottleneck" Explained Simply

The paper identifies a specific "tipping point" in the density of the city.

• Above the line: The city is dense enough that the "Strict Counter" (Tool Y) works. The math holds up, and the tree size is stable.
• Below the line: The city is too sparse. The "Strict Counter" fails because the "drift" in the math becomes too large. The tree size becomes erratic and smaller than expected.

Why Does This Matter?

This isn't just about trees in graphs. It's about understanding complex systems (like social networks, the internet, or biological networks).

• Stability: It tells us when a system is stable and predictable (you can rely on the average).
• Instability: It tells us when a system is fragile and the "average" is a dangerous lie.
• The Method: The author shows that to understand very sparse networks, you can't just count the obvious things (like independent trees). You have to look for "clusters" or "almost-independent" groups, a technique that is much harder but necessary for the "Chaos Zone."

In summary: The paper maps out exactly how sparse a network can get before the size of its largest "tree-like" structure stops being predictable and starts behaving erratically. It confirms that for a surprisingly wide range of sparse networks, things are still orderly, but once you cross a specific threshold, chaos takes over.

Technical Summary

Here is a detailed technical summary of the paper "Concentration of the largest induced tree size of $G_{n,p}$ around the standard expectation threshold" by Jakob Hofstad.

1. Problem Statement

The paper investigates the size of the largest induced tree, denoted as $T(G)$, in a binomial random graph $G_{n,p}$.

• Context: Previous work by Erdős and Palka established the asymptotic size for constant $p$. Later, Kamaldinov, Skorkin, and Zhukovskii proved that for constant $p$, $T(G_{n,p})$ is concentrated on two consecutive values (2-point concentration). Oropeza extended this to vanishing $p$ where $p > n^{-e^{-2}/(3e^{-2}) + \epsilon}$.
• Gap: The behavior of $T(G_{n,p})$ for smaller vanishing $p$ (specifically $p \ll n^{-1/2}$) was unknown.
• Objective: To determine the range of $p$ for which $T(G_{n,p})$ exhibits 2-point concentration and to analyze the behavior of the variable when it falls below this threshold, specifically regarding the "expectation threshold."

2. Methodology

The author employs the first and second moment methods combined with the introduction of specialized random variables to handle the dependencies inherent in induced subgraphs.

Key Random Variables

1. $X_k$: The number of induced subgraphs of size $k$ that are trees.
   • Used to define the "expectation threshold" $k_0$, where $\mathbb{E}[X_k]$ transitions from $\omega(1)$ to $o(1)$.
2. $Y_k$: The number of induced trees of size $k$ such that every vertex outside the tree has at least 3 neighbors inside the tree.
   • This restriction is crucial for the second moment method. It ensures that if a tree exists, it is "robust" against small perturbations, reducing the variance of the count.
3. $W_k$: The number of maximal induced trees of size $k$ (trees where no vertex outside has exactly one neighbor inside).
   • Used to prove that for very small $p$, the size of the largest induced tree cannot be concentrated near the expectation threshold.

Analytical Techniques

• Stirling's Approximation: Used extensively to estimate factorials and binomial coefficients in the expectation calculations.
• Second Moment Method (Chebyshev's Inequality): To prove concentration, the author shows that $\text{Var}(Y_k) / \mathbb{E}[Y_k]^2 = o(1)$. This involves splitting the sum of covariances based on the size of the intersection $|A \cap B| = \ell$ between two potential trees and the number of components $m$ in their intersection.
• Case Analysis: The proof of the second moment bound is divided into cases based on the overlap size $\ell$ (small vs. large overlap) and the number of components $m$ in the intersection.
• Drift Analysis: For small $p$, the author analyzes the ratio $\mathbb{E}[W_k]/\mathbb{E}[X_k]$, showing that the expectation of maximal trees "drifts" significantly away from the expectation of all trees, preventing concentration.

3. Key Contributions and Results

The paper establishes Theorem 1, which provides a comprehensive characterization of $T(G_{n,p})$ across different regimes of $p$:

(i) Definition of the Threshold

There exists an integer function $k_0(n, p)$ such that for $1/n \ll p \ll 1/\ln^2 n$:

• The largest $k$ where $\mathbb{E}[X_k] \geq 1$ is either $k_0$ or $k_0 + 1$.
• $k_0$ is asymptotically given by:
  $$k_0 \approx \frac{2 \ln(np) + 2}{p}$$

(ii) Two-Point Concentration (Upper Bound Regime)

If $p = \omega(n^{-1/2} \ln^{3/2} n)$, then:
$$T(G_{n,p}) \in \{k_0, k_0 + 1\} \quad \text{whp (with high probability)}$$

• Significance: This extends the known range of concentration significantly lower than previous results. The proof relies on the variable $Y_k$ and the second moment method, showing that the variance is negligible in this regime.

(iii) Non-Concentration (Lower Bound Regime)

If $p = o(n^{-1/2})$, then:
$$T(G_{n,p}) < k_0 - \frac{1}{4np^2} \quad \text{whp}$$

• Significance: This result demonstrates that for sufficiently small $p$, the size of the largest induced tree cannot be concentrated around the standard expectation threshold $k_0$. The "drift" caused by the maximality condition (using $W_k$) pushes the actual maximum size significantly below the point where the expected number of trees is 1.

4. Technical Insights and Tightness

• Tightness of the Threshold: The paper argues that the condition $p \gg n^{-1/2} \ln^{3/2} n$ for 2-point concentration is likely tight. The analysis of the term $k^3 p / n$ in the variance calculation suggests that if $p$ drops below this threshold, the variance of the counting variable becomes too large to guarantee concentration using the current "3-neighbor" restriction.
• Comparison to Independence Number: The results parallel recent findings on the independence number $\alpha(G_{n,p})$ by Bohman and the author, where similar techniques (counting "almost independent" sets) were required to push concentration results to lower $p$ values.

5. Significance and Future Directions

• Resolution of a Conjecture: The paper resolves the behavior of induced trees in the sparse regime, bridging the gap between constant $p$ and very sparse graphs.
• Methodological Advancement: It demonstrates the necessity of modifying the counting variable (from simple induced trees to trees with specific external neighbor constraints) to handle the "clustering" effects that arise in sparse random graphs.
• Future Work:
  • The author suggests that for $p$ slightly smaller than the proven threshold, one might need to count "clusters" (sets of vertices containing multiple induced trees) rather than single trees, similar to techniques used for the independence number.
  • The paper briefly touches on induced forests, noting that while the constant $p$ case is solvable via trees, the vanishing $p$ case is more complex due to the structure of the forest's remainder (resembling a cycle-free $G(1/p, p)$).

In summary, this paper provides a rigorous proof that the largest induced tree in $G_{n,p}$ is concentrated on two values for a wide range of sparse probabilities, while also identifying a critical lower bound below which this concentration breaks down, pushing the maximum size significantly below the expectation threshold.