Spectral Bounds for Antipodal Graphs

Samuel Korsky

arxiv: 2603.10334 · v2 · pith:MBT2ROXDnew · submitted 2026-03-11 · 🧮 math.CO · math.MG

Spectral Bounds for Antipodal Graphs

Samuel Korsky This is my paper

Pith reviewed 2026-05-21 12:32 UTC · model grok-4.3

classification 🧮 math.CO math.MG

keywords antipodal graphsspectral graph theorypoint setsdiameterdistance ratioscombinatorial geometryeigenvalue bounds

0 comments

The pith

Sets of points in the plane with diameter at most 1 have roughly the square root as many close pairs as nearly opposite pairs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that in any finite collection of points inside a disk of diameter 1, the count of ordered pairs at distance no more than ε stands in ratio at least ε to the power 1/2 plus a little o(1) to the count of ordered pairs at distance at least 1 minus ε. This improves an earlier lower bound of order ε to the 3/4 and reaches the conjectured optimal order up to a polylogarithmic factor. The argument proceeds by defining two auxiliary graphs on the same vertex set, one for small distances and one for large distances, then extracting the ratio from spectral information on their adjacency matrices. A reader interested in geometric combinatorics would care because the result forces a quantitative trade-off between local clustering and the existence of nearly diametral pairs.

Core claim

For any set of n points in R^2 with all pairwise distances at most 1, let N be the number of ordered pairs at distance ≤ ε and A the number at distance ≥ 1-ε. Then N/A ≳ ε^{1/2 + o(1)}. The same spectral technique yields an analogous statement in dimension d ≥ 3 with exponent min{d-3/2, 3(d-1)/4}.

What carries the argument

Spectral bounds on the adjacency matrices of the neighbor graph (pairs with distance ≤ ε) and the antipodal graph (pairs with distance ≥ 1-ε), which convert eigenvalue estimates into a lower bound on the ratio of their edge counts.

If this is right

The same method produces a dimension-dependent exponent in R^d for d ≥ 3.
The two-dimensional bound nearly matches the conjectured correct asymptotic.
The result holds uniformly for every finite point set obeying the diameter condition.
Spectral analysis of threshold graphs supplies a general tool for relating different distance scales.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The polylogarithmic slack might be removable by a more refined eigenvalue estimate.
Similar spectral comparisons could apply to point sets on the sphere or in other metrics.
The forced balance between close and far pairs may constrain sampling algorithms that try to avoid both clusters and outliers.

Load-bearing premise

The spectral properties of the two distance-threshold graphs on the point set directly control the neighbor-to-antipode edge-count ratio.

What would settle it

An explicit finite point set in the plane of diameter 1 for which the ratio of close pairs to antipodal pairs falls below ε^{0.4} for a sequence of ε tending to zero.

read the original abstract

Suppose $\left\{x_1, \dots, x_n\right\} \subset \mathbb{R}^2$ is a set of $n$ points in the plane with diameter $\leq 1$, meaning $|x_i - x_j| \leq 1$ for all $1 \leq i,j \leq n$. We show that the ratio of the number of ``neighbors'' (ordered pairs of points with distance $\leq \varepsilon$) to the number of ``antipodes'' (ordered pairs of points with distance $\geq 1 - \varepsilon$) is $\gtrsim\varepsilon^{1/2 + o(1)}$, attaining the conjectured correct asymptotic within a polylog factor and improving the $\gtrsim\varepsilon^{3/4+o(1)}$ bound of Steinerberger (2025). In dimensions $d\ge3$ we prove a similar result with exponent $\min\left\{d-3/2,\ 3(d - 1)/4\right\}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Korsky gets the exponent down to 1/2 + o(1) on the neighbor-to-antipode ratio using spectral bounds on the distance graphs, with a higher-d extension, but the step from operator norm to edge counts under irregular degrees is the part that needs verification.

read the letter

