Spectral radius and Hamiltonicity of uniform hypergraphs

George Brooks; Ruth Luo; William Linz

arxiv: 2504.18314 · v2 · submitted 2025-04-25 · 🧮 math.CO

Spectral radius and Hamiltonicity of uniform hypergraphs

George Brooks , William Linz , Ruth Luo This is my paper

Pith reviewed 2026-05-22 17:57 UTC · model grok-4.3

classification 🧮 math.CO

keywords spectral radiusHamiltonian Berge cycleuniform hypergraphsextremal combinatoricshypergraph Hamiltonicityadjacency tensor

0 comments

The pith

Any r-uniform hypergraph with spectral radius above binom(n-2, r-1) has a Hamiltonian Berge cycle unless it is the near-complete exception.

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

The authors prove that exceeding a certain spectral radius threshold in an r-uniform hypergraph forces the existence of a Hamiltonian Berge cycle. The threshold is the binomial coefficient binom(n-2, r-1), with the sole exception being the complete hypergraph on n-1 vertices plus one edge. This provides a generalization of a graph theory result and includes a parallel statement for when the number of edges is large enough.

Core claim

We prove that any r-uniform hypergraph H on n vertices with spectral radius λ(H) > binom(n-2, r-1) must contain a Hamiltonian Berge cycle unless H is the complete graph K_{n-1}^r with one additional edge. This generalizes a result proved by Fiedler and Nikiforov for graphs. As part of our proof, we show that if |H| > binom(n-1, r), then H contains a Hamiltonian Berge cycle unless H is the complete graph K_{n-1}^r with one additional edge, generalizing a classical theorem for graphs.

What carries the argument

Spectral radius of the adjacency tensor of the r-uniform hypergraph, which exceeds the value binom(n-2, r-1) to force the presence of a Hamiltonian Berge cycle.

If this is right

If the number of edges exceeds binom(n-1, r), the hypergraph contains a Hamiltonian Berge cycle unless it is the stated exception.
The spectral condition extends the Fiedler-Nikiforov theorem from graphs to uniform hypergraphs.
The edge-count condition extends a classical graph theorem to hypergraphs.

Where Pith is reading between the lines

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

The threshold could support computational checks for Hamiltonicity by calculating the spectral radius rather than searching for cycles directly.
Analogous spectral conditions might apply to other hypergraph properties such as perfect matchings or connectivity.
The uniqueness of the exception suggests the bound is tight and could guide further refinements in extremal hypergraph problems.

Load-bearing premise

The spectral radius defined via the adjacency tensor increases with added edges such that the stated extremal hypergraph is the unique maximizer without the cycle below the threshold.

What would settle it

Construct or exhibit an r-uniform hypergraph on n vertices that is not K_{n-1}^r plus one edge, has no Hamiltonian Berge cycle, yet has spectral radius strictly larger than binom(n-2, r-1).

read the original abstract

Let $n$ and $r$ be integers with $n-2\ge r\ge 3$. We prove that any $r$-uniform hypergraph $\mathcal{H}$ on $n$ vertices with spectral radius $\lambda(\mathcal{H}) > \binom{n-2}{r-1}$ must contain a Hamiltonian Berge cycle unless $\mathcal{H}$ is the complete graph $K_{n-1}^r$ with one additional edge. This generalizes a result proved by Fiedler and Nikiforov for graphs. As part of our proof, we show that if $|\mathcal{H}| > \binom{n-1}{r}$, then $\mathcal{H}$ contains a Hamiltonian Berge cycle unless $\mathcal{H}$ is the complete graph $K_{n-1}^r$ with one additional edge, generalizing a classical theorem for graphs.

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

A direct lift of the Fiedler-Nikiforov spectral condition to r-uniform hypergraphs for Berge Hamilton cycles, plus the matching edge-count version.

read the letter

The punchline is that this paper gives a clean spectral-radius threshold for Hamiltonian Berge cycles in r-uniform hypergraphs and proves the parallel statement using only edge count. Both results identify the same exceptional example: the complete r-uniform hypergraph on n-1 vertices plus one extra edge. The range is n-2 ≥ r ≥ 3, which keeps the statements away from trivial small cases. This is a straightforward generalization of the graph theorem by Fiedler and Nikiforov, and the hypergraph statements do not appear in the cited graph literature. The edge-count version is also new in the hypergraph setting. The statements are precise, the exceptions are explicit, and the approach appears to adapt existing graph arguments to the adjacency tensor without introducing new parameters or circular definitions. That is the main value: it organizes a known graph fact inside extremal hypergraph theory in a usable way. The soft spot is the step that links the spectral radius bound to the edge threshold. The argument needs to establish that binom(n-2, r-1) is the maximum spectral radius achievable with at most binom(n-1, r) edges and that it is achieved only by the stated exception. This requires showing that the spectral radius is non-decreasing under edge addition and that the increase is strict except in controlled cases, along with uniqueness of the maximizer. The stress-test note correctly flags that these properties depend on details of the Perron vector and connectivity assumptions for the tensor. If the full proof supplies those details without gaps, the central claim holds; otherwise the spectral version rests on an unverified lifting. No other load-bearing issues are visible from the abstract. This paper is for people working in spectral extremal combinatorics who already know the graph case and want the hypergraph extension. A reader comfortable with tensor eigenvalues and Berge cycles will extract the most from it. It is a bounded but honest advance rather than a reorganization of the field. I would send it to peer review so the technical steps can be checked in detail.

Referee Report

2 major / 2 minor

Summary. The paper proves that for integers n and r with n-2 ≥ r ≥ 3, any r-uniform hypergraph H on n vertices satisfying λ(H) > binom(n-2, r-1) contains a Hamiltonian Berge cycle unless H is exactly K_{n-1}^r with one additional edge. As an auxiliary result used in the proof, it also shows that the same conclusion holds whenever the number of edges exceeds binom(n-1, r). Both statements generalize the corresponding theorems of Fiedler and Nikiforov from the graph case (r=2).

Significance. If the technical details hold, the results supply a clean spectral sufficient condition for Hamiltonicity in uniform hypergraphs together with an explicit extremal example, extending classical graph-theoretic work into the hypergraph setting and linking spectral radius techniques with Berge-cycle problems in extremal combinatorics.

major comments (2)

[Proof of the spectral-radius statement (likely §4)] The central reduction from the spectral-radius hypothesis to the edge-count hypothesis (used to invoke the auxiliary theorem) requires proving that binom(n-2, r-1) is the maximum possible spectral radius among all r-uniform hypergraphs with at most binom(n-1, r) edges and that this maximum is achieved uniquely by K_{n-1}^r. The manuscript invokes monotonicity of λ under edge addition for the adjacency tensor, but does not supply a self-contained argument ruling out equality or larger values for other (possibly disconnected) hypergraphs with the same number of edges; this step is load-bearing for both main theorems.
[Extremal spectral-radius lemma preceding the main theorems] The uniqueness claim for the maximizer K_{n-1}^r and the strict increase of λ upon adding an edge to it rest on properties of the Perron vector of the adjacency tensor. No explicit verification is given that the vector remains positive or that the Rayleigh quotient strictly increases in the exceptional case; without this, the strict inequality λ(H) > binom(n-2, r-1) may not force |E(H)| > binom(n-1, r) as asserted.

minor comments (2)

[§2] The definition of the adjacency tensor and the precise normalization used for the spectral radius should be restated in the preliminaries so that the comparison λ(H) > binom(n-2, r-1) is immediately interpretable without consulting external references.
[Introduction] A short remark clarifying how the Berge-cycle notion reduces to the ordinary Hamilton cycle when r=2 would help readers see the exact scope of the generalization.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable feedback on our paper. The comments point to areas where the proof can be clarified and strengthened. We address each major comment below and will make the necessary revisions to the manuscript.

read point-by-point responses

Referee: The central reduction from the spectral-radius hypothesis to the edge-count hypothesis (used to invoke the auxiliary theorem) requires proving that binom(n-2, r-1) is the maximum possible spectral radius among all r-uniform hypergraphs with at most binom(n-1, r) edges and that this maximum is achieved uniquely by K_{n-1}^r. The manuscript invokes monotonicity of λ under edge addition for the adjacency tensor, but does not supply a self-contained argument ruling out equality or larger values for other (possibly disconnected) hypergraphs with the same number of edges; this step is load-bearing for both main theorems.

Authors: We appreciate the referee's observation regarding the need for a more explicit justification in the reduction step. While the monotonicity property of the spectral radius with respect to edge addition is known for hypergraph adjacency tensors, we acknowledge that a self-contained argument is desirable. In the revised version of the manuscript, we will insert a new lemma that proves λ(H) ≤ binom(n-2, r-1) for any r-uniform hypergraph H with |E(H)| ≤ binom(n-1, r), with equality holding if and only if H is isomorphic to K_{n-1}^r. This will include arguments showing that any other hypergraph, connected or disconnected, cannot exceed this bound, thereby supporting the strict inequality in the main theorems. revision: yes
Referee: The uniqueness claim for the maximizer K_{n-1}^r and the strict increase of λ upon adding an edge to it rest on properties of the Perron vector of the adjacency tensor. No explicit verification is given that the vector remains positive or that the Rayleigh quotient strictly increases in the exceptional case; without this, the strict inequality λ(H) > binom(n-2, r-1) may not force |E(H)| > binom(n-1, r) as asserted.

Authors: We agree that the details concerning the Perron vector and the strict monotonicity should be verified explicitly in the text. In the revision, we will expand the extremal spectral-radius lemma to include a direct argument showing that the Perron vector of K_{n-1}^r can be chosen with all positive entries on the n-1 vertices, and that adding any edge to this hypergraph results in a strict increase in the Rayleigh quotient. This will rigorously establish that λ(H) > binom(n-2, r-1) implies |E(H)| > binom(n-1, r). revision: yes

Circularity Check

0 steps flagged

Direct combinatorial proof against external spectral threshold with no self-referential reduction

full rationale

The paper derives the Hamiltonicity threshold by direct comparison of λ(H) to the fixed binomial coefficient binom(n-2,r-1), which is the spectral radius of the extremal complete hypergraph K_{n-1}^r. This comparison is external to the paper's own constructions and generalizes the Fiedler-Nikiforov graph result without fitting parameters or renaming known patterns. The uniqueness of the exception case K_{n-1}^r plus one edge is established inside the proof via edge-addition monotonicity of the adjacency tensor, rather than imported via self-citation. No step reduces by construction to its own inputs; the argument remains self-contained against standard tensor definitions and classical extremal combinatorics.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard definition of the adjacency tensor and its spectral radius for uniform hypergraphs, plus the combinatorial definition of a Berge cycle; no new free parameters or invented entities are introduced.

axioms (2)

standard math The spectral radius of an r-uniform hypergraph is defined via the largest eigenvalue of its adjacency tensor.
Invoked when comparing λ(H) to binom(n-2, r-1).
domain assumption A Berge cycle is a sequence of distinct vertices and edges where each consecutive pair is contained in the corresponding edge.
Used in the statement of the Hamiltonian property.

pith-pipeline@v0.9.0 · 5667 in / 1334 out tokens · 34501 ms · 2026-05-22T17:57:06.043927+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/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

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

λ(H) = max_{||x||_r=1} P_H(x) where P_H(x) = r ∑_{e∈E} ∏ x_i; Bai-Lu: λ(H) ≤ f_r(m) with equality only for complete + isolates

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.