# Long identity-free sequences of permutations

Let $N = [n]$ and for any subset $A \subseteq N$, let $S_A$ denote the subgroup of the symmetric group $S_n$ that fixes all objects outside $A$. Say that a sequence $A_1, \dots, A_k \subseteq N$ is "identity free" if the equivalence $$s_1 s_2 \dots s_k = \mathop{id} \qquad \text{where } s_i \in S_{A_i} \text{ for all } i$$ has no solutions, except for the trivial one where $s_1 = s_2 = \dots = s_k = \mathop{id}$.

Have these been studied under any name that I can search for? While I would be interested in any discussion at all, I am particularly interested in the question of the extremal length $L$ of the longest identity-free sequence when all $A_i$ are constrained to have some fixed size $\alpha$. The only upper bounds on $L$ I have been able to observe so far come from the easy observation that no two $A_i$ may overlap on more than one element (and then apply Cauchy-Schwarz).

Construct a bipartite graph $G$ where one part is $[n]$ and the other is $[k]$ such that there is an edge between $i\in[n]$ and $j\in[k]$ iff $i\in A_j$. Then $A_1, \dots, A_k$ are identity free if $G$ is acyclic. The converse may not hold though (as pointed out by Jan Kyncl).
If $|A_j|=\alpha>1$ for all $j\in[k]$, then $G$ has $\alpha k$ edges. In this case, $G$ may be acyclic only if $\alpha k \leq n+k-1$, i.e. $$k \leq \frac{n-1}{\alpha-1}.$$ This inequality does not have to hold if $G$ is not acyclic.
• I do not see why acyclicity is necessary. For example, $A_1=\{1,2\}, A_2=\{2,3\}, A_3=\{1,3\}$ is identity free but the graph $G$ is a six-cycle. – Jan Kyncl Aug 14 '17 at 21:50
• Thanks for the answer. It seems that this shows that any construction, where identity-freeness is certified by acyclic $A_i$'s, can only go up to $k \le \frac{n-1}{\alpha - 1}$. Definitely a nice observation. I've actually recently become aware of more complicated constructions with significantly higher $k$ than this (roughly $k \approx n^2 / \alpha^2$), so it looks like the acyclic argument isn't tight here. – GMB Aug 15 '17 at 21:32
• @GMB: But $n^2/\alpha^2$ is obviously the best you can get! Indeed, no two of the $A_i$ can have two elements in common; if $a,b\in A_[\cap A_j$, then you can take $s_i=s_j=(a,b)$ and $s_k=\mathop{\mathrm{id}}$ for $k\notin\{i,j\}$. This shows that $k{\alpha\choose 2}\leq {n\choose 2}$, or $k\leq \frac{n(n-1)}{\alpha(\alpha-1)}$. – Ilya Bogdanov Sep 23 '17 at 14:16
• @IlyaBogdanov Ahhh, shoot, you're right, I typoed earlier. The lower bound is actually $k = \Omega(n^2 / \alpha^3)$, and like you observed the upper bound is $k = O(n^2 / \alpha^2)$. That's the gap that I'm (still) trying to close. Thanks. – GMB Sep 24 '17 at 16:28