Shifted set families, degree sequences, and plethysm

C. Klivans, V. Reiner

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

We study, in three parts, degree sequences of k-families (or k-uniform hypergraphs) and shifted k-families. The first part collects for the first time in one place, various implications such as Threshold ⇒ Uniquely Realizable ⇒ Degree-Maximal ⇒ Shifted which are equivalent concepts for 2-families (= simple graphs), but strict implications for k-families with k ≥ 3. The implication that uniquely realizable implies degree-maximal seems to be new. 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. The third part recalls the connection between degree sequences of k-families of size m and the plethysm of elementary symmetric functions em[ek]. 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.

Original languageEnglish (US)
Pages (from-to)1-35
Number of pages35
JournalElectronic Journal of Combinatorics
Volume15
Issue number1 R
DOIs
StatePublished - Jan 14 2008

Fingerprint Dive into the research topics of 'Shifted set families, degree sequences, and plethysm'. Together they form a unique fingerprint.

Cite this