John Byrne, University of Delaware

Abstract

An Sk-set is a subset of a group whose k-tuples have distinct products. An Sk'-set is a subset of a group whose bipartite Cayley graph has no cycle of length 2k. We give explicit constructions of large Sk-sets in the symmetric and alternating groups and of S2-sets in direct powers of these groups. We give probabilistic constructions for 'nice' groups which obtain large S2'-sets in the symmetric group. We also give upper bounds on the size of Sk-sets in certain groups, improving the trivial bound by a constant multiplicative factor. We describe some connections between Sk-sets and extremal graph theory. In particular, we determine up to a constant factor the minimum outdegree of a digraph which guarantees even cycles with certain orientations. As applications, we improve the upper bound on Hamilton paths which pairwise create a two-part cycle of given length, and we show that a directed version of the Erdős-Simonovits compactness conjecture is false. This talk is based on joint work with Michael Tait.