Subgraphs of random graphs in hereditary families
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909204317470720 |
|---|---|
| author | Clifton, Alexander Liu, Hong Mattos, Letícia Zheng, Michael |
| author_facet | Clifton, Alexander Liu, Hong Mattos, Letícia Zheng, Michael |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_09486 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Subgraphs of random graphs in hereditary families Clifton, Alexander Liu, Hong Mattos, Letícia Zheng, Michael Combinatorics 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. |
| title | Subgraphs of random graphs in hereditary families |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.09486 |