×

Hypergraphs with many Kneser colorings. (English) Zbl 1239.05133

Summary: For fixed positive integers \(r\),\(k\) and \(\ell \) with \(1\leq \ell <r\) and an \(r\)-uniform hypergraph \(H\), let \(\kappa (H,k,\ell \)) denote the number of \(k\)-colorings of the set of hyperedges of \(H\) for which any two hyperedges in the same color class intersect in at least \(\ell \) elements. Consider the function \(KC(n,r,k,\ell)\)=max\(_{H\in {\mathcal H}_{n}}\mathcal K(H,k,\ell) \), where the maximum runs over the family \(\mathcal H_{n}\) of all \(r\)-uniform hypergraphs on \(n\) vertices.
In this paper, we determine the asymptotic behavior of the function \(KC(n,r,k,\ell)\) for every fixed \(r\), \(k\) and \(\ell \) and describe the extremal hypergraphs. This variant of a problem of Erdős and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the Erdős – Ko – Rado Theorem [P. Erdős, C. Ko and R. Rado [Q. J. Math., Oxf. II. Ser. 12, 313–320 (1961; Zbl 0100.01902)] on intersecting systems of sets.

MSC:

05C65 Hypergraphs
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory

Citations:

Zbl 0100.01902
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahlswede, R.; Khachatrian, L. H., The complete intersection theorem for systems of finite sets, European Journal of Combinatorics, 18, 2, 125-136 (1997) · Zbl 0869.05066
[2] Alon, N.; Balogh, J.; Keevash, P.; Sudakov, B., The number of edge colorings with no monochromatic cliques, Journal of the London Mathematical Society (2), 70, 2, 273-288 (2004) · Zbl 1060.05049
[3] Balogh, J.; Bollobás, B.; Simonovits, M., The number of graphs without forbidden subgraphs, Journal of Combinatorial Theory Series B, 91, 1, 1-24 (2004) · Zbl 1044.05044
[4] Balogh, J.; Bollobás, B.; Simonovits, M., The typical structure of graphs without given excluded subgraphs, Random Structures & Algorithms, 34, 3, 305-318 (2009) · Zbl 1227.05216
[5] Erdős, P., Some new applications of probabilistic methods to combinatorial analysis and graph theory, (Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic University, Boca Raton, Fl.). Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic University, Boca Raton, Fl.), Congressus Numerantium, vol. X (1974), Utilitas Mathematica: Utilitas Mathematica Winnipeg, Manitoba), 39-51
[6] Erdős, P.; Frankl, P.; Rödl, V., The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs and Combinatorics, 2, 113-121 (1986) · Zbl 0593.05038
[7] P. Erdős, D.J. Kleitman, B.L. Rothschild, Asymptotic enumeration of \(K_n\); P. Erdős, D.J. Kleitman, B.L. Rothschild, Asymptotic enumeration of \(K_n\)
[8] Erdős, P.; Ko, C.; Rado, R., Intersection theorems for systems of finite sets, Quarterly Journal of Mathematics, Oxford Series, 2, 12, 313-320 (1961) · Zbl 0100.01902
[9] Füredi, Z.; Simonovits, M., Triple systems not containing a Fano plane, Combinatorics, Probability & Computing, 14, 4, 467-484 (2005) · Zbl 1075.05062
[10] C. Hoppen, Y. Kohayakawa, H. Lefmann, Edge colorings of graphs avoiding monochromatic matchings of a given size, Combinatorics, Probability & Computing (in press).; C. Hoppen, Y. Kohayakawa, H. Lefmann, Edge colorings of graphs avoiding monochromatic matchings of a given size, Combinatorics, Probability & Computing (in press). · Zbl 1241.05054
[11] C. Hoppen, Y. Kohayakawa, H. Lefmann, An unstable extremal problem with a unique optimal solution (preprint).; C. Hoppen, Y. Kohayakawa, H. Lefmann, An unstable extremal problem with a unique optimal solution (preprint). · Zbl 1378.05147
[12] C. Hoppen, Y. Kohayakawa, H. Lefmann, Hypergraphs with many Kneser colorings (Extended version), ArXiv, 39 pp.; C. Hoppen, Y. Kohayakawa, H. Lefmann, Hypergraphs with many Kneser colorings (Extended version), ArXiv, 39 pp. · Zbl 1239.05133
[13] Keevash, P.; Sudakov, B., The Turán number of the Fano plane, Combinatorica, 25, 5, 561-574 (2005) · Zbl 1089.05074
[14] Kolaitis, Ph. G.; Prömel, H. J.; Rothschild, B. L., Asymptotic enumeration and a 0-1 law for \(m\)-clique free graphs, Bulletin of the American Mathematical Society (N. S.), 13, 2, 160-162 (1985) · Zbl 0584.05041
[15] Kolaitis, Ph. G.; Prömel, H. J.; Rothschild, B. L., \(K_{\ell + 1}\)-free graphs: asymptotic structure and a 0-1 law, Transactions of the American Mathematical Society, 303, 2, 637-671 (1987) · Zbl 0641.05025
[16] H. Lefmann, Y. Person, Exact results on the number of restricted edge colorings for some families of linear hypergraphs, (submitted for publication).; H. Lefmann, Y. Person, Exact results on the number of restricted edge colorings for some families of linear hypergraphs, (submitted for publication). · Zbl 1262.05082
[17] Lefmann, H.; Person, Y.; Rödl, V.; Schacht, M., On colorings of hypergraphs without monochromatic Fano planes, Combinatorics, Probability & Computing, 18, 803-818 (2009) · Zbl 1197.05053
[18] Lefmann, H.; Schacht, M.; Person, Y., A structural result for hypergraphs with many restricted edge colorings, Journal of Combinatorics, 1, 3-4, 441-475 (2010) · Zbl 1244.05160
[19] Lovász, L., Kneser’s conjecture, chromatic number, and homotopy, Journal of Combinatorial Theory Ser. A, 25, 319-324 (1978) · Zbl 0418.05028
[20] Nagle, B.; Rödl, V., The asymptotic number of triple systems not containing a fixed one, Discrete Mathematics, 235, 1-3, 271-290 (2001), Combinatorics, Prague 1998 · Zbl 0977.05018
[21] Nagle, B.; Rödl, V.; Schacht, M., Extremal hypergraph problems and the regularity method, (Topics in Discrete Mathematics. Topics in Discrete Mathematics, Algorithms and Combinatorics, vol. 26 (2006), Springer: Springer Berlin), 247-278 · Zbl 1116.05041
[22] O. Pikhurko, Z.B. Yilma, The maximum number of \(K_3 K_4\); O. Pikhurko, Z.B. Yilma, The maximum number of \(K_3 K_4\) · Zbl 1242.05135
[23] Simonovits, M., A method for solving extremal problems in graph theory, stability problems, (Theory of Graphs (Proc. Colloq., Tihany, 1966) (1968), Academic Press: Academic Press New York), 279-319
[24] Yuster, R., The number of edge colorings with no monochromatic triangle, Journal of Graph Theory, 21, 4, 441-452 (1996) · Zbl 0846.05026
[25] Ziegler, G. M., Generalized Kneser coloring theorems with combinatorial proofs, Inventiones Mathematicae, 147, 671-691 (2002) · Zbl 1029.05058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.