Hypergraphs with many Kneser colorings

Autor(es)

Hoppen, Carlos ; Kohayakawa, Yoshiharu ; Lefmann, Hanno

• Tipo de documento: Artigo Científico
• Fonte: EUROPEAN JOURNAL OF COMBINATORICS; v. 33, n. 5, p. 28-pg., 2012-07-01.

Resumo

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)

• Processo FAPESP: 07/56496-3 - A análise de estruturas discretas de grandes proporções
• Beneficiário: Carlos Hoppen
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado