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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Jan Kyncl Aug 14 '17 at 21:50
  • $\begingroup$ @JanKyncl: Indeed, it's only sufficient. Thanks for pointing this out. I'll edit the answer. $\endgroup$ – Max Alekseyev Aug 14 '17 at 22:53
  • $\begingroup$ 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. $\endgroup$ – GMB Aug 15 '17 at 21:32
  • 1
    $\begingroup$ @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)}$. $\endgroup$ – Ilya Bogdanov Sep 23 '17 at 14:16
  • $\begingroup$ @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. $\endgroup$ – GMB Sep 24 '17 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.