Extremal results for odd cycles in sparse pseudorandom graphs

Autor(es)

Aigner-Horev, Elad ^[1] ; Han, Hiep ^[2] ; Schacht, Mathias ^[1]

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

^[1] Univ Hamburg, Fachbereich Math, D-20146 Hamburg - Germany

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

• Tipo de documento: Artigo Científico
• Fonte: COMBINATORICA; v. 34, n. 4, p. 379-406, AUG 2014.
• Citações Web of Science: 0

Resumo

We consider extremal problems for subgraphs of pseudorandom graphs. For graphs F and Gamma the generalized Turan density pi(F) (Gamma) denotes the relative density of a maximum subgraph of Gamma, which contains no copy of F. Extending classical Turan type results for odd cycles, we show that pi(F) (Gamma)=1/2 provided F is an odd cycle and Gamma is a sufficiently pseudorandom graph. In particular, for (n,d,lambda)-graphs Gamma, i.e., n-vertex, d-regular graphs with all non-trivial eigenvalues in the interval {[}-lambda,lambda], our result holds for odd cycles of length l, provided lambda(l-2)<< dl-1/nlog(n)(-(l-2)(l-3)). Up to the polylog-factor this verifies a conjecture of Krivelevich, Lee, and Sudakov. For triangles the condition is best possible and was proven previously by Sudakov, Szab, and Vu, who addressed the case when F is a complete graph. A construction of Alon and Kahale (based on an earlier construction of Alon for triangle-free (n,d;lambda)-graphs) shows that our assumption on Gamma is best possible up to the polylog-factor for every odd l >= 5. (AU)

• Processo FAPESP: 10/16526-3 - Hipergrafos quase-aleatórios e imersão de subhipergrafos geradores
• Beneficiário: Hiep Han
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado