Let $k \geq 3 .$ Show that there exists a graph on $n$ vertices with $\Omega\left(n^{1+\frac{1}{k-1}}\right)$ many edges and no cycle of length $k$.

Question

Let $k \geq 3 .$ Show that there exists a graph on $n$ vertices with $\Omega\left(n^{1+\frac{1}{k-1}}\right)$ many edges and no cycle of length $k$.

I’d like to ask some questions about the following attempt, which is based on another, similar proof that I’ve read.

The idea is to consider a random graph on $n$ vertices. Normally, I’d try to make the expected number of cycles of length $k$ to be less than $1$, by choosing an appropriate edge probability. But in this case that would also lead to small expected number of edges (which we don’t like). So instead I’d choose a bigger $p$ (to be determined), allowing for some cycles of length $k$ to exist (say, about $n/2$ $k$-cycles) and also to get roughly $n^{1+\frac{1}{k-1}}$ edges. We then delete one vertex from each cycle, resulting in a $k$-cycle-free graph with vertex set of size of order $n$, and edge set of size of order $n^{1+\frac{1}{k-1}}$.

In particular, I choose $p = n^{\frac{1}{k+1} - 1}$. In $K_n$, the number of cycles of length $k$ is $\frac{n(n-1)\dots(n-k+1)}{2k} \leq \frac{n^k}{2k}$. Letting $X$ be the random variable counting the number of cycles of length $k$ in $G \sim G(n,p)$, we then have: $$\mathbb{E}[X]= (np)^k \leq n^{\frac{k}{k+1}}$$ By Markov’s inequality, we have: $$\mathbb{P}(X \geq n/2) \leq \frac{2\mathbb{E}[X]}{n} \leq 2 n^{\frac{k}{k+1} - 1} \to 0$$ So with positive probability, there exists a class of graphs $G’$ on $n$ vertices with less than $n/2$ cycles of length $k$. In each of those graphs, deleting a vertex from each of those cycles, we obtain a class of graphs $\tilde{G}$ with at least $n/2$ vertices and no cycles of length $k$.

Now the expected number of edges of those $\tilde{G}$ is ${{n/2} \choose 2}p \sim n^{1 + \frac{1}{k+1}}$, so there must exist a graph $G^\ast$ amongst those $\tilde{G}$ with that many edges. In particular, this implies $e(G^\ast) = \Omega\left(n^{1 + \frac{1}{k-1}}\right)$.

My questions are:

1. I toyed with different choices of $p$ for a bit, but couldn’t come up with a value that gives me exactly $\Omega\left(n^{1+\frac{1}{k-1}}\right)$ edges, but got $n^{1 + \frac{1}{k+1}}$ instead. I assume this is still ok?
2. As mentioned above, when deleting vertices, we must take care so that the remaining number of vertices is still of order $n$. This is represented in the expression $\mathbb{P}(X \geq n/2)$, which I must admit I lifted straight from the model proof. Would some value other than $n/2$ also work here, as long as it’s linear in $n$?

Answer 1

First, to answer the questions you actually asked:

• No, $n^{1 + \frac1{k+1}}$ is not good enough if you're aiming for $n^{1 + \frac1{k-1}}$. For example, when $k=3$, you are aiming for $n^{3/2}$ and only getting $n^{5/4}$.
• Yes, any expression linear in $n$ would work equally well.

However, I don't understand why you're deleting a vertex from every cycle. Instead, you could delete an edge from every cycle. This will work better, because you have way more edges to delete than vertices, so you can allow a higher $p$.

In $G(n,p)$, the expected number of edges is $\binom n2 p$, and the expected number of $k$-cycles is at most $\frac{(np)^k}{2k}$. So after we delete an edge from every cycle, the expected number of edges left is at least $\binom n2 p - \frac{(np)^k}{2k}$. (We might end up deleting the same edge many times, but this can only help us!)

Now try $p = n^{\frac1{k-1} - 1}$. Then $\binom n2 p$ is roughly $\frac12 n^{1+\frac1{k-1}}$, while $\frac{(np)^k}{2k} = \frac1{2k} n^{1 + \frac1{k-1}}$, so you're still left with $\Omega(n^{1 + \frac1{k-1}})$ edges in expectation. Therefore there must be an outcome in which we get at least this many edges.