Colloquium Details
The Erdos-Hajnal Conjecture and Combinatorial Clustering with Forbidden Patterns
Speaker: Krzysztof Choromanski, Google Research New York
Location: Warren Weaver Hall 1302
Date: November 21, 2014, 11:30 a.m.
Host: Joel Spencer
Synopsis:
The celebrated Erdos-Hajnal Conjecture is one of the most important open problems in modern Ramsey graph theory. In its undirected version it states that for every undirected graph H there exists ϵ(H)>0 such that every H-free n-vertex graph contains a clique or a stable set of order at least n^ϵ(H). In the equivalent directed version undirected graphs are replaced by tournaments and cliques/stable sets by transitive subtournaments. Thus the Conjecture predicts that (quite surprisingly) a strictly local property of not having a forbidden pattern implies a global property of containing a large well-organized substructure. In a truly random graph the largest clique/stable set/transitive set is of only logarithmic size. The Conjecture says that the non-randomness of graphs defined by forbidden patterns can be measured by the polynomial size of the induced clique/stable set in the undirected setting or transitive subtournament in the directed setting. In this talk I will describe the most recent results regarding the Conjecture. Furthermore I will show an intriguing connection between the Conjecture and the clustering problem. It turns out that the algorithmic tools used in the most recent proofs regarding special variants of the Conjecture can be very helpful to obtain good-quality graph clustering in both undirected and directed setting. They also help to identify communities in the social network graphs.
Speaker Bio:
Krzysztof Choromanski is a member of Google Research Group in New York. He works in different areas of machine learning and graph theory. Among his interests are: online non-parametric clustering, ranking algorithms, structural graph theory of networks defined by forbidden induced subgraphs, random graph theory, differential privacy. He was the first to prove the Erdos-Hajnal Conjecture for all tournaments on at most five vertices and to use the probabilistic method to give the best known upper bounds on the so-called Erdos-Hajnal coefficients of prime graphs. He was a member of the team of researchers who gave a complete characteristic of the tournaments satisfying the Conjecture in the strongest - linear sense. Together with Maria Chudnovsky and Paul Seymour he gave a complete structural theorem of tournaments satisfying the Conjecture in the pseudolinear sense and, as a consequence, proved that tournaments with this weird property exist. Krzysztof did his Ph.D in 2013 at Columbia University under the supervision of Professor Maria Chudnovsky (his Ph.D thesis was about the structural properties of graphs defined by forbidden patterns). He plays piano and is an avid salsa dancer.
Notes:
In-person attendance only available to those with active NYU ID cards.