On the chromatic number of Kneser hypergraphs
HTML articles powered by AMS MathViewer
- by Jiří Matoušek PDF
- Proc. Amer. Math. Soc. 130 (2002), 2509-2514 Request permission
Abstract:
We give a simple and elementary proof of Kříž’s lower bound on the chromatic number of the Kneser $r$-hypergraph of a set system $\mathcal {S}$.References
- N. Alon, P. Frankl, and L. Lovász, The chromatic number of Kneser hypergraphs, Trans. Amer. Math. Soc. 298 (1986), no. 1, 359–370. MR 857448, DOI 10.1090/S0002-9947-1986-0857448-8
- I. Bárány, A short proof of Kneser’s conjecture, J. Combin. Theory Ser. A 25 (1978), no. 3, 325–326. MR 514626, DOI 10.1016/0097-3165(78)90023-7
- A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819–1872. MR 1373690
- Albrecht Dold, Simple proofs of some Borsuk-Ulam results, Proceedings of the Northwestern Homotopy Theory Conference (Evanston, Ill., 1982) Contemp. Math., vol. 19, Amer. Math. Soc., Providence, RI, 1983, pp. 65–69. MR 711043, DOI 10.1090/conm/019/711043
- 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.
- V. L. Dol′nikov, A combinatorial inequality, Sibirsk. Mat. Zh. 29 (1988), no. 3, 53–58, 219 (Russian); English transl., Siberian Math. J. 29 (1988), no. 3, 375–379 (1989). MR 953021, DOI 10.1007/BF00969645
- V. L. Dol′nikov, Transversals of families of sets in $\textbf {R}^n$ and a relationship between Helly and Borsuk theorems, Mat. Sb. 184 (1993), no. 5, 111–132 (Russian, with Russian summary); English transl., Russian Acad. Sci. Sb. Math. 79 (1994), no. 1, 93–107. MR 1239754, DOI 10.1070/SM1994v079n01ABEH003491
- M. Kneser. Aufgabe 360. Jahresbericht der Deutschen Mathematiker-Vereinigung, 2. Abteilung, 58:27, 1955.
- P. Hebroni, Sur les inverses des éléments dérivables dans un anneau abstrait, C. R. Acad. Sci. Paris 209 (1939), 285–287 (French). MR 14
- Igor Kříž, Equivariant cohomology and lower bounds for chromatic numbers, Trans. Amer. Math. Soc. 333 (1992), no. 2, 567–577. MR 1081939, DOI 10.1090/S0002-9947-1992-1081939-3
- Igor Kriz, A correction to: “Equivariant cohomology and lower bounds for chromatic numbers” [Trans. Amer. Math. Soc. 333 (1992), no. 2, 567–577; MR1081939 (92m:05085)], Trans. Amer. Math. Soc. 352 (2000), no. 4, 1951–1952. MR 1665335, DOI 10.1090/S0002-9947-99-02494-0
- L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), no. 3, 319–324. MR 514625, DOI 10.1016/0097-3165(78)90022-5
- J. Matoušek. A combinatorial proof of Kneser’s conjecture. Combinatorica, 2001, in press.
- K. S. Sarkaria, A generalized Kneser conjecture, J. Combin. Theory Ser. B 49 (1990), no. 2, 236–240. MR 1064678, DOI 10.1016/0095-8956(90)90029-Y
- G. M. Ziegler. Generalized Kneser coloring theorems with combinatorial proofs. Invent. Math., in press.
- Rade T. Živaljević, User’s guide to equivariant methods in combinatorics, Publ. Inst. Math. (Beograd) (N.S.) 59(73) (1996), 114–130. MR 1444570
- Jacob E. Goodman and Joseph O’Rourke (eds.), Handbook of discrete and computational geometry, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. MR 1730156
Additional Information
- Jiří Matoušek
- 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
- 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
- © Copyright 2002 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 130 (2002), 2509-2514
- MSC (2000): Primary 05C15, 05C65
- DOI: https://doi.org/10.1090/S0002-9939-02-06371-2
- MathSciNet review: 1900856