Problem 82

Erdős Problem #82: declared status 'open'. Formalized: yes. Let $F(n)$ be maximal such that every graph on $n$ vertices contains a regular induced subgraph on at least $F(n)$ vertices. Prove that $F(n)/\log n\to \infty$. Current best: It is known that $F(5)=3$ and $F(7)=4$. Prize: no. OEIS: A120414, A390256, A390257, A390919, A392636, A394400, A394462, A394539, A394563, A394564, A394573, A394574, A394930, A394933. Tags: graph theory.