The chromatic number of Kneser hypergraphs

Alon, N.; Frankl, P.; Lovász, L.

doi:10.1090/S0002-9947-1986-0857448-8

The chromatic number of Kneser hypergraphs
HTML articles powered by AMS MathViewer

by N. Alon, P. Frankl and L. Lovász PDF

Trans. Amer. Math. Soc. 298 (1986), 359-370 Request permission

Abstract:

Suppose the $r$-subsets of an $n$-element set are colored by $t$ colors. THEOREM 1.1. If $n \geq (t - 1)(k - 1) + k \cdot r$, then there are $k$ pairwise disjoint $r$-sets having the same color. This was conjectured by Erdös $[{\mathbf {E}}]$ in 1973. Let $T(n, r, s)$ denote the Turán number for $s$-uniform hypergraphs (see $\S 1$). THEOREM 1.3. If $\varepsilon > 0, t \leq (1 - \varepsilon )T(n, r, s)/(k - 1)$, and $n > {n_0}(\varepsilon , r, s, k)$, then there are $k$ $r$-sets ${A_1},{A_2}, \ldots ,{A_k}$ having the same color such that $\left | {{A_i} \cap {A_j}} \right | < s$ for all $1 \leq i < j \leq k$. If $s = 2, \varepsilon$ can be omitted. Theorem 1.1 is best possible. Its proof generalizes Lovász’ topological proof of the Kneser conjecture (which is the case $k = 2$). The proof uses a generalization, due to Bárány, Shlosman, and Szücs of the Borsuk-Ulam theorem. Theorem 1.3 is best possible up to the $\varepsilon$-term (for large $n$). Its proof is purely combinatorial, and employs results on kernels of sunflowers.

References

N. Alon and P. Frankl, Families in which disjoint sets have large union, Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985) Ann. New York Acad. Sci., vol. 555, New York Acad. Sci., New York, 1989, pp. 9–16. MR 1018603, DOI 10.1111/j.1749-6632.1989.tb22431.x
Noga Alon, Splitting necklaces, Adv. in Math. 63 (1987), no. 3, 247–253. MR 877785, DOI 10.1016/0001-8708(87)90055-7
Noga Alon and Douglas B. West, The Borsuk-Ulam theorem and bisection of necklaces, Proc. Amer. Math. Soc. 98 (1986), no. 4, 623–628. MR 861764, DOI 10.1090/S0002-9939-1986-0861764-9
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

Homotopy properties of greedoids

Béla Bollobás, On complete subgraphs of different orders, Math. Proc. Cambridge Philos. Soc. 79 (1976), no. 1, 19–24. MR 424614, DOI 10.1017/S0305004100052063
Karol Borsuk, On the imbedding of systems of compacta in simplicial complexes, Fund. Math. 35 (1948), 217–234. MR 28019, DOI 10.4064/fm-35-1-217-234
D. G. Bourgin, Modern algebraic topology, The Macmillan Company, New York; Collier Macmillan Ltd., London, 1963. MR 0160201
I. Bárány, S. B. Shlosman, and A. Szűcs, On a topological generalization of a theorem of Tverberg, J. London Math. Soc. (2) 23 (1981), no. 1, 158–164. MR 602247, DOI 10.1112/jlms/s2-23.1.158
E. J. Cockayne and P. J. Lorimer, The Ramsey number for stripes, J. Austral. Math. Soc. 19 (1975), 252–256. MR 0371733
Paul Erdős, Problems and results in combinatorial analysis, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973) Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome, 1976, pp. 3–17 (English, with Italian summary). MR 0465878
P. Erdős and R. Rado, Intersection theorems for systems of sets, J. London Math. Soc. 35 (1960), 85–90. MR 111692, DOI 10.1112/jlms/s1-35.1.85
P. Erdős, Chao Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2) 12 (1961), 313–320. MR 140419, DOI 10.1093/qmath/12.1.313
Paul Erdős and Miklós Simonovits, Supersaturated graphs and hypergraphs, Combinatorica 3 (1983), no. 2, 181–192. MR 726456, DOI 10.1007/BF02579292
Péter Frankl, On intersecting families of finite sets, J. Combinatorial Theory Ser. A 24 (1978), no. 2, 146–161. MR 480051, DOI 10.1016/0097-3165(78)90003-1
P. Frankl, On the chromatic number of the general Kneser-graph, J. Graph Theory 9 (1985), no. 2, 217–220. MR 797510, DOI 10.1002/jgt.3190090204
P. Frankl and Z. Füredi, Extremal problems concerning Kneser graphs, J. Combin. Theory Ser. B 40 (1986), no. 3, 270–284. MR 842995, DOI 10.1016/0095-8956(86)90084-5
P. Frankl and V. Rödl, Hypergraphs do not jump, Combinatorica 4 (1984), no. 2-3, 149–159. MR 771722, DOI 10.1007/BF02579215

On the Ramsey number of disjoint hyperedges

Charles H. Goldberg and Douglas B. West, Bisection of circle colorings, SIAM J. Algebraic Discrete Methods 6 (1985), no. 1, 93–106. MR 772181, DOI 10.1137/0606010
A. Hajnal and Bruce Rothschild, A generalization of the Erdős-Ko-Rado theorem on finite set systems, J. Combinatorial Theory Ser. A 15 (1973), 359–362. MR 325398, DOI 10.1016/0097-3165(73)90085-x
Gyula Katona, Tibor Nemetz, and Miklós Simonovits, On a problem of Turán in the theory of graphs, Mat. Lapok 15 (1964), 228–238 (Hungarian, with English and Russian summaries). MR 172263

Aufgabe 300

58

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
L. Lovász, Self-dual polytopes and the chromatic number of distance graphs on the sphere, Acta Sci. Math. (Szeged) 45 (1983), no. 1-4, 317–323. MR 708798

On an extremal problem in graph theory

48

On the theory of graphs

3