Problem 64 — Visual explainer (undergrad)
=========================================

Problem statement
---------------
Does every finite graph with minimum degree at least 3 contain a cycle of length $2^k$ for some $k\geq 2$?

Picture
-------
Graph picture:

o---o
|\  |
| \ |
o---o    K4 is the complete graph on 4 vertices (all connections)

Question: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Context
-------
Area hint: infinite graph theory / Ramsey-type decompositions.

Benchmarks / known results (from comments)
----------------------------------------
- Conjectured by Erd\H{o}s and Gy\'{a}rf\'{a}s, who believed the answer must
  be negative, and in fact for every $r$ there must be a graph of minimum
  degree at least $r$ without a cycle of length $2^k$ for any $k\geq 2$.
- This was solved in the affirmative if the minimum degree is larger than some
  absolute constant by Liu and Montgomery (therefore disproving the above
  stronger conjecture of Erd\H{o}s and Gy\'{a}rf\'{a}s).
- Liu and Montgomery prove a much stronger result: if the average degree of
  $G$ is sufficiently large then there is some large integer $\ell$ such that
  for every even integer $m\in [(\log \ell)^8,\ell]$, $G$ contains a cycle of
  length $m$.
- An infinite tree with minimum degree $3$ shows that the answer is trivially
  false for infinite graphs.