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.is thatHypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972). Lecture Notes in Math., Vol. 411, Springer, Berlin, 1974,

The following papers are directly related to this conjecture:

- 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)** - 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)** - 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)** - 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)** - 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)** -
P. Stein and J. Schönheim,
On Chvátal's conjecture related to hereditary systems.
*Ars Combin.***5**(1978), 275--291.**MR0498179 (58 #16334)** -
D.L. Wang and P. Wang,
Some results about the Chvátal conjecture.
*Discrete Math.***24**(1978), 95--101.**MR0522737 (80b:05003)** - 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)** -
V.V. Gritsak,
Independence systems of matroid type. (Russian)
*Dokl. Akad. Nauk Ukrain. SSR Ser. A***1982,**61--62, 87.**MR0678705 (84b:05009)** -
P. Stein,
On Chvátal's conjecture related to a hereditary system.
*Discrete Math.***43**(1983), 97--105.**MR0680308 (84d:05028)** -
P. Stein,
Chvátal's conjecture and point-intersections.
*Discrete Math.***43**(1983), 321--323.**MR0685640 (84g:05111)** -
D. Miklós,
Great intersecting families of edges in hereditary hypergraphs.
*Discrete Math.***48**(1984), 95--99.**MR0732205 (85c:05026)** -
P.C. Fishburn,
Combinatorial optimization problems for systems of subsets.
*SIAM Rev.***30**(1988), 578--588.**MR0967960 (89i:05003)** - 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)** - C. Berge, On two conjectures to generalize Vizing's theorem.
*Matematiche (Catania)***45**(1990), 15--23 (1991).**MR1180996 (94m:05137)** - H. Snevily, A new result on Chvátal's conjecture.
*J. Combin. Theory Ser. A***61**(1992), 137--141.**MR1178391 (93d:05004)** - M. Gionfriddo and Zs. Tuza, On conjectures of Berge and
Chvátal.
*Discrete Math.***124**(1994), 79--86.**MR1258844 (94m:05080)** - M. Gionfriddo and S. Milici, A result concerning two
conjectures of Berge and Chvátal.
*Discrete Math.***155**(1996), 77--79.**MR1401360 (97d:05036)** - 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)** - C. Bey, An
intersection theorem for weighted sets.
*Discrete Math.***235**(2001), 145--150.**MR1829843 (2002a:05243)** - Y. Wang, Notes on Chvátal's conjecture.
*Discrete Math.***247**(2002), 255--259.**MR1893035 (2003b:05152)** -
P. Borg,
Extremal $t$-intersecting sub-families of hereditary
families.
*J. Lond. Math. Soc. (2)***79**(2009), 167--185.**MR2472139 (2009k:05184)** - P. Borg, On
cross-intersecting uniform sub-families of hereditary families ,
paper
**R60**in*The Electronic Journal of Combinatorics*Volume 17(1), 2010 - P. Borg, On
Chvátal's conjecture and a conjecture on families
of signed sets,
*European Journal of Combinatorics***32**(2011), 140--145.

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