Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.12953 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915600831348736 |
|---|---|
| author | Dong, Zichao Gao, Jun Liu, Hong |
| author_facet | Dong, Zichao Gao, Jun Liu, Hong |
| contents | For graphs $H_1$ and $H_2$, if we glue them by identifying a given pair of vertices $u \in V(H_1)$ and $v \in V(H_2)$, what is the extremal number of the resulting graph $H_1^u \odot H_2^v$? In this paper, we study this problem and show that interestingly it is equivalent to an old question of Erdős and Simonovits on the Zarankiewicz problem. When $H_1, H_2$ are copies of a same bipartite graph $H$ and $u, v$ come from a same part, we prove that $\operatorname{ex}(n, H_1^u \odot H_2^v) = Θ\bigl( \operatorname{ex}(n, H) \bigr)$. As a corollary, we provide a short self-contained disproof of a conjecture of Erdős, which was recently disproved by Janzer. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12953 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bipartite Turán problems via graph gluing Dong, Zichao Gao, Jun Liu, Hong Combinatorics 05C35, 05D40 For graphs $H_1$ and $H_2$, if we glue them by identifying a given pair of vertices $u \in V(H_1)$ and $v \in V(H_2)$, what is the extremal number of the resulting graph $H_1^u \odot H_2^v$? In this paper, we study this problem and show that interestingly it is equivalent to an old question of Erdős and Simonovits on the Zarankiewicz problem. When $H_1, H_2$ are copies of a same bipartite graph $H$ and $u, v$ come from a same part, we prove that $\operatorname{ex}(n, H_1^u \odot H_2^v) = Θ\bigl( \operatorname{ex}(n, H) \bigr)$. As a corollary, we provide a short self-contained disproof of a conjecture of Erdős, which was recently disproved by Janzer. |
| title | Bipartite Turán problems via graph gluing |
| topic | Combinatorics 05C35, 05D40 |
| url | https://arxiv.org/abs/2501.12953 |