The strong Hall property and symmetric chain orders

Abstract

Let G=(X,Y;E) be a bipartite graph with \X\≥\Y\. For A⊆X, write φ(A)=|A|-\N(A)\ and for a≤\X\, define φ(a)=max{φ(A)|A⊆X, \A\=a}. The graph G is said to have the strong Hall property if φ(a)+φ(b)≤\X\-\Y\ for all nonnegative integers a and b with a+b≤|X|. We shall prove that any unimodal and self-dual poset with the strong Hall property is a symmetric chain order. This result will also be used to show that the inversion poset S5 is a symmetric chain order. © 1999 Elsevier Science B.V. All rights reserved.