Edge-colorings of uniform hypergraphs avoiding monochromatic matchings

Autor(es)

Hoppen, Carlos ^[1] ; Kohayakawa, Yoshiharu ^[2] ; Lefmann, Hanno ^[3]

Afiliação do(s) autor(es)

^[1] Univ Fed Rio Grande do Sul, Inst Matemat, BR-91509900 Porto Alegre, RS - Brazil

^[2] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil

^[3] Tech Univ Chemnitz, Fac Informat, D-09107 Chemnitz - Germany

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS; v. 338, n. 2, p. 262-271, FEB 6 2015.
• Citações Web of Science: 3

Resumo

For positive integers k, l and r, and an r-uniform hypergraph H, let c(k,l,r) (H) be the number of k-colorings of the set of hyperedges of H with no l independent hyperedges of the same color. Let H-n,H-r denote the set of all n-vertex r-uniform hypergraphs and consider the function c(k,l,r) (n) = max [c(k,l,r)(H): H epsilon H-n,H-r], the maximum of C-k,C-l,C-r (H) over all r-uniform hypergraphs H on n vertices. In this paper, we determine, for all fixed values of r, k and l, and large n, the r-uniform n-vertex hypergraphs H with C-k,C-l,C-r (n) = C-k,C-l,C-r (H). (C) 2014 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat
• Beneficiário: Oswaldo Baffa Filho
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático