Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



On the chromatic number of Kneser hypergraphs

Author: Jirí Matousek
Journal: Proc. Amer. Math. Soc. 130 (2002), 2509-2514
MSC (2000): Primary 05C15, 05C65
Published electronically: January 23, 2002
MathSciNet review: 1900856
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We give a simple and elementary proof of Kríz's lower bound on the chromatic number of the Kneser $r$-hypergraph of a set system $\mathcal{S}$.

References [Enhancements On Off] (What's this?)

  • 1. N. Alon, P. Frankl, and L. Lovász.
    The chromatic number of Kneser hypergraphs.
    Trans. Amer. Math. Soc., 298:359-370, 1986. MR 88g:05098
  • 2. I. Bárány.
    A short proof of Kneser's conjecture.
    J. Combinatorial Theory Ser. A, 25:325-326, 1978. MR 81g:05056
  • 3. A. Björner.
    Topological methods.
    In Handbook of Combinatorics (eds. R. Graham, M. Grötschel, L. Lovász), pages 1819-1872. North-Holland, Amsterdam, 1995. MR 96m:52012
  • 4. A. Dold.
    Simple proofs of some Borsuk-Ulam results.
    In Contemp. Math. 19, pages 65-69. Amer. Math. Soc., 1983. MR 85e:55003
  • 5. V. L. Dol'nikov.
    Transversals of families of sets.
    In Studies in the theory of functions of several real variables (Russian), pages 30-36, 109. Yaroslav. Gos. Univ., Yaroslavl', 1981. CMP 20:03
  • 6. V. L. Dol'nikov.
    A combinatorial inequality.
    Siberian Math. J., 29, 1988.
    Translated from Sibirsk. Mat. Zh., 29:53-58, 1988. MR 89k:05079
  • 7. V. L. Dol'nikov.
    Transversals of families of sets in $R^n$ and a connection between the Helly and Borsuk theorems.
    Russian Acad. Sci. Sb. Math., 79:93-107, 1994.
    Translated from Ross. Akad. Nauk Matem. Sbornik, Tom 184, No. 5, 1993. MR 94g:52005
  • 8. M. Kneser.
    Aufgabe 360.
    Jahresbericht der Deutschen Mathematiker-Vereinigung, 2. Abteilung, 58:27, 1955.
  • 9. M. A. Krasnosel'skii.
    On the estimation of the number of critical points of functionals (in Russian).
    Uspehi Mat. Nauk, 7:157-164, 1952. MR 14:55f
  • 10. I. Kríz.
    Equivariant cohomology and lower bounds for chromatic numbers.
    Trans. Amer. Math. Soc., 333:567-577, 1992. MR 92m:05085
  • 11. I. Kríz.
    A correction to ``Equivariant cohomology and lower bounds for chromatic numbers'' (Trans. Amer. Math. Soc. 333 (1992) 567-577).
    Trans. Amer. Math. Soc., 352(4):1951-1952, 2000. MR 2000i:05078
  • 12. L. Lovász.
    Kneser's conjecture, chromatic number and homotopy.
    J. Combinatorial Theory Ser. A, 25:319-324, 1978. MR 81g:05059
  • 13. J. Matousek. A combinatorial proof of Kneser's conjecture. Combinatorica, 2001, in press.
  • 14. K. S. Sarkaria.
    A generalized Kneser conjecture.
    J. Combinatorial Theory Ser. B, 49:236-240, 1990. MR 91g:05003
  • 15. G. M. Ziegler. Generalized Kneser coloring theorems with combinatorial proofs. Invent. Math., in press.
  • 16. R. T. Zivaljevic.
    User's guide to equivariant methods in combinatorics.
    Publ. Inst. Math. Beograd, 59(73):114-130, 1996. MR 98c:55001
  • 17. R. T. Zivaljevic.
    Topological methods.
    In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 11, pages 209-224. CRC Press LLC, Boca Raton, FL, 1997. MR 2000j:52001

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 05C15, 05C65

Retrieve articles in all journals with MSC (2000): 05C15, 05C65

Additional Information

Jirí Matousek
Affiliation: Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic

Received by editor(s): January 12, 2000
Received by editor(s) in revised form: March 30, 2001
Published electronically: January 23, 2002
Additional Notes: This research was supported by Charles University grants No. 158/99 and 159/99
Communicated by: John R. Stembridge
Article copyright: © Copyright 2002 American Mathematical Society

American Mathematical Society