Counting flags in digraph

Thursday, September 24, 2009 -
2:30pm to 4:30pm
Many results in asymptotic extremal combinatorics are obtained using just a handful of instruments, such as induction and Cauchy-Schwarz inequality. The ingenuity lies in combining these tools in just the right way. Recently, Razborov developed a flag calculus which captures many of the available techniques in pure form, and allows one, in particular, to computerize the search for the right combination.In this talk we outline the general approach and describe its application to two problems in extremal digraph theory. We show that an $n$ vertex digraph with minimum outdegree $0.3465n$ contains a directed triangle, obtaining a new bound in an important special case of the Caccetta-Haggkvist conjecture. We also show that the maximum number of induced directed two-edge paths in an $n$ vertex digraph is $n3/15 + o(n3)$, resolving a conjecture of Thomasse.Based on joint work with Jan Hladky and Daniel Kral.
Speaker: 
Sergey Norin
Princeton University
Event Location: 
Fine Hall 224