Largest subgraph from a hereditary property in a random graph

DOI10.1016/J.DISC.2023.113480zbMATH Open1516.05198arXiv2210.12754OpenAlexW4367308549MaRDI QIDQ6098071FDOQ6098071

Authors: Noga Alon, Michael Krivelevich, Wojciech Samotij 

Publication date: 12 June 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

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$.

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

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

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)

Cites Work

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

Cited In (4)

• Supersaturation for hereditary properties
• The structure of hereditary properties and colourings of random graphs
• The structure of hereditary properties and 2-coloured multigraphs
• Title not available (Why is that?)

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)