Nagy Zoltán Lóránt: Resolving the no-(k+1)-in-line problem when k is not small

Kedves Résztvevők,

Idei utolsó szemináriumunk szokás szerint kicsit rövidebb lesz, hogy pizzával zárjuk a félévet.

Előadó: Nagy Zoltán Lóránt

Hely-idő: Dec 13 14:15, ELTE Déli tömb 3-607.

Cím: Resolving the no-(k+1)-in-line problem when k is not small.

Absztrakt:

What is the  maximum number of points that can be selected from an n × n lattice square 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 paper, we prove that the precise answer is $kn$, provided that $k>c\sqrt{n \log{n}}$ for an absolute constant c. The proof relies on carefully constructed bi-uniform random bipartite graphs and switching techniques.