Computer Science/Discrete Mathematics Seminar II
On the Minimal Density of Triangles in Graphs (continued)
Given the edge density $\rho$ of an undirected graph, what is the minimal possible density $g(\rho)$ of triangles in this graph? This is the quantitative version of the classical Turan theorem (41) that in the asymptotical form can be re-stated as the inequality $g(\rho)>0$ for any $\rho>1/2$. 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 the question for any value of $\rho$. Our proof is the first application of a general methodology (based on the same underlying idea as the theory of graph homomorphisms by Lovasz, B. Szegedy et. all) that systematically reduces various techniques in extremal combinatorics to clean and intuitively clear computations in certain commutative algebras. In this talk we will try to illustrate both the abstract concepts underlying our framework and quite concrete computations (many of them MAPLE-based) performed therein.