Peter Cameron's homepage

Welcome to my St Andrews homepage. Under construction This page is under construction (and probably always will be!)

I am a half-time Professor in the School of Mathematics and Statistics at the University of St Andrews, and an Emeritus Professor of Mathematics at Queen Mary, University of London.

Events

About me

On this site

Me

Elsewhere


School of Mathematics and Statistics
University of St Andrews
North Haugh
St Andrews, Fife KY16 9SS
SCOTLAND
Tel.: +44 (0)1334 463769
Fax: +44 (0)1334 46 3748
Email: pjc20(at)st-arthurs(dot)ac(dot)uk
  [oops – wrong saint!]





Page revised 27 June 2016

A problem

Let k be a positive integer, and I a subset of {0,…, k−1} such that neither I nor its complement is empty. For n ≥ 2k+1, let G(n,k,I) be the graph whose vertex set is the set of k-subsets of {1,…n}, two subsets joined if the cardinality of their intersection is in I.

Problem

Show that, with finitely many exceptions, G(n,k,I) has clique number and chromatic number equal if and only if there exists t < k such that

Remark The second bullet point above gives the divisibility conditions necessary for the existence of a Steiner system S(t,k,n). According to the recent result of Peter Keevash, these conditions are also asymptotically sufficient. This fact will be relevant for the proof!

Old problems are kept here.