Largest subgraph from a hereditary property in a random graph

DOI10.1016/J.DISC.2023.113480MaRDI QIDQ6098071zbMATHOpenAlexFDO

Authors Noga Alon, Michael Krivelevich, Wojciech Samotij

Publication date 12 June 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.12754

zbMATH Keywords

random graphshereditary propertysubgraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial probability (60C05)

Abstract: We prove that for every non-trivial hereditary family of graphs $calP$ and for every fixed $pin(0,1)$, the maximum possible number of edges in a subgraph of the random graph $G(n,p)$ which belongs to $calP$ is, with high probability, ${\displaystyle }$ left(1-frac{1}{k-1}+o(1) ight)p{n choose 2}, ${\displaystyle }$ where $k$ is the minimum chromatic number of a graph that does not belong to $calP$.

Recommendations

• The structure of hereditary properties and colourings of random graphs
• Generalized chromatic numbers of random graphs
• Generalized Chromatic Numbers of Random Graphs
• The size of a maximum subgraph of the random graph with a given number of edges
• Extremal subgraphs of random graphs

Cites work

• A note on induced Ramsey numbers
• Combinatorial theorems in sparse random sets
• Extremal results for random discrete structures
• On the KŁR conjecture in random graphs
• Structured Codes of Graphs
• The probabilistic method
• What is the furthest graph from a hereditary property?

Cited in

(5)

• The size of a maximum subgraph of the random graph with a given number of edges
• The structure of hereditary properties and colourings of random graphs
• The structure of hereditary properties and 2-coloured multigraphs
• Supersaturation for hereditary properties
• scientific article; zbMATH DE number 3912417 (Why is no real title available?)

This page was built for publication: Largest subgraph from a hereditary property in a random graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098071)