Skip to main content
Picture added
Source Link
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

I care only about linear term in the answer, relaxing an additive constant. However, for $n=12k+11$ I show the tight answer.

An example I told in a comment was slightly suboptimal. An optimal one is the following. Take a cycle of length $8k+7$, number its vertices from 1 to $8k+7$, and duplicate those with residues $2,3,6,7$ modulo 8. We get $n=12k+11$ vertices, so a shortest odd cycle has length of almost $2n/3$. See below an example for $k=0$.

Assume a shortest odd cycle has length more than $2n/3$. The cycle has no chords (otherwise we shorten the cycle), so each its vertex has a neighbor outside the cycle. Then three vertices have the same outer neighbor, which again leads easily to shortening the cycle (if $n$ is large).

Notice that exactly $2n/3$ is also impossible, as this number is even whenever integer.

I care only about linear term in the answer, relaxing an additive constant. However, for $n=12k+11$ I show the tight answer.

An example I told in a comment was slightly suboptimal. An optimal one is the following. Take a cycle of length $8k+7$, number its vertices from 1 to $8k+7$, and duplicate those with residues $2,3,6,7$ modulo 8. We get $n=12k+11$ vertices, so a shortest odd cycle has length of almost $2n/3$.

Assume a shortest odd cycle has length more than $2n/3$. The cycle has no chords (otherwise we shorten the cycle), so each its vertex has a neighbor outside the cycle. Then three vertices have the same outer neighbor, which again leads easily to shortening the cycle (if $n$ is large).

Notice that exactly $2n/3$ is also impossible, as this number is even whenever integer.

I care only about linear term in the answer, relaxing an additive constant. However, for $n=12k+11$ I show the tight answer.

An example I told in a comment was slightly suboptimal. An optimal one is the following. Take a cycle of length $8k+7$, number its vertices from 1 to $8k+7$, and duplicate those with residues $2,3,6,7$ modulo 8. We get $n=12k+11$ vertices, so a shortest odd cycle has length of almost $2n/3$. See below an example for $k=0$.

Assume a shortest odd cycle has length more than $2n/3$. The cycle has no chords (otherwise we shorten the cycle), so each its vertex has a neighbor outside the cycle. Then three vertices have the same outer neighbor, which again leads easily to shortening the cycle (if $n$ is large).

Notice that exactly $2n/3$ is also impossible, as this number is even whenever integer.

Source Link
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

I care only about linear term in the answer, relaxing an additive constant. However, for $n=12k+11$ I show the tight answer.

An example I told in a comment was slightly suboptimal. An optimal one is the following. Take a cycle of length $8k+7$, number its vertices from 1 to $8k+7$, and duplicate those with residues $2,3,6,7$ modulo 8. We get $n=12k+11$ vertices, so a shortest odd cycle has length of almost $2n/3$.

Assume a shortest odd cycle has length more than $2n/3$. The cycle has no chords (otherwise we shorten the cycle), so each its vertex has a neighbor outside the cycle. Then three vertices have the same outer neighbor, which again leads easily to shortening the cycle (if $n$ is large).

Notice that exactly $2n/3$ is also impossible, as this number is even whenever integer.