The Degree Landscape of the Partition Graph: Maximal Degree, Extremal Vertices, and Spectra

Abstract

We study the degree landscape of the partition graph $G_n$, whose vertices are the integer partitions of $n$ and whose edges correspond to elementary transfers of one unit between parts, followed by reordering. Using the previously established local degree formula, we introduce the degree layers $D_d(n)$, the degree spectrum $Spe{c}_D(n)$, and the numerical invariants ${\Delta }_n$, $m_{\Delta }(n)$, and $s(n)$. The main theorem provides an exact formula for the maximal degree. If $$\rho (n):=\max \{r:T_r\le n\},T_r=\frac{r(r+1)}{2},$$ and $$\nu :=n-T_{\rho (n)},$$ then $${\Delta }_n=\rho (n)(\rho (n)-1)+{\beta }_{\rho (n)}(\nu ),$$ where ${\beta }_r$ is an explicit budget function governed by a square--pronic threshold rule. We also prove that every maximal-degree vertex lies on the maximal-support stratum, and we obtain exact extremal classifications at the levels $n=T_t$, $n=T_t+1$, and $n=T_t+2$. The paper also includes a finite computation on the range $1\le n\le 60$, recording extremal multiplicities, representative extremal shapes, spectrum sizes, selected degree histograms, and first data on contact between the extremal layer and the self-conjugate axis. This computational part is deliberately limited in scope. It is descriptive rather than exhaustive, and is included only as a first numerical profile of the degree landscape.

arXiv comment30 pages, 1 figure