View Related Documents

Abstract

Let X = {1, . . . , n}, and let $ {\user1{A}} $ {\user1{A}} be a family of subsets of X. Given the size of $ {\user1{A}} $ {\user1{A}} , at least how many pairs of elements of $ {\user1{A}} $ {\user1{A}} must be disjoint? In this paper we give a lower bound for the number of disjoint pairs in $ {\user1{A}} $ {\user1{A}} . The bound we obtain is essentially best possible. In particular, we give a new proof of a result of Frankl and of Ahlswede, that if $ {\user1{A}} $ {\user1{A}} satisfies $ {\left| {\user1{A}} \right|} = {\left| {X^{{{\left( { \geqslant r} \right)}}} } \right|} $ {\left| {\user1{A}} \right|} = {\left| {X^{{{\left( { \geqslant r} \right)}}} } \right|} then $ {\user1{A}} $ {\user1{A}} contains at least as many disjoint pairs as X($ {\user1{A}} \subset X^{{{\left( r \right)}}} $ {\user1{A}} \subset X^{{{\left( r \right)}}} : then we are asking for the minimum number of edges spanned by a subset of the Kneser graph of given size. We make a conjecture on this lower bound, and disprove a related conjecture of Poljak and Tuza on the largest bipartite subgraph of the Kneser graph.

Mathematics Subject Classification (2000):  05D05 - 05C65

* Research partially supported by NSF grant DMS-9971788

Fulltext Preview

Image of the first page of the fulltext document

Frequently asked questions General info on journals and books Send us your feedback Impressum Contact us

© Springer, Part of Springer Science+Business Media Privacy, Disclaimer, Terms & Conditions, and Copyright Info