For each $l\ge 3$, and $n ≥ 2^{l+2}$, there exists a graph, with $n$ vertices and no cycles of length $l$ or less, that has $\Omega(n^{1+ \frac{1}{l−1}} )$ edges.
Consider the random graph $G_{n,p}$, where $p \ge \frac{2}{n}$.Give a deterministic algorithm that returns a graph with the desired properties. Analyze the running time of your algorithm.
I know why the lower bound of edges, but I can't construct it.
What firstly in my mind, was greedy algorithm. As there was a two set, one set is connected, and the other is unknown. Guarantee the maximum edges in the connected set, and add vertex from the unknown to connected set one by one, with edges as much as possible. But I don't know whether it can work, I guess it can't.
Greatly appreciated!