***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Huy Pham, Caltech and IAS

Thursday 6th February, 3:00 in Fine Hall 224.

Title: Independent sets in random Cayley graphs 

Abstract: Cayley graphs are an important and extensively studied class of graphs
with rich symmetries. Random Cayley graphs, constructed by choosing a generating
set at random in a fixed ambient finite group, provide an interesting and highly
challenging ensemble of random graphs. I will discuss several results and
surprises that arise in studying the independence number of random Cayley
graphs. 

In the dense regime where the density $p$ of the random Cayley graph is
constant, in joint work with David Conlon, Jacob Fox and Liana Yepremyan, we
determine a sharp upper bound for the independence numbers of dense random
Cayley graphs of general groups. Surprisingly, while this task is naturally
connected with some fundamental problems in additive combinatorics, our approach
to these problems is purely combinatorial. This approach also allows us to
resolve a fundamental question in additive combinatorics by Ruzsa, and make
progress on a conjecture of Alon on Ramsey Cayley graphs. 

The problem is significantly harder in the sparse regime of p. Alon showed
that the independence number is at most min( (n/p)^{1/2} , p^{-2} ) up to
logarithmic factors. We obtain a power improvement on this upper bound in a
large range of p, and as a corollary, an improved bound on a question of Ben
Green on the largest subset of {Z}_N which cannot be written as a
sumset. The key idea is the construction of an efficient cover for the
collection of sumsets of sets with small doubling. 

Finally, over prime cyclic groups, for density p at least (log N)^{-2+o(1)},
we show that the independence number of the random Cayley graph is
asymptotically the same as the Erdos-Renyi random graph at the same density.
This breaks over significant barriers in previous techniques and improves
earlier results of Green and Morris, and Campos, Dahia and Marciano. 
                                                                        
		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)