A Note on Blockers in Posets

Anders Björner and Axel Hultman

Department of Mathematics, Royal Institute of Technology, 100 44, Stockholm, Sweden

{bjorner, axel}@math.kth.se

Annals of Combinatorics 8 (2) p.123-131 June, 2004

Abstract:

The *blocker* *A*^{*} of an antichain *A* in a finite poset *P* is the set of elements minimal with the property of having with each member of *A* a common predecessor. The following is done:

(1) The posets*P* for which *A*^{**} = *A* for all antichains are characterized.

(2) The blocker*A*^{*} of a symmetric antichain in the partition lattice is characterized.

(3) Connections with the question of finding minimal size blocking sets for certain set families are discussed.

(1) The posets

(2) The blocker

(3) Connections with the question of finding minimal size blocking sets for certain set families are discussed.

References:

1. M. Aigner, Combinatorial Theory, Springer-Verlag, Berlin-Heidelberg-New York, 1979, Reprint Edition, 1997.

2. A. Björner, Subspace arrangements, In: First European Congress of Mathematics, Vol. I, Paris, 1992, Progr. Math., Vol. 119, Birkhäuser, Basel, 1994, pp. 321--370.

3. A. Björner, I. Peeva, and J. Sidman, Subspace arrangements defined by products of linear forms, preprint, 2003, available at http://arXiv.org/abs/math/0401373.

4. J. Edmonds and D. Fulkerson, Bottleneck extrema, J. Combin. Theory 8 (1970) 299--306.

5. J.W.P. Hirschfeld, Projective Geometries over Finite Fields, 2nd Ed., Oxford University Press, 1998.

6. A. Lehman, A solution of the Shannon switching game, SIAM J. Appl. Math. 12 (1964) 687--725.

7. S.-Y.R. Li and W.-C.W. Li, Independence numbers of graphs and generators of ideals, Combinatorica 1 (1981) 55--61.

8. L. Lovász, Stable sets and polynomials, Discrete Math. 124 (1994) 137--153.

9. A.O. Matveev, On blockers in bounded posets, Int. J. Math. Math. Sci. 26 (2001) 581--588.

10. M. Simonovits, Extremal graph problems with symmetrical extremal graphs, additional chromatic conditions, Discrete Math. 7 (1974) 349--376.