Largest subgraph from a hereditary property in a random graph

2022/10/23 by Noga Alon, Michael Krivelevich, Alon, Noga +3
Computer Science · Mathematics · #05C35 #05C80 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2210.12754

openalex publication_date 2022/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that for every non-trivial hereditary family of graphs \cal P and for every fixed p ∈ (0,1), the maximum possible number of edges in a subgraph of the random graph G(n,p) which belongs to \cal P is, with high probability, (1-(1)/(k-1)+o(1))pn \choose 2, where k is the minimum chromatic number of a graph that does not belong to \cal P.

Related

• Subgraphs of random graphs in hereditary families
• The largest subgraph without a forbidden induced subgraph
• Some extremal problems for hereditary properties of graphs
• The structure of almost all graphs in a hereditary property
• Supersaturation for hereditary properties