This is a question I've been meaning to ask for quite some time.

Fact. For $n\in\mathbb N$ consider the set of segments $R=\{[i,j], 1\le i<j\le n\}$. Let a subset $E\subset R$ be nice iff $E$ is closed under nonempty intersection, i.e. $$[i,j],[k,l]\in E\text{ and }[i,j]\cap[k,l]\neq\varnothing\implies [i,j]\cap[k,l]\in E.$$ Then there exist exactly $n!$ nice $E\subset R$.

Moreover, the map taking a nice $E$ to the product of transpositions $$\prod_{[i,j]\in E} (i,j)$$ (with the factors ordered by $j-i$ increasing from right to left) is a bijection from the set of nice subsets to the group of permutations.

This is, essentially, Lemmas 3.3 - 3.4 in this paper.

Question. Has anyone come across this fact (or even just the above set of "nice" configurations of segments) in their or someone else's work?

Update: comments on the construction. Note that $R$ only contains segments of positive length. In particular, this means that if for a nice $E$ we have $[i,j],[k,l]\in E$, then $j\neq k$. This, in turn, means that if we additionally have $j-i=l-k$, then the transpositions $(i,j)$ and $(k,l)$ commute and the order in which they appear in the product does not matter.

Also, a list of all the $n!$ nice $E$'s for $n=2,3$ can be found in the comments.

  • $\begingroup$ how do you order those $(i,j)$ for fixed $j-i$? $\endgroup$ – YCor Jan 11 '17 at 23:52
  • $\begingroup$ @YCor Two transpositions with the same $j-i$ commute. $\endgroup$ – imakhlin Jan 11 '17 at 23:53
  • $\begingroup$ $(1,2)$ and $(2,3)$? $\endgroup$ – YCor Jan 12 '17 at 0:00
  • $\begingroup$ OK, my bad, they commute if the corresponding segments are contained in a nice set. The intersection of two segments as in your example is not contained in $R$, hence... $\endgroup$ – imakhlin Jan 12 '17 at 0:02
  • 1
    $\begingroup$ This vaguely reminds me of arxiv.org/abs/1405.6904. I am not claiming any direct relation, but you might be interested having a look. $\endgroup$ – Christian Stump Jan 12 '17 at 8:07

Your Answer

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

Browse other questions tagged or ask your own question.