Busca avançada
Ano de início
Entree
(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.)

A degree version of the Hilton-Milner theorem

Texto completo
Autor(es):
Frankl, Peter [1] ; Han, Jie [2] ; Huang, Hao [3] ; Zhao, Yi [4]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Alfred Renyi Inst Math, POB 127, H-1364 Budapest - Hungary
[2] Univ Sao Paulo, Inst Matemat & Estat, Rua Matao 1010, BR-05508090 Sao Paulo - Brazil
[3] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 - USA
[4] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 - USA
Número total de Afiliações: 4
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF COMBINATORIAL THEORY SERIES A; v. 155, p. 493-502, APR 2018.
Citações Web of Science: 3
Resumo

An intersecting family of sets is trivial if all of its members share a common element. Hilton and Milner proved a strong stability result for the celebrated Erdos-Ko-Rado theorem: when n > 2k, every non-trivial intersecting family of k-subsets of {[}n] has at most (n-1k-1) - (n-k-1 k-1) +1 members. One extremal family HMn,k consists of a k-set S and all k-subsets of {[}n] containing a fixed element x is an element of S and at least one element of S. We prove a degree version of the Hilton-Milner theorem: if n = Omega(k(2)) and F is a non-trivial intersecting family of k-subsets of {[}n], then delta(F) <= (HMn,k), where delta(F) denotes the minimum (vertex) degree of F. Our proof uses several fundamental results in extremal set theory, the concept of kernels, and a new variant of the Erdos-Ko-Rado theorem. (C) 2017 Elsevier Inc. All rights reserved. (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