A conjecture in extremal combinatorics


An independence system is a family of sets closed under taking subsets: if I is an independence system, if T belongs to I, and if S is a subset of T, then S also belongs to I. An intersecting family is a family of sets that includes no two disjoint sets. A star in an independence system consists of all its members that include a prescribed point.

The independence system that consists only of the empty set is an intersecting family and it has no nonempty star. The conjecture (Problem 25) in

Selected combinatorial research problems (V. Chvátal, D.A. Klarner, and D.E. Knuth), STAN CS-72-292, June 1972,
also reproduced in
V. Chvátal, Unsolved Problem No. 7. Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972) . Lecture Notes in Math., Vol. 411, Springer, Berlin, 1974,
is that
no other independence system contains an intersecting subfamily that is larger than its largest star.

The following papers are directly related to this conjecture:

  1. V. Chvátal, Intersecting families of edges in hypergraphs having the hereditary property. Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972), pp. 61--66. Lecture Notes in Math., Vol. 411, Springer, Berlin, 1974. MR0369170   (51 #5405)

  2. F. Sterboul, Sur une conjecture de V. Chvátal. Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972), pp. 152--164. Lecture Notes in Math., Vol. 411, Springer, Berlin, 1974. MR0379216   (52 #122)

  3. D.J. Kleitman and T.L. Magnanti, On the number of latent subsets of intersecting collections. J. Combinatorial Theory Ser. A 16 (1974), 215--220. MR0329908   (48 #8248)

  4. C. Berge, A theorem related to the Chvátal conjecture. Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), pp. 35--40. Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976. MR0409275   (53 #13035)

  5. J. Schönheim, Hereditary systems and Chvátal's conjecture. Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), pp. 537--539. Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976. MR0392586   (52 #13403)

  6. P. Stein and J. Schönheim, On Chvátal's conjecture related to hereditary systems. Ars Combin. 5 (1978), 275--291. MR0498179   (58 #16334)

  7. D.L. Wang and P. Wang, Some results about the Chvátal conjecture. Discrete Math. 24 (1978), 95--101. MR0522737   (80b:05003)

  8. D.J. Kleitman, Extremal hypergraph problems. Surveys in combinatorics (Proc. Seventh British Combinatorial Conf., Cambridge, 1979), pp. 44--65. London Math. Soc. Lecture Note Ser. 38, Cambridge Univ. Press, Cambridge-New York, 1979. MR0561306   (81d:05061)

  9. V.V. Gritsak, Independence systems of matroid type. (Russian) Dokl. Akad. Nauk Ukrain. SSR Ser. A 1982, 61--62, 87. MR0678705   (84b:05009)

  10. P. Stein, On Chvátal's conjecture related to a hereditary system. Discrete Math. 43 (1983), 97--105. MR0680308   (84d:05028)

  11. P. Stein, Chvátal's conjecture and point-intersections. Discrete Math. 43 (1983), 321--323. MR0685640   (84g:05111)

  12. D. Miklós, Great intersecting families of edges in hereditary hypergraphs. Discrete Math. 48 (1984), 95--99. MR0732205   (85c:05026)

  13. P.C. Fishburn, Combinatorial optimization problems for systems of subsets. SIAM Rev. 30 (1988), 578--588. MR0967960   (89i:05003)

  14. C. Berge, On the chromatic index of a linear hypergraph and the Chvátal conjecture. Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985), 40--44, Ann. New York Acad. Sci., 555, New York Acad. Sci., New York, 1989. MR1018607   (90j:05101)

  15. C. Berge, On two conjectures to generalize Vizing's theorem. Matematiche (Catania) 45 (1990), 15--23 (1991). MR1180996   (94m:05137)

  16. H. Snevily, A new result on Chvátal's conjecture. J. Combin. Theory Ser. A 61 (1992), 137--141. MR1178391   (93d:05004)

  17. M. Gionfriddo and Zs. Tuza, On conjectures of Berge and Chvátal. Discrete Math. 124 (1994), 79--86. MR1258844   (94m:05080)

  18. M. Gionfriddo and S. Milici, A result concerning two conjectures of Berge and Chvátal. Discrete Math. 155 (1996), 77--79. MR1401360   (97d:05036)

  19. A.D. Taylor, Chvátal's conjecture, Section 3.5. of A.D. Taylor and W.S. Zwicker, Simple Games: Desirability Relations, Trading, Pseudoweightings, Princeton University Press, 1999. MR1714706   (2000k:91028)

  20. C. Bey, An intersection theorem for weighted sets. Discrete Math. 235 (2001), 145--150. MR1829843   (2002a:05243)

  21. Y. Wang, Notes on Chvátal's conjecture. Discrete Math. 247 (2002), 255--259. MR1893035   (2003b:05152)

  22. P. Borg, Extremal $t$-intersecting sub-families of hereditary families. J. Lond. Math. Soc. (2) 79 (2009), 167--185. MR2472139   (2009k:05184)

  23. P. Borg, On cross-intersecting uniform sub-families of hereditary families , paper R60 in The Electronic Journal of Combinatorics Volume 17(1), 2010

  24. P. Borg, On Chvátal's conjecture and a conjecture on families of signed sets, European Journal of Combinatorics 32 (2011), 140--145.
There is also
Variations on Chvátal's Conjecture (2009),
a set of questions originating with H. Snevily and presented by D.B. West in the Research Experiences for Graduate Students in Combinatorics of the University of Illinois at Urbana-Champaign. (The mathematical symbols on this web page do not show up correctly in all browsers. They do show up correctly in Google Chrome.)
Back to Vašek Chvátal's home page