Algorithms, Combinatorics and Optimization Seminar
— 4:00pm
Location:
In Person
-
Wean Hall 8220
Speaker:
BORIS BUKH
,
Professor of Mathematics, Department of Mathematical Sciences, Carnegie Mellon University
http://www.borisbukh.org/
Extremal graphs without exponentially-small bicliques
In 1954 Kővári, Sós and Turán showed that every $n$-vertex graph not containing $K_{s,t}$ has at most $O(n^{2-1/s})$ edges. We construct graphs matching this bound with $t\approx 9^s$, improving on factorial-type bounds. In this talk, I plan to give a high-level idea of the construction, and to share the sense of excitement by waving my hands a lot.
Event Website:
https://aco.math.cmu.edu/abs-22-23/apr27.html