The main thing here is that Korsky improves the exponent on the ratio of close pairs to far pairs in a unit-diameter point set from the prior 3/4 + o(1) to 1/2 + o(1), and gives a higher-dimensional version with the min of d-3/2 and 3(d-1)/4. The approach builds neighbor and antipodal graphs directly from the Euclidean distances and applies spectral inequalities to them. That is the actual advance over Steinerberger, and it is new rather than a restatement. The construction looks clean and avoids obvious circularity or fitted quantities. The higher-d statement is also fresh. The paper does a reasonable job framing the problem in terms of extremal discrete geometry questions where such ratios matter for packing or rigidity bounds. The math is formally grounded in standard spectral graph theory tools applied to explicitly defined graphs. The soft spot is the one flagged in the stress test. When degrees in these induced graphs vary by polynomial factors in 1/ε, which is common in arbitrary point configurations, the conversion from the largest eigenvalue or operator norm to a lower bound on the edge ratio can lose sharpness. If the argument relies on average-degree estimates without controlling the spread or using a norm that is robust to irregularity, the claimed 1/2 might not survive. The abstract gives no proof sketch or error-term details, so it is impossible to see whether they handle this with a trace method, degree regularization, or something else. That is the load-bearing step for the improvement. This is the sort of paper that belongs in a reading group for people working on geometric extremal problems or spectral methods in combinatorics. A reader who already knows the Steinerberger bound and wants the next quantitative step would get value from it. It deserves a serious referee to check the spectral-to-combinatorial translation and confirm the exponent holds under the degree variation that actually occurs in the geometric setting.

Referee Report

2 major / 2 minor

Summary. The manuscript establishes spectral bounds on graphs induced by distance thresholds on finite point sets in Euclidean space. For n points in R^2 of diameter at most 1, it proves that the ratio of ordered pairs at distance ≤ε to ordered pairs at distance ≥1-ε is ≳ε^{1/2+o(1)}, improving the ε^{3/4+o(1)} bound of Steinerberger (2025). In dimensions d≥3 the exponent is min{d-3/2, 3(d-1)/4}. The argument proceeds by constructing neighbor graph G and antipodal graph H from the point set, applying spectral inequalities to their adjacency matrices, and converting the resulting eigenvalue bounds into the stated combinatorial ratio.

Significance. If the central derivation holds, the result supplies a near-optimal lower bound on the neighbor-to-antipode ratio that matches the conjectured asymptotic up to a polylog factor. The explicit use of spectral graph theory on geometrically defined graphs, together with the improvement over the prior 3/4 exponent, constitutes a clear advance in the area of geometric discrepancy and unit-distance problems. The higher-dimensional statement is also of independent interest.

major comments (2)

[§3.1] §3.1, the passage from ||A_H||_2 ≤ f(ε,d) to a lower bound on e(G)/e(H): the argument invokes the Rayleigh quotient or trace(A_H^2) to relate the spectral radius to the number of antipodal pairs. Because degrees in H can vary by a polynomial factor in 1/ε (as the point set is arbitrary), replacing average degree by maximum degree in the conversion step appears to degrade the exponent from 1/2 back toward 3/4. Please supply the precise inequality used and show that it preserves the claimed 1/2 + o(1) exponent under irregular degrees.
[§4.2] §4.2, Lemma 4.3: the o(1) term in the planar exponent is stated to arise from a logarithmic factor in the eigenvalue estimate for the distance graphs. The dependence on ε is not made fully explicit; if the hidden log(1/ε) factor is larger than any fixed power of ε, the improvement over the Steinerberger bound would be lost for sufficiently small ε. An explicit error-term calculation is needed.

minor comments (2)

[§2] The definition of ordered pairs (directed edges) versus unordered pairs should be stated once at the beginning of §2 to avoid ambiguity when counting e(G) and e(H).
[Theorem 1.2] In the higher-dimensional statement, the two competing exponents d-3/2 and 3(d-1)/4 cross at d=3; a short remark explaining why the minimum is taken would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable suggestions. The comments have helped us clarify key steps in the proof. We address each major comment below.

read point-by-point responses

