Skip to main content
2 of 3
top-level tag
Ben Barber
  • 4.6k
  • 2
  • 25
  • 38

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

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}).$$ 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})$?
GMB
  • 1.4k
  • 9
  • 17