Sperner Properties for Groups and Relations

An equivalence on the family of subsets of an e-element set E is hereditary if |a| = |b| and |x{⊆a:x∼}|=|x{⊆b:x∼}| whenever a, b, c, ⊂ E and a ˜ b. Let Wi˜ denote the number of blocks of ˜ consisting of i-element sets. Setting e=⌊1/2e⌋ we prove W0~≤⋯≤We~andWp~≤We−p~ for all p≼e′. The equivalence ˜ is symmetric (is selfdual) if Wp~=We−p~ for all p (if a ∼ b⇔E\a∼E\b). We prove ˜ is symmetric if ˜ is selfdual. The set of blocks of ˜ has a natural order with X ≼ Y if x ⊆ y for some x ∈ X and y ∈ Y. We study the properties of this order, in particular, we prove that for ˜ symmetric the order has the strong Sperner property: for all k the union of the k largest levels is a maximum sized k-family (i.e. a maximum sized union of k antichains). For a permutation group G on E put a ˜ Gb if b = g(a) for some g ∈ G. This set-orbit partition is symmetric and therefore the associated order has the strong Sperner property. A direct application proves that the following finite orders have the strong Sperner property: (a) product of chains (De Bruijn et al., 1949) and (b) the initial segments of the product of two chains (Stanley, 1980). Another consequence is that among the unlabelled graphs on n vertices the graphs with ⌊12(n2)Ȱ edges form a maximum sized family allowing no embedding (as a subgraph) between its members. For a binary relation R set a ˜ Rb if R ⋂ a2 (i.e. the restriction of R to the set a) is isomorphic to R⋂b2. This equivalence is hereditary. Its equivalence classes are essentially the isomorphism types of restrictions of R and the above order is the usual embedability order of isomorphism types. A consequence of the main result is that for a homogeneous R the order has the strong Sperner property