On subgraphs of C2k-free graphs

We show that for any ε>0, and any integer k≥2, there is a C2k-free graph G which does not contain a bipartite subgraph of girth greater than 2k with more than (1−122k−2)22k−1(1+ε) fraction of the edges of G. Győri et al. showed that if c denotes the largest constant such that every C6-free graph G contains a bipartite subgraph which is C4-free having c fraction of edges of G, then 38≤c≤25. Putting k = 3, our result implies that c=38.Our proof uses the following statement, which we prove using probabilistic ideas, generalizing a theorem of Erdős: For any ε>0, and any integers a,b,k≥2, there exists an a-uniform hypergraph H of girth greater than k which does not contain any b-colorable subhypergraph with more than (1−1ba−1)(1+ε) fraction of the hyperedges of H.Kühn and Osthus showed that every bipartite C2l-free graph G contains a C4-free subgraph with at least 1/(l−1) fraction of the edges of G. We give a new and simple proof of this result. In the same paper Kühn and Osthus also showed that a C2l-free graph which is obtained by pasting together C4's has average degree at most 16l and asked whether there exists a number d=d(l) such that every C2l-free graph which is obtained by pasting together C2k's has average degree at most d if l>k≥3 are given integers. We answer this question negatively.