An extremal problem for random graphs and the number of graphs with large even-girth

Autor(es)

Kohayakawa‚ Y. ; Kreuter‚ B. ; Steger‚ A.

• Tipo de documento: Artigo Científico
• Fonte: COMBINATORICA; v. 18, n. 1, p. 101-120, 1998.

Resumo

We study the maximal number of edges a C-2k-free subgraph of a random graph Gn,p may have, obtaining best possible results for a. range of p= p(n). Our estimates strengthen previous bounds of Furedi [12] and Haxell, Kohayakawa, and Luczak [13]. Two main tools are used here: the first one is an upper bound for the number of graphs with large even-girth, i.e., graphs without short even cycles, with a given number of vertices and edges, and satisfying a certain additional pseudorandom condition; the second tool is the powerful result of Ajtai, Komlos, Pintz;, Spencer, and Szemeredi [1] on uncrowded hypergraphs as given by Duke, Lefmann, and Rodl [7]. (AU)

• Processo FAPESP: 96/04505-2 - Aspectos estruturais e algorítmicos de objetos combinatórios
• Beneficiário: Yoshiharu Kohayakawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático