New constructions and bounds for nonabelian Sidon sets with applications to Turán-type problems

An $S_k$-set in a group $\mathrm{\Gamma }$ is a set $A\subseteq \mathrm{\Gamma }$ such that ${\alpha }_1\cdots {\alpha }_k={\beta }_1\cdots {\beta }_k$ with ${\alpha }_i,{\beta }_i\in A$ implies $({\alpha }_1,\dots ,{\alpha }_k)=({\beta }_1,\dots ,{\beta }_k)$. An $S_k^{\mathrm{\prime }}$-set is a set such that ${\alpha }_1{\beta }_1^{-1}\cdots {\alpha }_k{\beta }_k^{-1}=1$ implies that there exists $i$ such that ${\alpha }_i={\beta }_i\text{ or }{\beta }_i={\alpha }_{i+1}$. We give explicit constructions of large $S_k$-sets in the group $S_n$ and $S_2$-sets in $S_n\times S_n$ and $A_n\times A_n$. We give probabilistic constructions for `nice’ groups which obtain large $S_2$-sets in $A_n$ and $S_2^{\mathrm{\prime }}$-sets in $S_n$. We also give upper bounds on the size of $S_k$-sets in certain groups, improving the trivial bound by a constant multiplicative factor. We describe some connections between $S_k$-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.