An extremal problem for random graphs and the number of graphs with large even-girth (Q1280282): Difference between revisions

For given graphs \(G\), \(H\) denote by \(\text{ex}(G,H)\) the maximum number of edges an \(H\)-free subgraph of \(G\) may have. The paper estimates \(\text{ex}(G,H)\) in the case when \(H\) is a cycle of an even length and \(G\) is a random graph on \(n\) labelled vertices whose edges are independently present with probability \(p = p(n)\). The obtained results strengthen bounds of \textit{Z. Füredi} [Discrete Math. 126, No. 1-3, 407-410 (1994; Zbl 0792.05128)] and \textit{P. E. Haxell, Y. Kohayakawa}, and \textit{T. Luczak} [J. Comb. Theory, Ser. B 64, No. 2, 273-287 (1995; Zbl 0828.05056)]. To obtain the upper bound a technical lemma is proved concerning the number of certain graphs with large even-girth, i.e. without short even cycles, with a given number of vertices and edges, and satisfying a certain additional pseudorandom condition. To deduce the lower bound the result of Atai, Komlós, Pindr, Spencer, and Szemerédi on uncrowded hypergraphs is used as formulated in \textit{R. A. Duke, H. Lefmann} and \textit{V. Rödl} [Random Struct. Algorithms 6, No. 2-3, 209-212 (1995; Zbl 0822.05051)].