Georgia Institute of Technology College of Sciences

An $S_k$-set is a subset of a group whose $k$-tuples have distinct products. We give explicit constructions of large $S_k$-sets in the groups $\mathrm{Sym}(n)$ and $\mathrm{Alt}(n)$ and of large $S_2$-sets in $\mathrm{Sym}(n)\times\mathrm{Sym}(n)$ and $\mathrm{Alt}(n)\times\mathrm{Alt}(n)$, as well as some probabilistic constructions for 'nice' groups. We show that $k$ is even and $\Gamma$ has a normal abelian subgroup with bounded index then any $S_k$-set has size at most $(1-\varepsilon)|\Gamma|^{1/k}$. We describe some connections between $S_k$-sets and extremal graph theory. We determine up to a constant factor the largest possible minimum outdegree in a digraph with no subgraph in $\{C_{2,2},\ldots,C_{k,k}\}$, where $C_{\ell,\ell}$ is the orientation of $C_{2\ell}$ with two maximal directed $\ell$-paths. Contrasting with undirected cycles, the extremal minimum outdegree for $\{C_{2,2},\ldots,C_{k,k}\}$ is much smaller than that for any $C_{\ell,\ell}$. We count the directed Hamilton cycles in one of our constructions to improve the upper bound for a problem on Hamilton paths introduced by Cohen, Fachini, and Körner. Joint work with Michael Tait.