On the Duke--Erdős--Rödl Problem at the One-Third Threshold

Abstract

Let $G$ be an $n$-vertex graph with $e(G)\ge n^2/k$. We prove a self-contained internal short-cycle core theorem at the threshold $k\le n^{1/3}$: the graph $G$ contains a subgraph $H_6$ with $\hat{I}\text{c◯}(n^2/k^3)$ edges in which every two distinct edges lie together on a cycle of length at most $6$ contained in $H_6$, and a subgraph $H_8$ with $\hat{I}\text{c◯}(n^2/k^2)$ edges in which every two distinct edges lie together on a cycle of length at most $8$ contained in $H_8$. In density notation $\ddot{I}=e(G)/n^2$, this gives internal cores of sizes $\hat{I}\text{c◯}(\ddot{I}{}^3{n}^2)$ and $\hat{I}\text{c◯}(\ddot{I}{}^2{n}^2)$ throughout the range $\ddot{I}\ge n^{-1/3}$. The $C_{\le 6}$ conclusion above is an edge-connected statement and does not impose the adjacent-edge $C_4$ condition appearing in the strongest Duke--Erdős--Rödl formulation. We also include two complementary results clarifying this distinction. First, under the ambient-witness convention, every graph with at least $n^2/k$ edges and $k=o(n^{1/2})$ contains $\hat{I}\text{c◯}(n^2/k^3)$ selected edges whose pairs are witnessed by ambient cycles of length at most $6$, with adjacent pairs witnessed by ambient $C_4$'s. Second, under the standard internal strong $C_6$ convention, for every fixed ${\hat{I}}^2\in [1/3,1/2)$ there is an infinite sequence of bipartite graphs $G$ with $n\to \infty$ and $e(G)=\hat{I}{˜}_{\hat{I}}^2(n^{2-{\hat{I}}^2})$ such that every internally strongly $C_6$-connected subgraph has only $O_{\hat{I}}^2(\ddot{I}(G{)}^3{n}^2/(\log n{)}^2)$ edges. The obstruction is a random cyclic shift-lift of $K_{q,q}$, together with an occupancy estimate excluding large aligned two-covers.

20 pages