Bondy and Simonovits Proof for Small Graphs

Question

In their paper, Cycles of Even Length in Graphs (http://renyi.hu/~miki/BondySimEven.pdf), Bondy and Simonovits prove that if a graph $G^n$ has $n$ vertices and at least $100kn^{1+1/k}$ edges then $G^n$ contains a cycle $C^{2l}$ of length $2l$ for every integer $l \in [k, kn^{1/k}]$.

Does this proof let us say anything about small (about 100 vertices) graphs? Since an undirected graph can only have at most $\frac{n(n-1)}{2}$ vertices, the lower bound on the number edges of set by Bondy and Simonovits can never be reached for these small graphs. Is there an equivalent formulation that is relevant for this size of graph?

Answer 1

That particular theorem is a "for all large enough $n$..." type result so I don't think it says much for small $n$. I'm not sure what would count as an equivalent formulation but it is interesting to ask why it has the form it does and what can be said about "if there are enough edges then their are cycles of a range of sizes."

With less than $n$ edges there need not be any cycles. For a connected graph with $n$ edges there is one cycle but it could be any size. With $n+1$ edges there are two cycles at least and a cycle using no more than about half the vertices (two bigger cycles would share vertices and create a smaller cycle.)

A complete bipartite graph has about $\frac{n^2}4$ edges but no odd cycles which is why the focus is on even length cycles.

Consider a graph with $n=2k+1$ made of $k$ triangles with a common vertex. There are no even length cycles and $\frac32 n -\frac12$ edges.

With at least $\frac32n$ edges (i.e. average degree at least $3$) There must be a sub-graph which is a theta graph, three internally disjoint paths sharing endpoints, and hence some even length cycle.

A hexagonal grid rolled up into a torus is regular of degree $3$ with cycles of lengths $6,10,12$ but not $4$ or $8.$ However this is not that optimal.

For any $d$ and $c$ there are graphs with minimal cycle length $c$ and all vertices of degree $d$. The number of vertices, $n$ grows quickly though. So what can be said for $n \approx 100?$

There is a result I've seen several place, such as here that there are graphs with $\frac{n}4(1+\sqrt{4n-3})$ edges must have $4$ cycles. That is average degree about $10.4$ when $n=100.$ I'm not sure how sharp that is.

There is a graph on $50$ vertices regular of degree $7$ with no $4$-cycles. One can put two of those together sharing a vertex to get $n=99$ and average degree just over $7.$

A projective plane of order $7$ has $57$ points and the same number of lines. This gives a graph with $n=114$, regular of degree $8$ and minimum cycle length $6.$ The corresponding affine plane gives a subgraph with $n=105$ and average degree $7 \frac{7}{15}$.