Balanced supersaturation and Turan numbers in random graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911925274673152 |
|---|---|
| author | Jiang, Tao Longbrake, Sean |
| author_facet | Jiang, Tao Longbrake, Sean |
| contents | In a ground-breaking paper solving a conjecture of Erdős on the number of $n$-vertex graphs not containing a given even cycle, Morris and Saxton \cite{MS} made a broad conjecture on so-called balanced supersaturation property of a bipartite graph $H$. Ferber, McKinley, and Samotij \cite{FMS} established a weaker version of this conjecture and applied it to derive far-reaching results on the enumeration problem of $H$-free graphs.
In this paper, we show that Morris and Saxton's conjecture holds under a very mild assumption about $H$, which is widely believed to hold whenever $H$ contains a cycle. We then use our theorem to obtain enumeration results and general upper bounds on the Turán number of a bipartite $H$ in the random graph $G(n,p)$, the latter being first of its kind. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_10572 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Balanced supersaturation and Turan numbers in random graphs Jiang, Tao Longbrake, Sean Combinatorics 05C35, 05C80 In a ground-breaking paper solving a conjecture of Erdős on the number of $n$-vertex graphs not containing a given even cycle, Morris and Saxton \cite{MS} made a broad conjecture on so-called balanced supersaturation property of a bipartite graph $H$. Ferber, McKinley, and Samotij \cite{FMS} established a weaker version of this conjecture and applied it to derive far-reaching results on the enumeration problem of $H$-free graphs. In this paper, we show that Morris and Saxton's conjecture holds under a very mild assumption about $H$, which is widely believed to hold whenever $H$ contains a cycle. We then use our theorem to obtain enumeration results and general upper bounds on the Turán number of a bipartite $H$ in the random graph $G(n,p)$, the latter being first of its kind. |
| title | Balanced supersaturation and Turan numbers in random graphs |
| topic | Combinatorics 05C35, 05C80 |
| url | https://arxiv.org/abs/2208.10572 |