Optimal Spectral Bounds for Antipodal Graphs

This paper establishes that for a set of $n$ points in the plane with diameter at most 1, the ratio of pairs with distance $\leq \varepsilon$ to pairs with distance $\geq 1-\varepsilon$ is bounded below by $\varepsilon^{1/2+o(1)}$, thereby improving upon Steinerberger's previous $\varepsilon^{3/4+o(1)}$ bound and nearly confirming the conjectured asymptotic behavior.

The Gist

Here is an explanation of the paper "Optimal Spectral Bounds for Antipodal Graphs" using simple language and everyday analogies.

The Big Picture: The "Party" Problem

Imagine you are hosting a party in a room that is exactly 1 meter wide. You invite $n$ guests and tell them to stand anywhere in the room, but with one rule: No two guests can be more than 1 meter apart. (Since the room is only 1 meter wide, this is automatically true, but it sets the stage).

Now, you want to count two specific types of relationships between your guests:

1. The "Buddies" (Neighbors): Pairs of people standing very close together (within a tiny distance, say $\epsilon$).
2. The "Rivals" (Antipodes): Pairs of people standing as far apart as possible (almost 1 meter apart, within a tiny distance $\epsilon$ of the maximum).

The Question: If you have a huge number of "Rivals" (people standing on opposite sides of the room), does that force you to have a certain number of "Buddies" (people standing close together)?

