AN EXTREMAL PROBLEM FOR RANDOM GRAPHS AND THE NUMBER OF GRAPHS WITH LARGE EVEN-GIRTH

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 Ha xell, Kohayakawa, and Luczak [13]. Two main tools are used here: the f irst one is an upper bound for the number of graphs with large even-gi rth, i.e., graphs without short even cycles, with a given number of ve rtices and edges, and satisfying a certain additional pseudorandom con dition; the second tool is the powerful result of Ajtai, Komlos, Pintz ;, Spencer, and Szemeredi [1] on uncrowded hypergraphs as given by Duk e, Lefmann, and Rodl [7].