Hoffman's bound for hypergraphs

V. Nikiforov

Hoffman's bound for hypergraphs

T0 review · 0 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Hoffman's eigenvalue bound for graph colorings carries over to weighted even-rank hypergraphs: for every weighted $k$-partite $r$-graph with even $r$ and $p \ge r$, the spectral ratio $\lambda^{(p)}/\lambda^{(p)}_{\min}$ is at least the…

desk verdict A clean, correct generalization of Hoffman's bound to weighted even-uniform hypergraphs; the p≥r caveat is real but honestly flagged, and the proof holds up. read the letter →

arxiv 1908.01433 v1 pith:PA5FMMCK submitted 2019-08-05 math.CO

V. Nikiforov This is my paper · ORCID

classification math.CO MSC 15A4205C65

keywords Hoffman'sboundhypergrapheigenvaluesk-partitehypergraphsweightedℓ^p-spectralradiuschromaticnumbercompleter-graphspolynomialform

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Hoffman's inequality for graphs says the chromatic number satisfies $\chi(G) \ge 1 - \lambda(G)/\lambda_{\min}(G)$, tying colorability to the two extreme adjacency eigenvalues. This note proves the analogous statement for weighted $r$-uniform hypergraphs with even $r$: if $G^w$ is $k$-partite (vertices split into $k$ classes, every edge meeting each class at most once), then for every $p \ge r$, $\lambda^{(p)}(G^w)/\lambda^{(p)}_{\min}(G^w) \ge \lambda^{(p)}(K^k_r)/\lambda^{(p)}_{\min}(K^k_r)$, where the two quantities are the maximum and minimum of the hypergraph's polynomial form on the unit $\ell^p$ sphere, and $K^k_r$ is the complete $k$-partite $r$-graph; regular complete $k$-partite $r$-graphs attain equality. Setting $r = p = 2$ with unit weights recovers Hoffman's inequality exactly. The result matters because the bound is sharp on a natural class and because the paper shows the hypothesis $k$-partite cannot be relaxed to $k$-chromatic: explicit 2-chromatic 4-graphs have spectral ratio growing without bound.

What carries the argument

The load-bearing object is the polynomial form $P_{G^w}(x) = r! \sum_{\{i_1,\dots,i_r\} \in E(G)} w_{i_1\dots i_r} x_{i_1}\cdots x_{i_r}$ on $\mathbb{R}^n$, whose extrema on the unit $\ell^p$ sphere define $\lambda^{(p)}(G^w)$ and $\lambda^{(p)}_{\min}(G^w)$. The proof's engine is a permutation collapse: write $\eta(i)$ for the part of vertex $i$, let $x$ maximize $P_{G^w}$ and $y$ minimize the complete $k$-partite form, and form $z_{\sigma,i} = x_i y_{\sigma(\eta(i))}$ for every permutation $\sigma$ of the $k$ parts; summing the pointwise bound $P_{G^w}(z_\sigma) \ge \lambda^{(p)}_{\min}(G^w)|z_\sigma|_p^r$ over all $k!$ permutations turns the cross terms into $(k-r)!\,\lambda^{(p)}_{\min}(K^k_r)\,\lambda^{(p)}(G^w)$. The Power Mean inequality — which needs $r/p \le 1$, hence $p \ge r$ — then caps the accumulated $\ell^p$ sums at $k^{1-r/p}(k-1)!$, and Maclaurin's inequality yields $\lambda^{(p)}(K^k_r) = k^{1-r/p}(k-1)\cdots(k-r+1)$; assembling these pieces gives the ratio bound.

What would settle it

Take the complete 4-partite 4-graph on five singleton parts (five edges, one per 4-subset of parts), change one edge weight from 1 to 2, and compute both sides of inequality (3) at $p = 2$ by numerically optimizing the polynomial form $P_{G^w}$ on the $\ell^2$ unit sphere. If the perturbed ratio comes out strictly smaller than the complete ratio (larger in magnitude), the claimed bound fails below the $p \ge r$ threshold and Problem 4 is answered negatively; if it holds for every single-edge perturbation, the restriction is likely technical, and the same test at $p = 4$ would confirm the theorem on its proven range.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1: for even $r \ge 2$, integers $k \ge r$, real $p \ge r$, and any weighted $k$-partite $r$-graph $G^w$, the ratio inequality $\lambda^{(p)}(G^w)/\lambda^{(p)}_{\min}(G^w) \ge \lambda^{(p)}(K^k_r)/\lambda^{(p)}_{\min}(K^k_r)$ holds, with equality for regular complete $k$-partite $r$-graphs. Since $\lambda^{(p)}_{\min}$ is negative, the inequality bounds the magnitude of the extreme-eigenvalue ratio from above by the complete $k$-partite value; for ordinary graphs at $r = p = 2$ it reads $1 - \lambda/\lambda_{\min} \le k$, which with $k = \chi(G)$ is Hoffman's inequality. The weighted form also extends a matrix inequality of Lovász. The proof pins down half of the sharp constant, $\lambda^{(p)}(K^k_r) = k^{1-r/p}(k-1)\cdots(k-r+1)$, while the corresponding minimum $\lambda^{(p)}_{\min}(K^k_r)$ remains an explicitly identified unknown whose order of magnitude is announced for a sequel.

Load-bearing premise

The load-bearing premise is that $p \ge r$ and $r$ is even: the Power Mean step in equation (6) needs $r/p \le 1$ to point the right way, the case $1 \le p < r$ is left open as Problem 4, and for odd $r$ the statement holds only in the trivial sense that $\lambda^{(p)}_{\min}(G) = -\lambda^{(p)}(G)$.

Editorial extensions

If this is right

At $r = p = 2$ with unit weights the theorem is Hoffman's inequality: it gives $1 - \lambda(G)/\lambda_{\min}(G) \le k$ for every $k$-partite graph, and taking $k = \chi(G)$ returns $\chi(G) \ge 1 - \lambda(G)/\lambda_{\min}(G)$; allowing edge weights extends a matrix version of the bound due to Lovász.
For any weighted $k$-partite $r$-graph with even $r$ and $p \ge r$, the magnitude of the spectral ratio is at most the complete $k$-partite value, $|\lambda^{(p)}(G^w)/\lambda^{(p)}_{\min}(G^w)| \le \lambda^{(p)}(K^k_r)/|\lambda^{(p)}_{\min}(K^k_r)|$, and regular complete $k$-partite $r$-graphs attain equality, so that value is the sharp constant.
The hypothesis 'k-partite' is essential: the 4-graphs on $2n$ vertices whose edges are the 4-sets containing exactly two vertices from each of two equal classes are 2-chromatic yet satisfy $\lambda^{(p)}(G)/|\lambda^{(p)}_{\min}(G)| = \Omega(n)$, so no function of the chromatic number alone can bound the spectral ratio for $r \ge 4$.
For odd $r$ the theorem holds only trivially, since $\lambda^{(p)}_{\min}(G) = -\lambda^{(p)}(G)$ forces the ratio to be $-1$; the paper's open problems ask for a meaningful odd-$r$ extension and for the even-$r$ regime $1 \le p < r$.
The proof fixes the numerator of the sharp constant, $\lambda^{(p)}(K^k_r) = k^{1-r/p}(k-1)\cdots(k-r+1)$, while the denominator $\lambda^{(p)}_{\min}(K^k_r)$ remains an identified unknown whose order of magnitude the paper announces for a forthcoming paper.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A decisive test of the $p \ge r$ restriction is the unweighted complete $k$-partite $r$-graph itself: since the paper gives $\lambda^{(p)}(K^k_r)$ exactly but leaves $\lambda^{(p)}_{\min}(K^k_r)$ open, computing that minimum for $1 \le p < r$ would likely settle Problem 4 and reveal whether the reversed Power-Mean direction is a real obstruction or a proof artifact.
Read against the graph case, the 2-chromatic example marks a genuine graph/hypergraph divide: bipartite graphs have perfectly symmetric spectra (ratio exactly $-1$), whereas 2-chromatic 4-graphs can have unbounded ratio — so for $r \ge 4$ the structural parameter that spectral methods see is k-partiteness, not k-colorability.
A quantitative stability statement suggests itself: for graphs, Hoffman-type bounds are tight on many graphs, and the paper's equality case suggests that weighted $k$-partite $r$-graphs whose ratio comes close to the complete $k$-partite value should be close to a regular complete $k$-partite $r$-graph in structure (balanced parts, nearly constant weights) — a near-equality version of the paper's

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

I read this short note with some care, and I think the reader's report is about right. The central result—Theorem 1—generalizes Hoffman's bound to weighted even-uniform r-graphs, and the proof is genuinely clean. The averaging argument is a nice extension of the author's earlier eigenvector method, and the weighted setting plus the equality case for regular complete k-partite r-graphs are real additions. The infinite family of 2-chromatic 4-graphs in Section 2 is a good counterexample: it shows the k-partite hypothesis cannot simply be replaced by k-chromatic, because the ratio λ/|λ_min| grows unboundedly. I checked the main steps of the proof, and they hold. The Power Mean inequality is used in the right direction exactly because p≥r, and the sign bookkeeping works because both λ_min values are negative. The omitted proof of equation (10) is not a problem—it is genuinely the same lines as (9), and the statement is true.

The soft spots are minor and mostly cosmetic. The permutation set P is misprinted as [r]→[r] when it is used as permutations of [k]; the subsequent counting (k!, (k-r)!, the sum over σ) makes the intended set clear, so this is harmless. Proposition 2 writes λ_min = Ω(n^{3-4/p}) for a negative quantity, which is informal—really one should say |λ_min| = Ω(...) or use the sign explicitly. The dangling 'Proposition ??' is a typographical artifact. The one substantive caveat is that the right side of (3) depends on λ_min(p)(K^k_r), which is not known exactly, although the author says a forthcoming paper will determine its order of magnitude. That limits immediate numerical applications, but it doesn't affect the validity of the theorem.

The p

Who this is for: anyone working on spectral hypergraph theory or spectral bounds for chromatic/partition properties. It is not a big paper, but it is a solid, correct extension of a classical result. I would send it to a referee rather than desk-reject it; with minor revisions (fix the typo, include or spell out (10), fix the Ω notation) it should be publishable as is.

Referee Report

0 major / 6 minor

Summary. The paper extends Hoffman's classical chromatic-number eigenvalue bound to weighted uniform r-graphs. For an even integer r, real p ≥ r, integer k ≥ r, and a weighted k-partite r-graph G^w, Theorem 1 asserts that λ^{(p)}(G^w)/λ_min^{(p)}(G^w) ≥ λ^{(p)}(K^k_r)/λ_min^{(p)}(K^k_r), with equality for regular complete k-partite r-graphs. The proof averages the polynomial form P_G over the k! permutations of the partite classes and combines the Power Mean inequality with Maclaurin's inequality; the sign handling uses that λ_min is negative for even r. Section 2 constructs a family of 2-chromatic 4-graphs for which λ^{(p)}/|λ_min^{(p)}| grows linearly in the order, showing that replacing 'k-partite' by 'k-chromatic' is impossible. Two open problems are posed: meaningful extensions for odd r and for 1 ≤ p < r.

Significance. The main result is a genuine and natural generalization of Hoffman's bound to hypergraphs, obtained by a short and transparent argument that relies only on standard inequalities. The paper is careful to state the range of p and to flag the unknown value of λ_min(K^k_r); the counterexample in Section 2 is a useful negative result. The proof of the inequality is essentially complete, and the equality claim is supported except for a routine omitted calculation. These strengths make the paper a solid contribution to spectral hypergraph theory, suitable for a combinatorics or linear-algebra journal.

minor comments (6)

[Proof of Theorem 1, definition of P] In the proof of Theorem 1, P is defined as the set of all permutations σ:[r]→[r]; however, the subsequent counting of permutations, such as the r!(k-r)! permutations mapping {η(i1),...,η(ir)} onto {j1,...,jr}, is only valid for permutations of [k]. Please correct the definition to σ:[k]→[k] (or equivalently state the intended set explicitly), since as written the proof is not internally consistent.
[Proof of Theorem 1, equation (10)] The proof of equation (10) is omitted with the note that it 'goes along the same lines.' Since equality in (3) for complete regular k-partite r-graphs is part of the theorem statement, please include the argument or at least give the explicit analogue of the argument for λ_min, indicating that the same choice of x and the same two-sided bounding prove the equality for λ^{(p)} as well.
[Proposition 2, equation (13)] The statement λ_min^{(p)}(G) = Ω(n^{3-4/p}) is not meaningful as written because λ_min^{(p)}(G) is negative, while the Ω-notation normally refers to positive quantities. The intended statement is |λ_min^{(p)}(G)| = Ω(n^{3-4/p}) (or λ_min^{(p)}(G) = -Ω(n^{3-4/p})). Please correct this statement and the analogous line in the proof.
[Introduction, Rayleigh-Ritz citation] The citation 'the Rayleigh-Ritz theorem (see [3], Theorem 4.2.4)' appears to be a misreference; reference [3] is Hoffman's 1970 paper, whereas the Rayleigh-Ritz theorem is in [4] (Horn and Johnson, Matrix Analysis). Please correct the citation.
[Various locations, notation] The superscript (p) is used inconsistently: for example, equation (8) writes λ(K^k_r) without the superscript, and the paragraph after Theorem 1 refers to λ(K^k_r) without clarifying that the p-dependent eigenvalue is meant. Please standardize the notation to avoid confusion.
[Proof of Proposition 2] In the proof of Proposition 2, strict inequalities are used where weak inequalities would be more precise, e.g., '2S2(A) > ...' and '2S2(B) < ...'. Since the preceding estimates are derived from Maclaurin's and Power Mean inequalities, which are non-strict, please replace the strict signs with ≥ and ≤ as appropriate.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1 is proved from standard inequalities and independent prior definitions.

full rationale

The derivation chain is self-contained. Theorem 1 is proved by an explicit averaging argument: choose x maximizing P_Gw, choose y minimizing P_K^k_r, form z_sigma, apply the elementary inequality P_Gw(x) >= lambda_min(Gw)|x|_p^r, sum over permutations, compute the average of P_Gw(z_sigma) exactly using the k-partite structure, and bound the remaining factor by the Power Mean inequality. The unknown value lambda_min(K^k_r) appears only as a common factor and is never assumed to have a particular value; it is not a fitted input or a renamed prediction. Equation (8) computes lambda(K^k_r) from Maclaurin's inequality and the Power Mean inequality, so the right side of (3) is an explicit extremal ratio up to the genuinely unknown lambda_min(K^k_r), which is not needed for the direction of the proof. The equality case for regular complete k-partite r-graphs is verified by constructing x from y and checking both eigenvalue identities directly. The self-citations [9] and [10] supply the averaging method and the definition of lambda_min, respectively; these are independent prior tools, not the target inequality, and the argument does not rely on a self-citation to establish the theorem. The paper explicitly leaves the 1 <= p < r regime open in Problem 4 and does not claim it. No fitted-input-called-prediction, no uniqueness imported from authors, and no renaming of a known result as a new structure were found. The only noticeable defect is a harmless typographical range [r] instead of [k] for the permutation set, which does not affect the counts or the argument. Overall, the proof is independent and non-circular.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters or new entities are introduced. The proof draws on standard inequalities and on the variational definition of λ^(p) and λ_min^(p) from the prior literature. The only domain assumption is the non-degeneracy λ(p) > 0 > λ_min(p) for nonempty nonzero even-uniform weighted hypergraphs.

assumptions (4)

standard math Power Mean inequality: for nonnegative a_i and q ∈ [0,1], sum_i a_i^q ≤ m^(1-q) (sum_i a_i)^q
Used in equations (6), (8), Proposition 2, and the equality case to bound averages.
standard math Maclaurin's inequality: elementary symmetric means decrease with degree
Used to compute λ(p)(K^k_r) in (8) and to bound S2(A) and S2(B) in Proposition 2.
standard math Existence of maximizers and minimizers of a continuous polynomial over the compact l_p sphere
Invoked to select x and y attaining λ(p) and λ_min(p).
domain assumption For a nonempty weighted even-uniform hypergraph with not all weights zero, λ(p) > 0 and λ_min(p) < 0
Stated informally in Section 1 as 'Simple examples show...' and used for sign-sensitive divisions by λ_min.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Hoffman's bound for hypergraphs." pith.science (2026). https://pith.science/paper/PA5FMMCK

@misc{pith2026190801433,
  author       = {Pith},
  title        = {Pith review of: Hoffman's bound for hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PA5FMMCK}},
  note         = {Machine review of arXiv:1908.01433}
}

abstract

One of the best-known results in spectral graph theory is the inequality of Hoffman \[ \chi\left( G\right) \geq1-\frac{\lambda\left( G\right) }{\lambda_{\min }\left( G\right) }, \] where $\chi\left( G\right) $ is the chromatic number of a graph $G$ and $\lambda\left( G\right) ,$ $\lambda_{\min}\left( G\right) $ are the largest and the smallest eigenvalues of its adjacency matrix. In this note Hoffman's inequality is extended to weighted uniform $r$-graphs for every even $r$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Spectral Theory of Hypergraphs: A Survey
math.HO 2025-07 conditional

A survey of hypergraph spectral theory via tensors, compiling known bounds, characteristic polynomials, and Turán-type results without new mathematical contributions.

Reference graph

Works this paper leans on

12 extracted references · 11 canonical work pages · cited by 1 Pith paper

[9]

Nikiforov , Chromatic number and spectral radius, Linear Algebra Appl

V . Nikiforov , Chromatic number and spectral radius, Linear Algebra Appl. 426 (2007), 810–814

work page 2007
[10]

Nikiforov , Analytic methods for uniform hypergraphs, Linear Algebra Appl

V . Nikiforov , Analytic methods for uniform hypergraphs, Linear Algebra Appl. 457 (2014), 455–535

work page 2014
[1]

Cooper and A

J. Cooper and A. Dutle, Spectra of hypergraphs, Linear Algebra Appl. 436 (2012) 3268– 3292

work page 2012
[2]

Godsil and G

C. Godsil and G. Royle, Algebraic Graph Theory , Graduate Texts in Mathematics vol. 207, Springer-V erlag, New York, 2001, xx+439pp

work page 2001
[3]

Hoffman, On eigenvalues and colorings of graphs, in Graph Theory and its Applica- tions, Academic Press, New York (1970), pp

A.J. Hoffman, On eigenvalues and colorings of graphs, in Graph Theory and its Applica- tions, Academic Press, New York (1970), pp. 79–91

work page 1970
[4]

Horn and C

R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985. xiii+561 pp

work page 1985
[5]

Keevash, J

P . Keevash, J. Lenz, and D. Mubayi, Spectral extremal pro blems for hypergraphs, SIAM J. Discrete Math., 28 (2013), 1838–1854

work page 2013
[6]

L.-H. Lim, Singular values and eigenvalues of hypermatr ices: a variational approach, in Proceedings of the IEEE International Workshop on Computat ional Advances in Multi-Sensor Adaptive Processing (CAMSAP ’05) 1 (2005), pp. 129–132

2005

Show all 12 references

[7]

Kenter, Necessary spectral conditions for coloring h ypergraphs, J

F. Kenter, Necessary spectral conditions for coloring h ypergraphs, J. Combin. Math. Com- bin. Comput. 88 (2014), 73–84

2014
[8]

Lovász, On the Shannon capacity of a graph

L. Lovász, On the Shannon capacity of a graph. IEEE T ransactions Information Theory IT-25(1979), 1–7. 8

1979
[11]

Qi, Eigenvalues of a real supersymmetric tensor, J

L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput. 40 (2005) 1302– 1324

2005
[12]

Qi, Symmetric nonnegative tensors and copositive te nsors, Linear Algebra Appl

L. Qi, Symmetric nonnegative tensors and copositive te nsors, Linear Algebra Appl. 439 (2013), 228–238. 9

2013

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [9]

Nikiforov , Chromatic number and spectral radius, Linear Algebra Appl

V . Nikiforov , Chromatic number and spectral radius, Linear Algebra Appl. 426 (2007), 810–814

work page 2007

[2] [10]

Nikiforov , Analytic methods for uniform hypergraphs, Linear Algebra Appl

V . Nikiforov , Analytic methods for uniform hypergraphs, Linear Algebra Appl. 457 (2014), 455–535

work page 2014

[3] [1]

Cooper and A

J. Cooper and A. Dutle, Spectra of hypergraphs, Linear Algebra Appl. 436 (2012) 3268– 3292

work page 2012

[4] [2]

Godsil and G

C. Godsil and G. Royle, Algebraic Graph Theory , Graduate Texts in Mathematics vol. 207, Springer-V erlag, New York, 2001, xx+439pp

work page 2001

[5] [3]

Hoffman, On eigenvalues and colorings of graphs, in Graph Theory and its Applica- tions, Academic Press, New York (1970), pp

A.J. Hoffman, On eigenvalues and colorings of graphs, in Graph Theory and its Applica- tions, Academic Press, New York (1970), pp. 79–91

work page 1970

[6] [4]

Horn and C

R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985. xiii+561 pp

work page 1985

[7] [5]

Keevash, J

P . Keevash, J. Lenz, and D. Mubayi, Spectral extremal pro blems for hypergraphs, SIAM J. Discrete Math., 28 (2013), 1838–1854

work page 2013

[8] [6]

L.-H. Lim, Singular values and eigenvalues of hypermatr ices: a variational approach, in Proceedings of the IEEE International Workshop on Computat ional Advances in Multi-Sensor Adaptive Processing (CAMSAP ’05) 1 (2005), pp. 129–132

2005