Abstract

Algebraic constructions of K_{s,t}-free graphs

Boris Bukh
Carnegie-Mellon University

How many edges can an $n$-vertex graph have without containing $G$ as a subgraph? If $G$ is not bipartite, then the asymptotics is known, but for only a few bipartite graphs the humankind knows the answer. In all the resolved instances the construction is algebraic. It turns out that no real algebraic construction of extremal $K_{4,4}$-free graphs is possible.
In this talk, I will explain what that means, and sketch a new construction of extremal $K_{s,t}$-free graphs for $t$ much larger than $s$.