A souvenir from Hungary (other's work)

A classical result of Paul Erdoes states that we always have two-colorability if m < 2^{n-1}. (You may try this on your own and either find the one-line proof or be amazed when seeing the solution).

Much later and with much effort, this bound was improved to m = O(n^{1/3} 2^n) and then m = O(n^{1/2-\epsilon} 2^n). Taking into account the simplicity of the problem, a moderately simple argument proving a bound better than Erdoes's was considered a high goal.

This problem was now solved in a very elegant manner by Andras Pluhar from Szeget. In the talk, I shall present the full proof. Again, you may try this on your own (aim for m = O(n^{1/4} 2^n) and a ten-line proof), but don't be disappointed if it doesn't work...