6
Sep
Title: Two applications of Szemeredi’s Regularity Lemma
Speaker: Oleg Pikhurko
When: September 6, 15:30-16:20pm
Where: Wean Hall, Room 5310
Abstract:
I will present two (short and unrelated) applications of Szemeredi’s Regularity Lemma.
In one (joint work with Benny Sudakov) we prove, for all large $n$, the conjecture of Lazebnik (1989) that among all graphs with n vertices and $m < n^2/4$ edges the maximum number of $3$-colorings is achieved by a semi-complete biparite graph.
Another application proves the conjecture of Aigner, Triesch, and Tuza (1995) that one can find an unknown acyclic orientation of any given graph of order $n$ by quering at most $(1/4+o(1))n^2$ edges.
