Subgraphs of random graphs in hereditary families

2024/05/15 by Alexander Clifton, Clifton, Alexander, Hong Liu +5
Mathematics · #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2405.09486

Abstract

For a graph G and a hereditary property P, let ex(G,P) denote the maximum number of edges of a subgraph of G that belongs to P. We prove that for every non-trivial hereditary property P such that L ∉ P for some bipartite graph L and for every fixed p ∈ (0,1) we have ex(G(n,p),P) ≤ n^2-ε with high probability, for some constant ε = ε(P)>0. This answers a question of Alon, Krivelevich and Samotij.

Related

• Largest subgraph from a hereditary property in a random graph
• The largest subgraph without a forbidden induced subgraph
• Some extremal problems for hereditary properties of graphs
• Supersaturation for hereditary properties
• The number of hypergraphs and colored Hypergraphs with hereditary properties