Hypergraphs with many Kneser colorings

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.

FAPERGS

FAPERGS [Proc. 11/1436-1]

FAPESP [Proc. 2007/56496-3]

FAPESP

CNPq

CNPq [Proc. 484154/2010-9, Proc. 308509/2007-2]

MaCLinC (University of Sao Paulo)

MaCLinC (University of Sao Paulo)