Bernard Lidicky (UIUC): Flag Algebras and iterated blow-ups |
|
|
|
Csütörtök, 3. Július 2014, 14:30 - 15:30
|
|
Abstract. Flag Algebras is a recently developed method by Razborov with many applications in extremal combinatorics, discrete geometry, and number theory. Flag Algebras seems to work very well if the extremal construction is a blow-up of a small structure. However, if the extremal construction is an iterated blow-up, Flag Algebras still provide a bound, but the bound is not exact. Erdős and Sós proposed a problem of maximizing the number $F(n)$ of rainbow triangles in 3-edge-colored complete graphs on $n$ vertices. They conjectured that $F(n)=F(a)+F(b)+F(c)+F(d)+abc+abd+acd+bcd$, where $a+b+c+d=n$ and $a,b,c,d$ are as equal as possible and $F(0) = 0$. This is an example of a problem where the extremal construction is an iterated blow-up. In this talk we give an introduction to Flag Algebras and show that they can be combined with a stability argument that proves the conjectured recurrence by Erdős and Sós for sufficiently large $n$. |
Hely : Kalmár Intézet, Árpád tér, szemináriumi szoba |
Vissza
JEvents v3.1.8 Stable
Copyright © 2006-2013