Supersaturation via edge-gluing
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917048760664064 |
|---|---|
| author | Jin, Zihao Longbrake, Sean Yepremyan, Liana |
| author_facet | Jin, Zihao Longbrake, Sean Yepremyan, Liana |
| contents | In 1984, Erdős and Simonovits conjectured the following: given a bipartite graph $H$, there exist constants $β, C > 0$ such that any graph $G$ on $n$ vertices and $pn^2\geq C \mathrm{ex}(n, H)$ edges contains at least $βn^{\mathrm{v}(H)} p^{\mathrm{e}(H)}$ copies of $H$. We show that edge-gluing preserves the satisfiability of this conjecture under some mild symmetry conditions. Namely, if two graphs $H_1$ and $H_2$ satisfy this conjecture, and if furthermore, gluing them along a fixed edge produces a unique graph then the resulting graph satisfies the conjecture as well.
In the same paper, Erdős and Simonovits conjectured a weaker statement: for every $H$, there is some $α, β, C > 0$ such that any graph $G$ on $n$ vertices and $pn^2\geq C n^{1+ α}$ edges contains at least $βn^{\mathrm{v}(H)} p^{\mathrm{e}(H)}$ copies of $H$. We show that if $H$ satisfies this conjecture then by gluing several copies of labeled $H$ along the same copy of a subforest of $H$ produces a graph that also satisfies the conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_16804 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Supersaturation via edge-gluing Jin, Zihao Longbrake, Sean Yepremyan, Liana Combinatorics 05C35 In 1984, Erdős and Simonovits conjectured the following: given a bipartite graph $H$, there exist constants $β, C > 0$ such that any graph $G$ on $n$ vertices and $pn^2\geq C \mathrm{ex}(n, H)$ edges contains at least $βn^{\mathrm{v}(H)} p^{\mathrm{e}(H)}$ copies of $H$. We show that edge-gluing preserves the satisfiability of this conjecture under some mild symmetry conditions. Namely, if two graphs $H_1$ and $H_2$ satisfy this conjecture, and if furthermore, gluing them along a fixed edge produces a unique graph then the resulting graph satisfies the conjecture as well. In the same paper, Erdős and Simonovits conjectured a weaker statement: for every $H$, there is some $α, β, C > 0$ such that any graph $G$ on $n$ vertices and $pn^2\geq C n^{1+ α}$ edges contains at least $βn^{\mathrm{v}(H)} p^{\mathrm{e}(H)}$ copies of $H$. We show that if $H$ satisfies this conjecture then by gluing several copies of labeled $H$ along the same copy of a subforest of $H$ produces a graph that also satisfies the conjecture. |
| title | Supersaturation via edge-gluing |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2507.16804 |