Busca avançada
Ano de início
Entree
Conteúdo relacionado
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

THE MAXIMUM SIZE OF A NON-TRIVIAL INTERSECTING UNIFORM FAMILY THAT IS NOT A SUBFAMILY OF THE HILTON-MILNER FAMILY

Texto completo
Autor(es):
Han, Jie ; Kohayakawa, Yoshiharu
Número total de Autores: 2
Tipo de documento: Artigo Científico
Fonte: Proceedings of the American Mathematical Society; v. 145, n. 1, p. 73-87, JAN 2017.
Citações Web of Science: 4
Resumo

The celebrated Erdos-Ko-Rado theorem determines the maximum size of a k-uniform intersecting family. The Hilton-Milner theorem determines the maximum size of a k-uniform intersecting family that is not a subfamily of the so-called Erdos-Ko-Rado family. In turn, it is natural to ask what the maximum size of an intersecting k-uniform family that is neither a subfamily of the Erdos-Ko-Rado family nor of the Hilton-Milner family is. For k >= 4, this was solved (implicitly) in the same paper by Hilton-Milner in 1967. We give a different and simpler proof, based on the shifting method, which allows us to solve all cases k >= 3 and characterize all extremal families achieving the extremal value. (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 14/18641-5 - Circuitos Hamiltonianos e problemas de ladrilhamento em hipergrafos
Beneficiário:Jie Han
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 15/07869-8 - Emparelhamento perfeitos e ladrilhamentos em hipergrafos
Beneficiário:Jie Han
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
Processo FAPESP: 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat
Beneficiário:Jefferson Antonio Galves
Linha de fomento: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs