The spectral radius of $k$-chromatic $r$-graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918501616189440 |
|---|---|
| author | Liu, Xizhi Luo, Junchi |
| author_facet | Liu, Xizhi Luo, Junchi |
| contents | For an $r$-uniform hypergraph $G$, let $λ^{(p)}(G)$ denote its $p$-spectral radius, defined as the maximum of the polyform of $G$ over the unit sphere in the $\ell_p$-norm. Let $Q_k^r(n)$ be the complete $k$-chromatic $r$-graph on $n$ vertices with color classes as equal as possible. Kang--Nikiforov--Yuan conjectured that, for every $p\ge1$ and $n>(r-1)k$, the $r$-graph $Q_k^r(n)$ is the unique maximizer of $λ^{(p)}$ among all $k$-chromatic $r$-graphs of order $n$. They also conjectured the corresponding explicit bound \[
λ^{(p)}(G)
\le
r!\left(\tbinom nr-k\tbinom{n/k}{r}\right)n^{-r/p}, \] with equality only in the divisible extremal case. The case $r=3$ was established in their work. This paper resolves the remaining cases $r\ge4$, and hence settles both conjectures for all $r\ge3$. As a consequence, the same threshold gives an anti-Wilf-type spectral certificate: any $r$-graph of order $n$ whose $p$-spectral radius exceeds the displayed bound has chromatic number at least $k+1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_14755 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The spectral radius of $k$-chromatic $r$-graphs Liu, Xizhi Luo, Junchi Combinatorics For an $r$-uniform hypergraph $G$, let $λ^{(p)}(G)$ denote its $p$-spectral radius, defined as the maximum of the polyform of $G$ over the unit sphere in the $\ell_p$-norm. Let $Q_k^r(n)$ be the complete $k$-chromatic $r$-graph on $n$ vertices with color classes as equal as possible. Kang--Nikiforov--Yuan conjectured that, for every $p\ge1$ and $n>(r-1)k$, the $r$-graph $Q_k^r(n)$ is the unique maximizer of $λ^{(p)}$ among all $k$-chromatic $r$-graphs of order $n$. They also conjectured the corresponding explicit bound \[ λ^{(p)}(G) \le r!\left(\tbinom nr-k\tbinom{n/k}{r}\right)n^{-r/p}, \] with equality only in the divisible extremal case. The case $r=3$ was established in their work. This paper resolves the remaining cases $r\ge4$, and hence settles both conjectures for all $r\ge3$. As a consequence, the same threshold gives an anti-Wilf-type spectral certificate: any $r$-graph of order $n$ whose $p$-spectral radius exceeds the displayed bound has chromatic number at least $k+1$. |
| title | The spectral radius of $k$-chromatic $r$-graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.14755 |