On subgraphs of $C_{2k}$-free graphs and a problem of Kühn and Osthus

Abstract

Let $c$ denote the largest constant such that every $C_6$-free graph $G$ contains a bipartite and $C_4$-free subgraph having $c$ fraction of edges of $G$. Győri et al. showed that $\frac{3}{8}\le c\le \frac{2}{5}$. We prove that $c=\frac{3}{8}$. More generally, we show that for any $\epsilon >0$, and any integer $k\ge 2$, there is a $C_{2k}$-free graph $G_1$ which does not contain a bipartite subgraph of girth greater than $2k$ with more than $\left(1-\frac{1}{2^{2k-2}}\right)\frac{2}{2k-1}(1+\epsilon )$ fraction of the edges of $G_1$. There also exists a $C_{2k}$-free graph $G_2$ which does not contain a bipartite and $C_4$-free subgraph with more than $\left(1-\frac{1}{2^{k-1}}\right)\frac{1}{k-1}(1+\epsilon )$ fraction of the edges of $G_2$. One of our proofs uses the following statement, which we prove using probabilistic ideas, generalizing a theorem of Erdős: For any $\epsilon >0$, and any integers $a$, $b$, $k\ge 2$, there exists an $a$-uniform hypergraph $H$ of girth greater than $k$ which does not contain any $b$-colorable subhypergraph with more than $\left(1-\frac{1}{b^{a-1}}\right)\left(1+\epsilon \right)$ fraction of the hyperedges of $H$. We also prove further generalizations of this theorem. In addition, we give a new and very short proof of a result of Kühn and Osthus, which states that every bipartite $C_{2k}$-free graph $G$ contains a $C_4$-free subgraph with at least $1/(k-1)$ fraction of the edges of $G$. We also answer a question of Kühn and Osthus about $C_{2k}$-free graphs obtained by pasting together $C_{2l}$'s (with $k>l\ge 3$).