Shifted set families, degree sequences, and plethysm

2006/10/26 by Caroline Klivans, Klivans, Caroline, Victor Reiner +1
Mathematics · #05C07 #05C65 #05E05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C07 #msc:05C65 #msc:05E05

paper · pdf · doi:10.48550/arxiv.math/0610787

Final version, 26 pages, 3 figures

arxiv created 2008/01/10 · arxiv updated 2009/12/01

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 implies Uniquely Realizable implies Degree-Maximal implies Shifted, which are equivalent concepts for 2-families (=simple graphs), but strict implications for k-families with k > 2. 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 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.

Related

• On the Degree Sequences of Multigraphs with Edge Additions and Deletions
• A degree sequence version of the Kühn-Osthus tiling theorem
• Nonconvexity of the set of hypergraph degree sequences
• A degree sequence strengthening of the vertex degree threshold for a perfect matching in 3-uniform hypergraphs
• The polytope of degree partitions