Advanced search
Start date
Betweenand


Hypergraphs with many Kneser colorings

Full text
Author(s):
Hoppen, Carlos ; Kohayakawa, Yoshiharu ; Lefmann, Hanno
Total Authors: 3
Document type: Journal article
Source: EUROPEAN JOURNAL OF COMBINATORICS; v. 33, n. 5, p. 28-pg., 2012-07-01.
Abstract

For fixed positive integers r, k and E with 1 <= l < r and an r-uniform hypergraph H, let kappa(H, k, l) 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 l elements. Consider the function KC(n, r, k, l) = max(H epsilon Hn) kappa(H, k, l), where the maximum runs over the family 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, l) for every fixed r, k and l and describe the extremal hypergraphs. This variant of a problem of Erdos and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the Erdos-Ko-Rado Theorem (Erdos et al., 1961 [8]) on intersecting systems of sets. (C) 2011 Elsevier Ltd. All rights reserved. (AU)