For $k\ge2$, 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\H{o}s and R\"odl. First, Duke, Erd\H{o}s and R\"odl showed that $f_3(n,\lfloor n^{2-\beta}\rfloor)=\Theta(n^{2-3\beta})$ for every fixed $0<\beta<1/2$ and ask for the case of $\beta\ge 1/2$. We solve this problem in a stronger form by determining that the optimal range of $\beta$ is $(0,2/3]$. Second, we prove that $f_2(n,\binom n2-s)=(1/(2e)+o(1))n^3/s$ whenever $\frac{s}{n}\to\infty$ and $s=o(n^2)$, determining the leading constant in an estimate of Duke, Erd\H{o}s, and R\"odl. 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.
For a graph $H$, let $f(n,e,H)$ be the least number of colors in an edge-coloring of some $n$-vertex graph with at least $e$ edges in which every copy of $H$ is rainbow. Burr, Erd\H{o}s, Graham, and S\'os conjectured that $f(n,\lfloor n^2/4\rfloor+1,C_{2k+1})=(1/8+o(1))n^2$ for every fixed $k\ge3$, and Buci\'c, Chen, a...
The Ramsey number $r_k(s,n)$ is the smallest integer $N$ such that every $N$-vertex $k$-graph contains either a copy of $K_s^{(k)}$ or an independent set of size $n$. Erd\H{o}s and Hajnal conjectured that for every fixed $s>k\ge 4$, one has $r_k(s,n)\ge \operatorname{twr}_{k-1}(\Omega(n))$. This conjecture was independ...
Long-Ma Du, Xin-Yu Hu, Rui-Long Liu et al.· 0 citations
The famous and actively studied problem of Brown--Erd\H{o}s--S\'os from 1973 asks for $f^{(r)}(n;s,k)$, the maximum number of edges in an $r$-graph with $n$ vertices in which no $s$ vertices span $k$ or more edges. In this paper, we concentrate on the case $r=3$ and $s=k+2$, with $k\ge2$ fixed and $n\to\infty$; then it...
Levente Bodnár, Oleg Pikhurko, Shu-Min Sun et al.· 0 citations
For a graph $H$, the suspension $\widehat H$ of $H$ is a graph obtained from $H$ by joining a new vertex to every vertex of $H$. The generalized Tur\'an number $\textrm{ex}(n,K_3,\widehat H)$ is the maximum number of triangles in an $n$-vertex $\widehat H$-free graph. For fixed $k \ge 4$, Mubayi and Mukherjee conjectur...
The Brown--Erd\H{o}s--S\'os problem is a fundamental problem in sparse hypergraph Tur\'an theory. For integers $r,k\ge 2$ and $s\ge r$, the problem asks for the maximum number $f^{(r)}(n;s,k)$ of edges in an $n$-vertex $r$-uniform hypergraph containing no $k$ distinct edges spanning at most $s$ vertices. In 1971, Brown...
For graphs $H$ and $F$, let $\text{ex}(n,H,F)$ denote the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. Gerbner, Gy\H{o}ri, Methuku, and Vizer proved that $\text{ex}(n,C_{2\ell},C_{2k})=\Theta(n^\ell)$ for $k>\ell\ge2$. They determined the leading term for $\ell=2$, but for $k>\ell\ge3$ their general...
Zhen Liu, Chuan-Shu Wu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
