Turannical hypergraphs

Autor(es)

Allen, Peter ^[1] ; Boettcher, Julia ^[1] ; Hladky, Jan ^{[2, 3]} ; Piguet, Diana ^[4]

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

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

^[2] Univ Warwick, Math Inst, Coventry CV4 7AL, W Midlands - England

^[3] Univ Warwick, DIMAP, Coventry CV4 7AL, W Midlands - England

^[4] Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands - England

• Tipo de documento: Artigo Científico
• Fonte: RANDOM STRUCTURES & ALGORITHMS; v. 42, n. 1, p. 29-58, JAN 2013.
• Citações Web of Science: 2

Resumo

This paper is motivated by the question of how global and dense restriction sets in results from extremal combinatorics can be replaced by less global and sparser ones. The result we consider here as an example is Turan's theorem, which deals with graphs G = ({[}n], E) such that no member of the restriction set R = (({[}n])(r)) induces a copy of K-r. Firstly, we examine what happens when this restriction set is replaced by R = [X is an element of (({[}n])(r)): X boolean AND {[}m] not equal empty set]. That is, we determine the maximal number of edges in an n-vertex such that no K-r hits a given vertex set. Secondly, we consider sparse random restriction sets. An r-uniform hypergraph R on vertex set {[}n] is called Turannical (respectively epsilon-Turannical), if for any graph G on {[}n] with more edges than the Turan number t(r)(n) (respectively (1+epsilon)t(r)(n)), no hyperedge of R induces a copy of K-r in G. We determine the thresholds for random r-uniform hypergraphs to be Turannical and to be epsilon-Turannical. Thirdly, we transfer this result to sparse random graphs, using techniques recently developed by Schacht {[}Extremal results for random discrete structures] to prove the Kohayakawa-Luczak-Rodl Conjecture on Turan's theorem in random graphs. (C) 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 29-58, 2013 (AU)

• Processo FAPESP: 09/17831-7 - Problemas de imersão e empacotamento em teoria extremal dos grafos
• Beneficiário: Julia Boettcher
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 10/09555-7 - Problemas estruturais, probabilísticos e de imersão em teoria extremal dos grafos
• Beneficiário: Peter David Allen
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado