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


Add event to Google
Add event to iCal