Hypergraphs with many Kneser colorings
Contribuinte(s) |
UNIVERSIDADE DE SÃO PAULO |
---|---|
Data(s) |
05/11/2013
05/11/2013
2012
|
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. 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) |
Identificador |
EUROPEAN JOURNAL OF COMBINATORICS, LONDON, v. 33, n. 5, Special Issue, supl. 1, Part 2, pp. 816-843, JUL, 2012 0195-6698 http://www.producao.usp.br/handle/BDPI/41218 10.1016/j.ejc.2011.09.025 |
Idioma(s) |
eng |
Publicador |
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD LONDON |
Relação |
EUROPEAN JOURNAL OF COMBINATORICS |
Direitos |
restrictedAccess Copyright ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD |
Palavras-Chave | #ASYMPTOTIC NUMBER #TRIPLE-SYSTEMS #EDGE COLORINGS #FINITE SETS #0-1 LAW #GRAPHS #SUBGRAPHS #THEOREMS #MATHEMATICS |
Tipo |
article original article publishedVersion |