The Computer Science Colloquium

Alexander A. Razborov
(IAS and Steklov Mathematical Institute)

"Flag Algebras and Density of Triangles in Graphs"

Many standard techniques in asymptotic extremal combinatorics, and especially those that involve a non-negligible amount of counting, can be underlined by a rich structure of algebraic and analytical nature. The backbone of this structure is made by simply defined commutative algebras associated with the class of combinatorial objects in question. For at least three good reasons (to be discussed in the talk) it looks highly desirable to distill this theory (as well as accompanying "formal calculus"') in a pure and convenient form, and this is what we attempt to do.

Time permitting, we will also talk about the first application of these techniques to a concrete problem in the extremal combinatorics. More specifically, given the edge density $\rho$ of an undirected graph, what is the minimal possible density $g(\rho)$ of triangles in this graph? This question turned out to be surprisingly difficult; partial results toward it were proved by Goodman (59), Bollobas (75), Lovasz and Simonovits (83) and Fisher (89). We completely solve it for any value of $\rho$.

The Colloquium is supported by generous contributions from the Bloomberg, Information Builders, Inc., and Netlogic, Inc.