Nagy Zoltán Lóránt: The no-(k+1)-in-line problem

What is the maximum number of points that can be selected from an n × n square lattice such that no k + 1 of them are in a line? This has been asked more than 100 years ago for k = 2 and it remained wide open ever since. In this talk, we prove that the precise answer is kn, provided that k > C(n log n)^{1/2} for an absolute constant C. The proof relies on carefully constructed bi-uniform random bipartite graphs and concentration inequalities. During the talk, I highlight two different ways how the proof can be carried out - both approaches might be of independent interest for further applications. Finally, I mention some results concerning the case when k is rather small. 

Joint work with Benedek Kovács and Dávid R. Szabó