Support and Support Jumps in the Partition Graph

Abstract

Let $G_n$ be the partition graph whose vertices are the partitions of $n$, with adjacency given by elementary transfers of one cell between parts, followed by reordering. We study the support of a partition -- the set of distinct part sizes -- as a global vertex invariant of $G_n$. We show that support size $r$ occurs in $G_n$ if and only if $T_r=r(r+1)/2\le n$, so the maximal support size is $\ddot{I}(n)=\max \{r:T_r\le n\}$. We determine exactly how support changes along an edge: the support jump always lies in $\{-2,-1,0,1,2\}$, and we give an explicit birth-death formula in terms of the source and target part sizes. We also prove the degree bound $\hat{A}°(\hat{I}»)\ge \ddot{I}ƒ(\hat{I}»)(\ddot{I}ƒ(\hat{I}»)-1)$ for every partition $\hat{I}»$, with equality exactly for staircase partitions. In addition, support size is invariant under conjugation, the support-$1$ stratum consists exactly of rectangular partitions, and the coarse support-level graph always contains the chain $1-2-\cdots -\ddot{I}(n)$. We conclude with computational data for small $n$, including support-stratum counts, support-jump counts, and connectivity data for fixed-support subgraphs.

24 pages, 5 tables