<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue2" %>
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
AMS Subject Classification: 05C35, 05D05, 06A07
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.
Keywords: antichain, blocker, partition, dominance, refinement, blocking set, Turán

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.