Proceedings of the American Mathematical Society

Author(s): Jirí Matousek
Journal: Proc. Amer. Math. Soc. 130 (2002), 2509-2514.
MSC (2000): Primary 05C15, 05C65
Posted: January 23, 2002
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract: We give a simple and elementary proof of Kríz's lower bound on the chromatic number of the Kneser

-hypergraph of a set system $\mathcal{S}$ .

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 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

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

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
Email: matousek@kam.mff.cuni.cz

DOI: 10.1090/S0002-9939-02-06371-2
PII: S 0002-9939(02)06371-2
Received by editor(s): January 12, 2000
Received by editor(s) in revised form: March 30, 2001
Posted: January 23, 2002
Additional Notes: This research was supported by Charles University grants No. 158/99 and 159/99
Communicated by: John R. Stembridge
Copyright of article: Copyright 2002, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6826 (e) ISSN 0002-9939 (p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS