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:
- 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.
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
Vaek Chvátal's home page