Fred Holroyd's Talk

The Erdos-Ko-Rado Theorem for Graphs

Fred Holroyd The Open University

I shall report on work in progress, conducted jointly with John Talbot and Antony Johnson, on the question of extending the Erdos-Ko-Rado Theorem to independent sets of vertices of graphs.

We shall say that a graph G is r-EKR if the size of a family of pairwise intersecting independent vertex r-sets is maximised by choosing all those containing some particular vertex; it is strictly r-EKR if all the extremal families are of this type. If G = N_n (the null graph of order n), then the original EKR Theorem states that G is r-EKR if and only if n is at least 2r (and shortly thereafter it was shown that G is strictly r-EKR if n > 2r). Bollobas and Leader (1997) have extended this result to the case where G is the lexicographic product N_n[K_l], and Talbot (2002, unpublished) has shown that if G is a power of a cycle graph, then G is r-EKR for each r such that independent r-sets exist (and strictly so except when G = C_{2r+2}), thus settling a conjecture by Johnson and myself (1997).

After powers of cycles, life gets tough! One might expect vertex-transitivity to ensure the EKR property for all r for which independent sets exist (except for the null graphs), but this is false, and I shall present some quite pleasant counterexamples. A more convincing possibility is that if m(G) is the minimum size of a maximal independent set, then G should be EKR if m(G) is at least 2r. I shall describe reasons why it is plausible that this may be true. If it is, then it is in a sense 'best possible', as for any r > 1, the union of two copies of the complete bipartite graph K_{r,r} fails to be (r+1)-EKR (and, if r is odd, is r-EKR but not strictly so).

The Hilton-Milner Theorem does, however, provide an upper bound on the vertex order of a graph of maximum degree d that can fail to be r-EKR. This bound can be expressed as a polynomial of degree r - 1 in d.

The 'EKR analysis' of graphs that are unions of copies of a complete multipartite graph is already quite a non-trivial problem, and I shall discuss progress on this.