Sharp bounds for Duke--Erd s--R"odl problems on cycle-connected subgraphs

arXiv:2610.34307 · math.CO · Submitted 2026-10-25 · Read on arXiv

math.CO

Submitted: 2026-10-25

Updated: 2026-10-25

Comments: 13 pages

License: http://creativecommons.org/licenses/by-nc-sa/4.0/

The gist: For k at least2, 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.

Abstract

For k at least2, 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 β at least 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, n2-s)=(1/(2e)+o(1))n 3/s whenever s over n to infinity 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.

Related papers