Turan number of cycles of length at most $2k$ for $k\geq 2$.

Question

Theorem (short even cycles)

For any integer $k\geq 2$, we have $\text{ex}(n,\{C_4,\dots,C_{2k}\})=O_k(n^{1+1/k}).$

Remark: $\text{ex}(n,\{C_4,\dots,C_{2k}\})$ is the maximal number of edges in the $n$-vertex graph which does not contains an even cycle of length at most $2k$.

To prove this theorem we need the following two technical lemmas.

Lemma 1 (Large bipartite subgraph)

Every $G$ has a bipartite subgraph with at least $e(G)/2$ edges.

Lemma 2 (Large average degree implies subgraph with large minimum degree)

Let $t>0$. Every graph with average degree $2t$ has a subgraph with minimum degree greater than $t$.

Proof of Theorem. Suppose that the graph $G$ is the maximizer, i.e. $\text{ex}(n,\{C_4,\dots,C_{2k}\})=e(G)$. Applying Lemma 1, we find a bipartite subgraph $G'$ of $G$ such that $e(G')\geq \dfrac{e(G)}{2}$. Now applying Lemma 2, we find a subgraph $G''$ of $G'$ such that $$\delta(G'')>\underbrace{\dfrac{d_{\text{ave}}(G')}{2}}_{=t}=\dfrac{e(G')}{\nu(G')}\geq\dfrac{e(G)}{2\nu(G)}.$$

Notice that $G''$ is a bipartite subgraph of $G'$ (and hence of $G$) with $\delta(G'')>t\geq\dfrac{e(G)}{2\nu(G)}$.

Let $u$ be an arbitrary vertex of $G''$. For each $i=0,1,\dots,k$, let $A_i$ denote the set of vertices at distance exactly $i$ from $u$.

For each $i=1,\dots,k-1$, every vertex of $A_i$ has:

• no neighbors in $A_i$ (or else $G''$ would not be bipartite),

• exactly one neighbor in $A_{i-1}$ (else we can backtrace through two neighbours which must converge at some point to form an even cycle of length at most $2k$),

• and thus $>t-1$ neighbors in $A_{i+1}$ (by the minimum degree assumption on $G''$).

Therefore, each layer $A_i$ expands to the next by a factor at least $t-1$. Hence $$\nu(G)\geq |A_k|\geq (t-1)^k\geq \left(\frac{e(G)}{2\nu(G)}-1\right)^k.$$ And thus $$e(G)\leq 2\nu(G)^{1+1/k}+2\nu(G).$$

I understand the idea of the proof but there are some technical moments which I did not understand:

Questions.

1. "every vertex of $A_i$ has no neighbors in $A_i$". Am I right that if this happens then we have an odd cycle in bipartite graph $G''$ which is absurd?

2. Here $A_1$ is basically the neighbors of $u$, i.e. $N(u)$ which exists because $|A_1|=\deg(u)\geq \delta(G'')>t>0$ and hence $|A_1|\geq 1$. But how do we know that $A_2,\dots, A_k$ exist? I think that it follows if $t>1$ but I cannot prove that $t>1$.

Thanks a lot!

Answer 1

First question. Yes: whenever there is an edge between $v,w \in A_i$, this creates an odd cycle. There is some largest $j<i$ (possibly $j=0$, possibly not) such that $v$ and $w$ have a common ancestor in $A_j$; going from $v$ back to that ancestor, forward to $w$, and then directly to $v$ is a cycle of length $2(i-j)+1$.

Second question. We cannot guarantee $t>1$ just from assuming that $G$ does not have an even cycle of length $2k$ or shorter. But remember: our goal is to prove that $G$ can't have too many edges, and having $t\le 1$ should help us with that.

If $t \le 1$, that means $G'$ has average degree at most $2t \le 2$, so $e(G') \le v(G')$, and therefore $e(G) \le 2 v(G)$. If $t>1$, you can proceed with your proof and obtain $e(G) \le 2v(G)^{1+1/k} + 2v(G)$. So the weaker of these two bounds, $e(G) \le 2v(G)^{1+1/k} + 2v(G)$, holds no matter what $t$ is.