Directions to CSI

Documentation and Help


HPC Systems



Training and Tutorials

User Accounts

Register for a Workshop


Data Intensive Computing

Advanced Computational Methods

Accelerators in High Performance Computing and Computational Science


operated by the College of
Staten Island
and funded, in part, by
grants from the City of
New York, State of New
York, CUNY Research
Foundation, and National
Science Foundation
Grants CNS-0958379,
CNS-0855217 and
ACI 1126113

NSF Logo


Seminar on Machine Learning and Graphs, by Dr. Krzysztof Choromanski, Google Research Laboratory, New York, NY

Dr. Krzysztof Choromanski, Google Research Laboratory with give a seminar titled:
"The Erdos-Hajnal Conjecture and Combinatorial Clustering with Forbidden Patterns"

RESCHEDULED FOR: 2:30 PM on Tuesday, March 31, 2015, Lecture Hall, Building 1P, College of Staten Island.

This seminar is open to all CUNY faculty and students.


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.

Short 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.

After the seminar, Dr. Choromanski will give a short piano recital.