Shifted set families, degree sequences, and plethysm

C. Klivans ; V. Reiner

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

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.

Détail

DOI : 10.37236/738

Classification : 05C07, 05C65, 05E05
Mots-clés : graphical degree sequences, \(k\)-families, \(k\)-uniform hypergraphs, shifted \(k\)-families, plethysm of elementary symmetric function