The Previous Guess (Steinerberger's 2025 Result)

A mathematician named Steinerberger looked at this problem in 2025. He proved that if you have a lot of Rivals, you must have some Buddies.

However, his math was a bit "loose." He estimated that if you have $X$ Rivals, you have roughly $\sqrt[4]{\epsilon}$ times $X$ Buddies.

• Analogy: Imagine you have 1,000 Rivals. Steinerberger said, "Okay, you definitely have at least 50 Buddies."
• The Problem: He suspected the real answer was much higher (around 300 Buddies), but his math couldn't prove it yet. He was using a "sledgehammer" approach that wasted a lot of energy.

The New Discovery (Korsky's 2026 Result)

Samuel Korsky, the author of this paper, says: "I can do better."

He proves that the number of Buddies is actually proportional to $\sqrt{\epsilon}$ times the number of Rivals.

• The Upgrade: Using the same 1,000 Rivals example, Korsky proves you actually have around 300 Buddies.
• Why it matters: This is the "optimal" (best possible) answer, up to some very small, annoying math details (called "polylog factors"). It matches the best possible scenarios we can imagine.

How Did He Do It? (The Secret Sauce)

To understand Korsky's improvement, let's look at how he changed the math.

1. The Old Way: Counting Everyone (The "Headcount" Method)

Steinerberger tried to solve this by looking at the total sum of all connections in the room.

• Analogy: Imagine trying to find the tallest person in a crowd. Steinerberger's method was to add up the heights of everyone in the room and divide by the number of people.
• The Flaw: This is inefficient. If you have one giant (a very popular person with many Rivals) and a bunch of tiny people, the average gets skewed. The "total sum" is much bigger than the "tallest person." This made his estimate too weak.

2. The New Way: The "Local Leader" Method (Collatz-Wielandt)

Korsky used a smarter tool called the Collatz-Wielandt formula. Instead of looking at the whole crowd at once, he looked at specific groups and asked: "Who is the most connected person in this specific neighborhood?"

• Analogy: Instead of averaging everyone's height, Korsky went to every corner of the room and asked, "Who is the tallest person right here?" He then took the maximum of those local leaders.
• The Result: This bypasses the "wasted" math of the average and zooms in on the most extreme cases. It allows him to see the true relationship between Rivals and Buddies much more clearly.

The Geometry: The "Donut" Intersection

To make this work, Korsky had to solve a tricky geometry puzzle involving annuli (donut shapes).

• The Setup: Imagine two people standing far apart. Around each person, draw a "donut" representing the area where a third person could stand to be a "Rival" to both of them.
• The Puzzle: Where do these two donuts overlap?
• The Old Math: Steinerberger only looked at cases where the people were very far apart.
• The New Math: Korsky realized that even when people are moderately far apart, the overlap of these donuts is still very small and predictable. He calculated the exact shape of this overlap (a tiny, curved quadrilateral) and proved it fits into very few small boxes.

This precise calculation allowed him to tighten the math, proving that you can't have a huge number of Rivals without forcing a significant number of Buddies to appear.

The Takeaway

In simple terms:
If you arrange a group of people in a room so that many of them are standing on opposite sides (Rivals), geometry forces many of them to also be standing close together (Buddies).

• Steinerberger (2025): Said, "There are some Buddies." (A bit vague).
• Korsky (2026): Said, "There are exactly this many Buddies, and here is the precise math to prove it."

Korsky didn't just find a new number; he found a smarter way to count (using local leaders instead of global averages) and a sharper way to measure (using precise donut overlaps). This moves the field from "good enough" to "mathematically perfect."

Technical Summary

Here is a detailed technical summary of the paper "Optimal Spectral Bounds for Antipodal Graphs" by Samuel Korsky.

1. Problem Statement

The paper addresses a geometric extremal problem concerning sets of points in the Euclidean plane $\mathbb{R}^2$.

• Setup: Let $X = \{x_1, \dots, x_n\} \subset \mathbb{R}^2$ be a set of $n$ points with diameter $\le 1$ (i.e., $\|x_i - x_j\| \le 1$ for all $i, j$).
• Definitions: For a small parameter $\varepsilon > 0$:
  • $\varepsilon$-neighbors: Pairs $(x_i, x_j)$ such that $\|x_i - x_j\| \le \varepsilon$.
  • $\varepsilon$-antipodes: Pairs $(x_i, x_j)$ such that $\|x_i - x_j\| \ge 1 - \varepsilon$.
• Objective: Determine the optimal asymptotic lower bound on the ratio of the number of neighbors to the number of antipodes as $n \to \infty$ and $\varepsilon \to 0$.
• Context: Steinerberger (2025) previously established that the existence of many antipodes implies the existence of many neighbors, but his bound was suboptimal. Extremal examples (points on a circle or an arc with a center cluster) suggest the ratio should scale as $\sim \sqrt{\varepsilon}$.

2. Methodology

Korsky refines the spectral graph theory approach used by Steinerberger. The core strategy involves modeling the geometric constraints as a graph problem and optimizing the spectral bound.

A. Graph Formulation

1. Discretization: The boundary of the convex hull of the point set is partitioned into $k \sim \varepsilon^{-1}$ small boxes of size $\varepsilon/2$.
2. Antipodal Graph ($G$): A graph is constructed where vertices represent these boxes. An edge exists between box $B_i$ and $B_j$ if the maximum distance between any points in the two boxes is $\ge 1 - \varepsilon$.
3. Adjacency Matrix ($M$): The problem reduces to bounding the spectral radius (largest eigenvalue) $\lambda_1(M)$ of the adjacency matrix $M$. A bound of $\lambda_1(M) = O(\varepsilon^{-\alpha})$ implies a neighbor-to-antipode ratio of $\Omega(\varepsilon^{\alpha})$.

B. Spectral Refinement (The Core Innovation)

Steinerberger's proof relied on a global trace argument: $\lambda_1(M) \le \sqrt{\text{tr}(M^T M)} = \sqrt{2|E|}$. Korsky argues this is "wasteful" because the trace sums all eigenvalues, not just the largest one.

• New Approach: Korsky replaces the trace bound with the Collatz-Wielandt formula combined with the Cauchy-Schwarz inequality.
• Derivation:
  $$\lambda_1(M) \le \max_i \frac{(Mx)_i}{x_i}$$
  By choosing the test vector $x_i = \sqrt{d_i}$ (where $d_i$ is the degree of vertex $i$), the bound becomes:
  $$\lambda_1(M) \le \max_i \sqrt{\sum_{j \in N(i)} d_j}$$
  This shifts the problem from bounding the total number of edges to bounding the sum of degrees of neighbors for high-degree vertices.

C. Geometric Analysis (Annuli Intersections)

To bound $\sum_{j \in N(i)} d_j$, the paper analyzes the geometry of "common neighborhoods."

• Lemma 4.1 (Refined Annuli Intersection): The paper proves a precise bound on the intersection of two thin annuli (inner radius $1-\varepsilon$, outer radius$1$) with centers separated by distance$d$.
  • Result: The intersection consists of two regions coverable by $\lesssim 1/d$ boxes of size $\varepsilon/2 \times \varepsilon/2$.
  • Improvement: Previous work only utilized this for $d \gtrsim \sqrt{\varepsilon}$. Korsky extends the validity to the full domain $d \gtrsim \varepsilon$ by carefully analyzing the vertical thickness of the intersection quadrilateral.
• Application: This geometric bound allows the author to show that vertices with high degrees (representing points with many antipodes) must have neighbors with relatively low degrees on average.

3. Key Contributions

1. Optimal Asymptotic Bound: The paper improves the lower bound on the neighbor-to-antipode ratio from Steinerberger's $\varepsilon^{3/4}$ to the conjectured optimal $\varepsilon^{1/2}$ (up to polylogarithmic factors).
2. Spectral Technique Upgrade: It demonstrates that replacing global trace arguments with local Collatz-Wielandt bounds is a powerful method for refining spectral estimates in geometric graph problems.
3. Geometric Precision: It provides a more rigorous and extended analysis of annuli intersections, allowing for tighter control over the "common neighbor" counts in the graph formulation.

4. Main Results

Theorem 1.2: There exists a universal constant $c > 0$ such that for all $\varepsilon > 0$ and any set $\{x_1, \dots, x_n\} \subset \mathbb{R}^2$ with diameter $\le 1$:
$$\#\{1 \le i < j \le n : \|x_i - x_j\| \le \varepsilon\} \ge \frac{c \cdot \varepsilon^{1/2}}{(\log \varepsilon^{-1})^{1/2}} \cdot \#\{1 \le i < j \le n : \|x_i - x_j\| \ge 1 - \varepsilon\}$$

This confirms that the ratio of neighbors to antipodes scales as $\gtrsim \varepsilon^{1/2}$, matching the behavior observed in the extremal examples (points on a circle or arc).

5. Significance

• Resolution of Conjecture: The result settles the asymptotic scaling question raised by Steinerberger, confirming that $\sqrt{\varepsilon}$ is indeed the correct natural scaling factor.
• Methodological Impact: The transition from trace-based spectral bounds to degree-weighted Collatz-Wielandt bounds offers a new toolkit for researchers dealing with spectral properties of geometric graphs, particularly where global sums overestimate the dominant eigenvalue.
• Geometric Insight: The refined analysis of annuli intersections provides a more complete understanding of how "antipodal" constraints propagate through a point set in the plane, bridging the gap between discrete geometry and spectral graph theory.