A bipartite version of the Erdős–McKay conjecture
Combinatorics Seminar
10th October 2023, 11:00 am – 12:00 pm
Fry Building, 2.04
A set of vertices in a graph is said to be 'homogeneous' if it is a clique or an independent set. An old conjecture of Erdős and McKay states that if all homogeneous sets in an n-vertex graph are of order at most O(log n), then the graph contains induced subgraphs of each size from {0,1,..., \Omega(n^2)}. We prove a bipartite analogue of this conjecture: if all balanced homogeneous sets in an n by n bipartite graph are of order at most O(log n), then the graph contains induced subgraphs of each size from {0,1,...,\Omega(n^2)}. Shortly after our work was completed, the Erdős-McKay conjecture was solved in a remarkable paper by Kwan et al, using a very different (and less combinatorial) approach. Based on joint work with Eoin Long (Birmingham).
Comments are closed.