Extremal density of a graph without a non-backtracking $2k$-cycle

Question

The current best bound for the maximum possible density of an $n$-node graph with girth (shortest cycle length) $>2k$ is of the form $$ex(n \ \mid \ C_{\le 2k}) = O(n^{1 + 1/k}),$$ while the current best bound for the maximum possible density of a graph without a $2k$-cycle is of the form $$ex(n \ \mid C_{2k}) = O(k \cdot n^{1 + 1/k}).$$ [Edit: this bound is actually wrong, see accepted answer below.] An "intermediate" question is the maximum possible density of a graph without a "non-backtracking $2k$-cycle," which we define as a circularly-ordered sequence of $2k$ nodes in which adjacent nodes are connected by an edge and there is no continuous subsequence of the form $(u, v, u)$. It is not hard to see that this function $ex(n \ \mid \ C^{\not \leftarrow}_{2k})$ lies between the above two, but:

1. Is $ex(n \ \mid \ C^{\not \leftarrow}_{2k})$ known to be asymptotically equivalent to either of these two functions?
2. (If not) is any upper bound on $ex(n \ \mid \ C^{\not \leftarrow}_{2k})$ known that is asymptotically better than $O(k \cdot n^{1 + 1/k})$?

Answer 1

The best bounds on $ex(n, C^{\not \leftarrow}_{2k})$ and on $ex(n, C_{2k})$ that we can prove with the current techniques are going to be basically same. Below I explain why.

First, contrary to what the question states the best known bound on the number of edges in $C_{2k}$-free graphs is $O(\sqrt{k}\log k\cdot n^{1+1/k})$, as proved in a paper of Jiang and myself.

In the appendix of that paper, we also show that this bound is almost the best one can obtain without improving the bound on $ex(n,C_{\leq 2k})$ itself. That construction also works for non-backtracking cycles. For completeness, I review the construction below.

For simplicity assume that $k$ is even. Consider bipartite version of the girth problem. Namely, we seek a $C_{\leq 2k}$-free bipartite graph whose parts have size $m$ and $n$. The same argument as in non-bipartite case shows that the number of edges in this case is at most $cn^{1/k}(mn)^{1/2}$ if $k$ is even. Let $m=n/k$ and suppose that this bound is tight, i.e., there is $C_{\leq 2k}$-free bipartite graph with parts $n/k$ and $n$ with $Ck^{-1/2}n^{1+1/k}$ edges. Replace each vertex in the smaller part by an independent set of size $k$ to get a graph $G$ with $Ck^{1/2}n^{1+1/k}$ edges. This graph contains no $C^{\not \leftarrow}_{2k}$ as the vertices of $C^{\not \leftarrow}_{2k}$ would induce a cycle length at most $2k$ in the original graph.

So, apart from the $\log k$ factor, no improvement is going to happen until we improve on the basic girth argument.

Answer 2

My upper bound is indeed correct and answers the question you wrote here (at least the upper-bound part), although my previous analysis was lacking in that it needed to account for floors and ceilings as we are dealing with integers. More precisely, it holds if $k$ is defined to be the largest integer such that the length of the smallest cycle is greater than $2k$ (as stated in your original question). Now, if $k$ were instead defined as the largest integer such that the length of the smallest cycle is at least (as opposed to strictly greater than) $2k$, it is indeed a different story. Is this what was really meant?

Let $D$ be such that $G$ has $(D+1)n$ edges where $n$ is the number of vertices. Then the average degree $D'$ of each vertex in $G$ is $2D+2$. You can use the link I posted to show that, letting $k' = \lfloor \frac{\log n}{\log(D)} \rfloor$, the length of the smallest cycle is no more than $2k'+2$, and is in fact no more than $2k'+1$ if $k'$ turns out to be exactly $\frac{\log n}{\log(D)}$.

So let $k$ be the largest integer such that the length of the smallest cycle is greater than $2k$. Then in either case $k$ must be no greater than $k'$ defined in the paragraph above. Thus, $k$ must satisfy $k \leq \frac{\log n}{\log(D)}$ (no ceiling functions needed) which implies that $\log(D)$ must satisfy $\log(D) \leq \frac{\log n}{k}$, which implies that $D$ must satisfy $D \leq n^{\frac{1}{k}}$, which implies that $D+1$ must satisfy $D+1\leq n^{\frac{1}{k}}+1$. So the average degree $D'$ of $G$ must satisfy $D'\leq 2n^{\frac{1}{k}}+2$.

Now, let $k$ be the largest integer such that the length of the smallest cycle is at least (as opposed to strictly greater than) $2k$. There my analysis (in the link I posted) guarantees only the slightly weaker inequality of $k \leq \lceil \frac{\log n}{\log(D)}\rceil$, which (for a range of values of $k$ relative to $n$) would allow $\log(D) -\frac{\log n}{k}$ to be large enough to allow $D$ to be much larger than $\theta(n^{\frac{1}{k}})$ and even $\theta(kn^{\frac{1}{k}})$.