Sharp bounds for Duke--Erdős--Rödl problems on cycle-connected subgraphs
Abstract
For k≥2, a graph is C2k-connected if every two distinct edges lie together on an even cycle of length at most 2k in that graph. Let fk(n,m) be the largest number of edges in a C2k-connected subgraph that every n-vertex graph with m edges must contain. In this paper, we study two cycle-connected problems raised by Duke, Erdős and Rödl. First, Duke, Erdős and Rödl showed that f3(n,⌊ n2−β⌋)=Θ(n2−3β) for every fixed 0< β<1/2 and ask for the case of β≥ 1/2. We solve this problem in a stronger form by determining that the optimal range of β is (0,2/3]. Second, we prove that f2(n,binom n2−s)=(1/(2e)+o(1))n3/s whenever s/n→∞ and s=o(n2), determining the leading constant in an estimate of Duke, Erdős, and Rödl. The first result uses a finite-field construction and a count of three-edge paths. The second uses the known structure of C4-connected graphs and estimates for complete bipartite subgraphs in a random graph.
Related
- Sharp bounds and extremal structure of minimally strongly k-connected digraphs
- The spectral Erdős book theorem: sharp bounds and stability
- On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs
- Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs
- Contractable 2-connected subgraphs in minimally 3-connected graphs
BibTeX
@misc{gao2026sharp,
title = {{Sharp bounds for Duke--Erdős--Rödl problems on cycle-connected subgraphs}},
author = {Guorong Gao and Run Zhao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34307},
eprint = {2610.34307},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34307},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Sharp bounds for Duke--Erdős--Rödl problems on cycle-connected subgraphs
AU - Guorong Gao
AU - Run Zhao
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34307
UR - https://arxiv.org/abs/2610.34307
AB - For k≥2, a graph is C_2k-connected if every two distinct edges lie together on an even cycle of length at most 2k in that graph. Let f_k(n,m) be the largest number of edges in a C_2k-connected subgraph that every n-vertex graph with m edges must contain. In this paper, we study two cycle-connected problems raised by Duke, Erdős and Rödl. First, Duke, Erdős and Rödl showed that f_3(n,⌊ n^2−β⌋)=Θ(n^2−3β) for every fixed 0< β<1/2 and ask for the case of β≥ 1/2. We solve this problem in a stronger form by determining that the optimal range of β is (0,2/3]. Second, we prove that f_2(n,binom n2−s)=(1/(2e)+o(1))n^3/s whenever s/n→∞ and s=o(n^2), determining the leading constant in an estimate of Duke, Erdős, and Rödl. The first result uses a finite-field construction and a count of three-edge paths. The second uses the known structure of C_4-connected graphs and estimates for complete bipartite subgraphs in a random graph.
ER -