The Connected Bipartite Turán Problem for Long Cycles and Paths
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_ | 1866909897820471296 |
|---|---|
| author | He, Zhen Salia, Nika Zhu, Xiutao |
| author_facet | He, Zhen Salia, Nika Zhu, Xiutao |
| contents | Caro, Patkós, and Tuza initiated a systematic study of the bipartite Turán number for trees, and in particular asked for the extremal number of edges in connected bipartite graphs with prescribed color-class sizes that contain no paths of given lengths. In this paper, we determine these numbers exactly and describe all corresponding extremal configurations. Our approach first establishes a more general result for long cycles: we determine the exact structure of all 2-connected bipartite graphs with no cycle of length at least a given constant. The proof combines Kopylov's method for long cycles with a strengthened version of Jackson's classical lemma, in which every extremal configuration is characterized.
To highlight the applicability of our results, we conclude with applications yielding concise proofs of classical theorems on bipartite Turán numbers, notably rederiving the results of Gyárfás, Rousseau, and Schelp for paths and Jackson for long cycles. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_07913 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Connected Bipartite Turán Problem for Long Cycles and Paths He, Zhen Salia, Nika Zhu, Xiutao Combinatorics Caro, Patkós, and Tuza initiated a systematic study of the bipartite Turán number for trees, and in particular asked for the extremal number of edges in connected bipartite graphs with prescribed color-class sizes that contain no paths of given lengths. In this paper, we determine these numbers exactly and describe all corresponding extremal configurations. Our approach first establishes a more general result for long cycles: we determine the exact structure of all 2-connected bipartite graphs with no cycle of length at least a given constant. The proof combines Kopylov's method for long cycles with a strengthened version of Jackson's classical lemma, in which every extremal configuration is characterized. To highlight the applicability of our results, we conclude with applications yielding concise proofs of classical theorems on bipartite Turán numbers, notably rederiving the results of Gyárfás, Rousseau, and Schelp for paths and Jackson for long cycles. |
| title | The Connected Bipartite Turán Problem for Long Cycles and Paths |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.07913 |