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 language | English (US) |
---|---|
Pages (from-to) | 1-35 |
Number of pages | 35 |
Journal | Electronic Journal of Combinatorics |
Volume | 15 |
Issue number | 1 R |
DOIs | |
State | Published - Jan 14 2008 |