Referee: [§3.1] §3.1, the passage from ||A_H||_2 ≤ f(ε,d) to a lower bound on e(G)/e(H): the argument invokes the Rayleigh quotient or trace(A_H^2) to relate the spectral radius to the number of antipodal pairs. Because degrees in H can vary by a polynomial factor in 1/ε (as the point set is arbitrary), replacing average degree by maximum degree in the conversion step appears to degrade the exponent from 1/2 back toward 3/4. Please supply the precise inequality used and show that it preserves the claimed 1/2 + o(1) exponent under irregular degrees.

Authors: In §3.1 we apply the Rayleigh quotient to the all-ones vector: for the adjacency matrix A_H of the antipodal graph, we have λ_max(A_H) ≥ (1^T A_H 1) / (1^T 1) = 2 e(H) / n . Since the spectral norm ||A_H||_2 equals λ_max (as A_H is symmetric and nonnegative), this yields e(H) ≤ (n/2) ||A_H||_2 ≤ (n/2) f(ε,d). An analogous bound holds for the neighbor graph G. The ratio e(G)/e(H) is then bounded below using these, without invoking the maximum degree. The use of the all-ones vector ensures that only the average degree appears, so the polynomial variation in individual degrees (which can indeed occur in arbitrary point sets) does not enter the estimate and the 1/2 + o(1) exponent is preserved. We have added this explicit inequality to the revised manuscript for clarity. revision: yes
Referee: [§4.2] §4.2, Lemma 4.3: the o(1) term in the planar exponent is stated to arise from a logarithmic factor in the eigenvalue estimate for the distance graphs. The dependence on ε is not made fully explicit; if the hidden log(1/ε) factor is larger than any fixed power of ε, the improvement over the Steinerberger bound would be lost for sufficiently small ε. An explicit error-term calculation is needed.

Authors: The logarithmic factor in Lemma 4.3 originates from the eigenvalue bound for the geometric graph, specifically from the discretization or covering argument used to estimate the operator norm, which introduces a factor of O(log(1/ε)). To make this explicit, we note that the bound on the ratio is at least C ε^{1/2} / log(1/ε)^k for some constant k and C>0. Since for any δ > 0, log(1/ε)^k = o(ε^{-δ}) as ε → 0, it follows that ε^{1/2} / log(1/ε)^k ≥ ε^{1/2 + δ} for all sufficiently small ε. Thus the bound is indeed ≳ ε^{1/2 + o(1)}, and the improvement over the ε^{3/4 + o(1)} bound is maintained. We have included the explicit error term calculation in the revised version of Lemma 4.3. revision: yes

Circularity Check

0 steps flagged

No circularity: spectral bounds applied to explicitly constructed distance graphs

full rationale

The derivation defines neighbor graph G (edges for dist ≤ ε) and antipodal graph H (edges for dist ≥ 1-ε) directly from the Euclidean point set. Standard spectral graph theory inequalities are then applied to bound the ratio of their edge counts. This translation uses external operator-norm or eigenvalue bounds on the adjacency matrices of these explicitly constructed graphs and does not reduce the claimed exponent to a fitted parameter, self-definition, or load-bearing self-citation. The result remains independent of the target asymptotic and improves on prior work via tighter analysis rather than re-labeling inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard Euclidean geometry and the applicability of spectral graph theory to the distance-threshold graphs; no free parameters or new entities are introduced in the abstract.

axioms (2)

standard math Euclidean distance satisfies the triangle inequality and is symmetric
Used to define diameter and the neighbor/antipode relations.
domain assumption Spectral bounds on adjacency or Laplacian matrices yield size estimates for the corresponding graphs
Central technique invoked to obtain the ratio lower bound.

pith-pipeline@v0.9.0 · 5689 in / 1356 out tokens · 66224 ms · 2026-05-21T12:32:10.592395+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We transform the problem into a statement about the d_i by employing the Collatz-Wielandt formula... λ1(M) ≤ max_i sqrt( sum_{j in N(i)} d_j )

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.