Videos

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

Presenter
May 23, 2014
Abstract
Boris Bukh Carnegie-Mellon University How many edges can an nn-vertex graph have without containing GG as a subgraph? If GG 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 K4,4K4,4-free graphs is possible. In this talk, I will explain what that means, and sketch a new construction of extremal Ks,tKs,t-free graphs for tt much larger than ss.