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

Speaker: John Byrne (U Delaware)

Thursday 20th November, 3:00 in Fine Hall 224.

Title: Nonabelian Sidon sets and extremal problems on digraphs

An Sk-set is a subset of a group whose k-tuples have distinct products. We
give explicit constructions of large Sk-sets in the groups Sym(n) and Alt(n)
and of large S2-sets in Sym(n) x Sym(n) and Alt(n) x Alt(n), as well as some
probabilistic constructions for 'nice' groups. We also give various upper
bounds; in particular, if k is even and the group has a normal abelian
subgroup with bounded index then the trivial upper bound can be improved by
some constant multiplicative factor. Next, we describe some connections
between Sk-sets and extremal graph theory. We determine up to a constant
factor the largest possible minimum outdegree in a digraph without certain
directed cycles. Interestingly, the extremal minimum outdegree is much larger
for any one of these cycles than for the whole family. We count the directed
Hamilton cycles in one of our constructions to improve the upper bound for a
problem on Hamilton paths posed by Cohen, Fachini, and Körner. This talk is
based on joint work with Michael Tait.

		----------------------------------

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