Sharp bounds for Duke--Erd s--R"odl problems on cycle-connected subgraphs
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality