Back to Search Start Over

Subgraphs of random graphs in hereditary families

Authors :
Clifton, Alexander
Liu, Hong
Mattos, Letícia
Zheng, Michael
Publication Year :
2024

Abstract

For a graph $G$ and a hereditary property $\mathcal{P}$, let $\text{ex}(G,\mathcal{P})$ denote the maximum number of edges of a subgraph of $G$ that belongs to $\mathcal{P}$. We prove that for every non-trivial hereditary property $\mathcal{P}$ such that $L \notin \mathcal{P}$ for some bipartite graph $L$ and for every fixed $p \in (0,1)$ we have \[\text{ex}(G(n,p),\mathcal{P}) \le n^{2-\varepsilon}\] with high probability, for some constant $\varepsilon = \varepsilon(\mathcal{P})>0$. This answers a question of Alon, Krivelevich and Samotij.<br />Comment: 5 pages

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2405.09486
Document Type :
Working Paper