| Texto completo | |
| Autor(es): |
Kohayakawa‚ Y.
;
Kreuter‚ B.
;
Steger‚ A.
Número total de Autores: 3
|
| 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 |