순열의 wiring diagram과 사인파

가로 방향으로 놓여진 줄 총 $n$ 개가 평행하게 세로로 나열되어있는 상태를 생각한다. 여기서 맨 왼쪽의 줄 끝들에 차례대로 $1,2,\ldots, n$ 을 대응시킨다. 이 때 각 줄을 따라가서 오른쪽 끝에 도달하면 각각 시작지점에 대응되어있던 수를 써넣는다. 맨 처음 상태라면 각각 오른쪽으로 쭉 이동할 뿐이므로, 그 결과는 위에서 아래로 $1,2,\ldots, n$ 이 차례대로 나올 것이다. 여기에서 두 인접한 줄을 X자로 교차하도록 꼬는 시행을 한다고 생각한다. 예컨대 첫 번째 줄과 두 번째 줄을 꼬았다면, 맨 오른쪽의 수들은 이번엔 $2,1,3, \ldots, n$ 이 될 것이다. 이런 식으로 X자로 교차하는 시행을 몇 차례 하다보면 오른쪽은 1에서 $n$ 까지가 뒤섞인 결과, 즉 순열이 된다.

Source: https://arxiv.org/pdf/1802.08934.pdf

편의상 어느 시점에서 위에서부터 $i$ 번째 줄과 $i+1$ 번째 줄 둘을 꼬는 것을 $s_i$ 라 한다. 위의 예시의 경우, $s_2, s_3, s_1, s_2, s_1, s_3$ 을 통해 최종적으로 순열 4,3,2,1을 얻는다.

만약 오른쪽에 나올 순열을 고정시켰다면, 그 순열이 나오도록 X자로 꼬는 시행을 할 수 있을까? 이것은 왼쪽의 $i$ 와 오른쪽의 $i$ 에 해당하는 위치에 대해 줄을 잡아당겨 팽팽하게 만들면 $n$ 개의 선분들이 나타나는데, 거기서 등장하는 교점들을 “잘” 처리해주면 위와 같이 $s_i$ 들로 그 순열을 표현할 수 있다는 것으로부터 가능함을 확인할 수 있다. (여기서 “잘”이라 함은 3개 이상의 선분이 만나는 교점의 처리나, 두 교점 중 어느 것을 먼저 시행할 것인지의 선택 등에 따라 달라진다. 이는 교점 부근에서 국소적으로 선들을 움직여 교점을 풀어내거나, 위상적으로 변하지 않도록 서선들을 움직여 각각의 X자가 세로로 겹치지 않게 움직이는 것 등으로 해결한다)

이렇게 줄(wire)들을 이용해 순열을 표현하는 것을 wiring diagram이라 한다. 또한, 위와 같은 과정을 통해 만든 wiring diagram은 주어진 순열에 대해 최소한의 교차 횟수를 필요로 하게 된다. (이는 왼쪽에선 $i$ 가 $j$ 의 위쪽에 있지만 오른쪽에선 그 반대가 되는 쌍 $(i,j)$ 에 대해선 이 둘이 언젠가 반드시 교차하는 순간이 와야하기 때문에, 그 교차 횟수의 최솟값은 이러한 순서쌍의 개수가 되어야하고 위의 예시를 통해 만든 예가 정확히 그 교차 횟수를 갖는다) 순열 $w$ 에 대해 그 inv의 값은 $\text{inv}(w)$ 로 쓴다.

그러면 $\text{inv}(w)$ 가 최대가 되는 경우는 $n,n-1,\ldots,1$ 이 된다는 것을 알 수 있다. 그래서 이 특수한 순열 $w_0$ 를 longest permutation이라 부른다. 인접한 두 수의 치환 $s_i$ 들의 시행에 대해서는 많은 연구가 이루어져 있으며, 특히 $w_0$ 에 대한 wiring diagram에 대해서도 많은 결과들이 나와있기도 하다. 이 $w_0$ 의 $s_i$ 를 이용한 표현은 sorting network라고도 불리우며, Schubert calculus (Bruhat order, etc.)나 quasisymmetric function 등과 관련되어 있다.

[1]에서는 이 random sorting network의 limit theorem에 대해 다룬다. [2]에서 $n\rightarrow \infty$ 에서 높은 확률로 이 줄들의 모습이 uniform하게 사인파의 모습과 가까워진다는 가설이 세워졌었는데 이를 증명한 것.

Source: https://arxiv.org/abs/1802.08934

한 편, 이번에는 어떤걸 생각하냐면 위와 같은 sorting network에서 $s_i$ 를 시행할 때마다 순열이 update되는데, 그 과정의 모든 permutation matrix들을 보도록 한다. 그러면 그 그림은 아래와 같이 나타난다.

즉 이것은 Archimedean measure가 일차변환된 꼴로 나타나며, 그 정중앙에서는 support가 원형으로 등장하게 되는데, $n\rightarrow \infty$ 에 따라 그렇게 수렴된다는 것도 증명되었다. 어느 쪽도 생각지 못했던 모양이 나와서 다소 인상적이었음.

참고로 앞서 언급한 sorting network의 개수, 즉 $w_0$ 을 $n(n-1)/2$ 개의 $s_i$ 들의 합성으로 표현하는 경우의 수는

$\displaystyle \frac{\binom{n}{2}!}{1^{n-1}3^{n-2}5^{n-3} \cdots (2n-3)^1}$

이 된다.[3]

트윗 타래를 정리. (2018/05/21)

https://t.co/jbxud10HMI Random sorting networks에 대한 conjecture들이 증명됨 (Duncan, 2018)
— 유닼 (@udaqueness) May 21, 2018

References

[1] D. Dauvergne, “The Archimedean limit of random sorting networks” arXiv preprint arXiv:1802.08934, 2018.

[2] O. Angel, A. E. Holroyd, D. Romik, B. Virág, “Random sorting networks” Advances in Mathematics, 215(2):839-868, 2007. DOI: 10.1016/j.aim.2007.05.019

[3] R. Stanley, “On the number of reduced decompositions of elements of Coxeter groups” European Journal of Combinatorics, 5(4):359-372, 1984. DOI: 10.1016/S0195-6698(84)80039-6

월	화	수	목	금	토	일
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

References

이 글 공유하기:

이것이 좋아요:

관련

답글 남기기 응답 취소