Algorithms, Combinatorics and Optimization Seminar

— 4:00pm

In Person - Wean Hall 8220

BORIS BUKH , Professor of Mathematics, Department of Mathematical Sciences, Carnegie Mellon University

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:

Add event to Google
Add event to iCal