Shifted Set Families, Degree Sequences, and Plethysm

Abstract

We study, in three parts, degree sequences of $k$-families (or $k$-uniform hypergraphs) and shifted $k$-families.
$\bullet$ The first part collects for the first time in one place, various implications such as $$ \scriptstyle \hbox{Threshold} \Rightarrow \hbox{Uniquely Realizable} \Rightarrow \hbox{Degree-Maximal} \Rightarrow \hbox{Shifted} $$ which are equivalent concepts for $2$-families (= simple graphs), but strict implications for $k$-families with $k \geq 3$. The implication that uniquely realizable implies degree-maximal seems to be new.
$\bullet$ The second part recalls Merris and Roby's reformulation of the characterization due to Ruch and Gutman for graphical degree sequences and shifted $2$-families. It then introduces two generalizations which are characterizations of shifted $k$-families.

$\bullet$ The third part recalls the connection between degree sequences of $k$-families of size $m$ and the plethysm of elementary symmetric functions $e_m[e_k]$. It then uses highest weight theory to explain how shifted $k$-families provide the "top part" of these plethysm expansions, along with offering a conjecture about a further relation.