6
$\begingroup$

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).

$\endgroup$
1

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
5
  • 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, 2017 at 21:50
  • $\begingroup$ @JanKyncl: Indeed, it's only sufficient. Thanks for pointing this out. I'll edit the answer. $\endgroup$ Aug 14, 2017 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, 2017 at 21:32
  • 2
    $\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$ Sep 23, 2017 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, 2017 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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