# Reference for an “elementary” combinatorial fact

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.

• how do you order those $(i,j)$ for fixed $j-i$? – YCor Jan 11 '17 at 23:52
• @YCor Two transpositions with the same $j-i$ commute. – imakhlin Jan 11 '17 at 23:53
• $(1,2)$ and $(2,3)$? – YCor Jan 12 '17 at 0:00
• 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... – imakhlin Jan 12 '17 at 0:02
• 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. – Christian Stump Jan 12 '17 at 8:07