An extremal problem for random graphs and the number of graphs with large even-girth
type: Item
instance of: scholarly article
title: An extremal problem for random graphs and the number of graphs with large even-girth
zbMATH Open document ID: 0910.05059
DOI: 10.1007/PL00009804
author: K. Appert
published in: Combinatorica
publication date: 1999-03-14T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 1261188
zbMATH Keywords: \(H\)-free subgraph
zbMATH Keywords: random graph
zbMATH Keywords: subgraph
zbMATH Keywords: even-girth
zbMATH Keywords: uncrowded hypergraph
Wikidata QID: Q97694922
reviewed by: Marie Demlová
MaRDI profile type: Publication
DBLP publication ID: journals/combinatorica/KohayakawaKS98
Recommended article: Extremal Results in Random Graphs
Recommended article: Q2934629
Recommended article: Turán's extremal problem in random graphs: Forbidding even cycles
Recommended article: Extremal problems for k-colour graphs and exact inequalities for pairs of random elements
Recommended article: Q4220195
Recommended article: On the size of a random maximal graph
Recommended article: Q5610919
Recommended article: Extremal subgraphs of random graphs
description: scientific article; zbMATH DE number 1261188