An Improved Interpolation Theorem and Disproofs of Two Conjectures on 2-Connected Subgraphs

Imagine you have a giant, complex city made of buildings (vertices) connected by roads (edges). In the world of mathematics, this is called a graph.

The paper you're asking about is like a detective story where mathematicians are trying to solve a puzzle about the "shape" of these cities. Specifically, they are looking for 2-connected subgraphs.

The Big Picture: What is a "2-Connected" City?

Think of a "2-connected" graph as a city that is robust. If you remove any single building (and all its roads), the rest of the city stays connected. You can still get from any point to any other point without getting stuck. It's a city with no "single points of failure."

The authors are investigating a property called Interpolation.

The Analogy: Imagine you have a city with 100 buildings. You know you can find a robust, self-contained neighborhood of 4 buildings. You also know you can find a massive robust neighborhood of 100 buildings (the whole city).
The Question: Does this city necessarily contain robust neighborhoods of size 5, 6, 7, 8... all the way up to 99? Or are there "gaps" where no such neighborhood exists?

The authors call this the Interpolation Property. They want to know: If a city is big enough and has enough roads, does it have robust neighborhoods of every possible size?

The Previous Rules (The "Old Map")

Before this paper, mathematicians Yin and Wu had drawn a map with two rules to guarantee these neighborhoods exist:

Rule A (Based on Total Roads): If the city has a huge number of roads (specifically, more than half the square root of the number of buildings cubed), it should have neighborhoods of all sizes.
Rule B (Based on Minimum Connections): If every building in the city connects to at least $\sqrt{n}$ (the square root of the total buildings) other buildings, it should have neighborhoods of all sizes.

They also had a third rule (Theorem 1.4) that said: "If every building connects to at least $n/3$ other buildings, you are safe."

The New Discovery: The "Improved Map"

The authors of this paper, Liu and Ning, said, "We can do better than $n/3$ ."

The New Rule (Theorem 1.5):
They proved that you don't need buildings to be connected to $n/3$ of the city. You only need them to be connected to $n/4 + 2$ of the city.

Simple Translation: If every building has at least 25% of the city's buildings as neighbors (plus a tiny bit of extra safety), you are guaranteed to find robust neighborhoods of every size from 4 up to the whole city.
Why it matters: This lowers the bar. It means even "sparser" cities (with fewer roads) still have this perfect "continuity" of neighborhood sizes.

The Disproofs: "The Map Was Wrong!"

The authors didn't just improve the rules; they also proved that Yin and Wu's other two rules were completely wrong.

1. Disproving Rule A (The Road Count)

They built a "fake city" (a counterexample) that has a massive number of roads—way more than the rule required.

The Trap: This city is huge and has tons of roads, but it has a "gap." It has robust neighborhoods of size 4, 5, 6... up to a certain point, and then it jumps straight to the size of the whole city. It is missing the middle sizes.
The Metaphor: Imagine a library that has millions of books (roads). You'd think you could find a collection of books of any size. But this library is organized in a weird way: it has small stacks of 4 books, then a giant shelf of 1,000 books, but absolutely nothing in between. The rule that "lots of roads = all sizes" is false.

2. Disproving Rule B (The Square Root Connection)

They also attacked the rule about the square root of the city size ( $\sqrt{n}$ ).

The Trap: They used special mathematical structures called SBIBDs (Symmetric Balanced Incomplete Block Designs). Think of these as perfectly balanced, intricate patterns (like a Sudoku puzzle or a specific type of tile pattern).
The Result: They found specific city sizes (like 8, 14, 22, etc.) where every building connects to enough neighbors to satisfy the $\sqrt{n}$ rule, yet the city still has "gaps" in its neighborhood sizes.
The Metaphor: It's like a dance floor where everyone is holding hands with enough people to satisfy the rule, but the way they are holding hands creates a pattern where you can't form a circle of 5 people, even though you can form a circle of 4 or 6.

The Final Guess (The New Conjecture)

Since they couldn't prove the rule works for every possible city size using the $\sqrt{n}$ rule, they proposed a new, slightly weaker idea:

Conjecture 3:
"If every building connects to at least $n/k$ neighbors (where $k$ is some number like 3, 4, or 5), then for very large cities, you will eventually find neighborhoods of every size."

The Nuance: They suspect that for small cities, weird patterns (like the ones they found) might still create gaps. But if the city gets huge (sufficiently large), the math smooths out, and the gaps disappear.

Summary in a Nutshell

The Goal: Prove that if a network is strong enough, it contains "strong sub-networks" of every possible size.
The Win: They proved you only need 25% connectivity ( $n/4$ ) to guarantee this, which is a big improvement over the old 33% ( $n/3$ ) rule.
The Bust: They proved that having "lots of roads" or "square-root connectivity" is not enough to guarantee this; they built specific examples where these rules fail.
The Future: They believe that for massive networks, a slightly lower connectivity threshold ( $n/k$ ) will eventually work, but they need more time to prove it for all cases.

It's a story of refining our understanding of how "connected" a network needs to be to ensure it's perfectly flexible and complete.

Here is a detailed technical summary of the paper "An Improved Interpolation Theorem and Disproofs of Two Conjectures on 2-Connected Subgraphs" by Haiyang Liu and Bo Ning.

1. Problem Statement

The paper addresses the interpolation property within the family of 2-connected subgraphs of a graph. A graph invariant possesses the interpolation property if, whenever a family of subgraphs contains members with invariant values $m$ and $n$ ( $m < n$ ), it also contains a member with value $k$ for every integer $k$ between $m$ and $n$ .

Specifically, the authors investigate whether a 2-connected graph $G$ of order $n$ with a specific minimum degree condition $\delta(G)$ contains a 2-connected subgraph of every order $k$ for $4 \le k \le n$.

The paper focuses on three main objectives:

Disproving Conjecture 1: Proposed by Yin and Wu, stating that if the number of edges $m \ge \frac{1}{2}n^{3/2}$ , the interpolation property holds.
Disproving Conjecture 2: Proposed by Yin and Wu, stating that if the minimum degree $\delta(G) \ge \sqrt{n}$ , the interpolation property holds.
Improving Theorem 1.4: Yin and Wu previously proved the property holds if $\delta(G) \ge \lfloor n/3 \rfloor + 1$ . The authors aim to lower this bound.

2. Methodology

The authors employ a combination of constructive counterexamples and inductive structural proofs.

Counterexample Construction:
- For Conjecture 1: They construct a graph $G_\epsilon$ by combining a large complete graph $K_{\lfloor n^{1-\epsilon} \rfloor}$ and a path $P_{n-\lfloor n^{1-\epsilon} \rfloor}$ , connected by two disjoint edges. They analyze the edge count to show it satisfies the conjecture's condition while demonstrating a "gap" in the sizes of 2-connected subgraphs.
- For Conjecture 2: They utilize Symmetric Balanced Incomplete Block Designs (SBIBDs), specifically $(v, k, 2)$ -SBIBDs. They construct bipartite incident graphs from these designs. Since bipartite graphs contain no odd cycles (specifically no $C_5$ ) and have restricted common neighbor structures, they serve as counterexamples for specific values of $n$ . They also use the hypercube $Q_3$ for small $n$ .
- Sharpness Examples: They construct a graph $H$ based on a chain of complete bipartite graphs $K_{s,s}$ connected by a cycle of edges to demonstrate that the proposed new bound is tight for small $n$ .
Proof Techniques:
- Induction: The proof of the main theorem uses induction on the order $k$ of the desired 2-connected subgraph.
- Case Analysis: The proof is divided into cases based on the size of the target subgraph $k$ relative to $n$ (e.g., small $k$ , medium $k$ , large $k$ ).
- Degree Sum Arguments: They utilize Reiman's theorem (regarding $C_4$ existence) and degree sum inequalities to force the existence of specific substructures.
- Critical Connectivity: They apply results regarding critically 2-connected graphs (graphs where removing any vertex reduces connectivity) to handle cases where standard extension fails.

3. Key Contributions and Results

A. Disproof of Conjecture 1 (Edge Count)

The authors prove that the condition $m \ge \frac{1}{2}n^{3/2}$ is insufficient.

Result: For any $\epsilon < 1/4$ , the constructed graph $G_\epsilon$ has size $m > \frac{1}{2}n^{3/2}$ for sufficiently large $n$ .
Gap: $G_\epsilon$ contains 2-connected subgraphs of orders in $\{3, \dots, \lfloor n^{1-\epsilon} \rfloor\}$ and $\{n - \lfloor n^{1-\epsilon} \rfloor + 2, \dots, n\}$ .
Conclusion: There is a large gap of missing orders in the middle (specifically between $\lfloor n^{1-\epsilon} \rfloor + 1$ and $n - \lfloor n^{1-\epsilon} \rfloor + 1$ ), disproving the conjecture.

B. Disproof of Conjecture 2 (Minimum Degree $\sqrt{n}$ )

The authors disprove the conjecture that $\delta(G) \ge \sqrt{n}$ guarantees the interpolation property.

Result: Using $(v, k, 2)$ -SBIBDs, they construct counterexamples for $n \in \{14, 22, 32, 74, 112, 158\}$ .
Mechanism: The incident graphs of these designs are bipartite (no $C_5$ ) and lack $K_{2,3}$ subgraphs. Since a 2-connected subgraph of order 5 must contain either a $C_5$ or a $K_{2,3}$ , these graphs fail to have a 2-connected subgraph of order 5, despite satisfying $\delta(G) \ge \sqrt{n}$ .
Small Case: For $n=8$ , the hypercube $Q_3$ serves as a counterexample ( $\delta(Q_3)=3 > \sqrt{8}$ , but no 2-connected subgraph of order 5 exists).

C. Improved Interpolation Theorem (The Main Theorem)

The authors improve the minimum degree bound established by Yin and Wu.

Theorem 1.5: Let $G$ be a 2-connected graph of order $n \ge 4$ . If $\delta(G) \ge \lfloor n/4 \rfloor + 2$ , then $G$ contains a 2-connected subgraph of order $k$ for every $k \in \{4, \dots, n\}$ .
Improvement: This lowers the required degree from $\approx n/3$ to $\approx n/4$ .
Sharpness: The authors show via examples (like the Hanoi graph $H^2_3$ and the constructed graph $H$ ) that the bound is sharp for small $n$ and cannot be easily lowered to $\delta(G) \ge n/k$ for arbitrary $k$ without further constraints.

D. New Conjecture

Based on the difficulty of disproving Conjecture 2 for all $n$ (due to the finiteness of known SBIBDs), the authors propose a weaker, asymptotic conjecture:

Conjecture 3: For any integer $k \ge 3$ , there exists a threshold $n_0 = f(k)$ such that if $G$ is a 2-connected graph of order $n \ge n_0$ with $\delta(G) \ge n/k$ , then $G$ contains 2-connected subgraphs of all orders from 4 to $n$ .

4. Significance

Refinement of Structural Graph Theory: The paper significantly tightens the known sufficient conditions for the existence of 2-connected subgraphs of all orders, moving the threshold from $n/3$ to $n/4$ .
Resolution of Open Problems: It definitively settles two open conjectures by Yin and Wu, showing that neither edge density ( $n^{3/2}$ ) nor a square-root degree condition ( $\sqrt{n}$ ) is sufficient to guarantee the interpolation property.
Interdisciplinary Application: The disproof of Conjecture 2 elegantly bridges graph theory with combinatorial design theory (SBIBDs), demonstrating how algebraic structures can generate specific graph-theoretic counterexamples.
Future Direction: The paper shifts the focus from global conditions to asymptotic behavior, suggesting that while $\delta(G) \ge n/k$ might fail for small $n$ , it likely holds for sufficiently large $n$ , opening a new avenue for research in interpolation properties.