순열의 wiring diagram과 사인파

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

편의상 어느 시점에서 위에서부터 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은 주어진 순열에 대해 최소한의 교차 횟수를 필요로 하게 된다. (이는 왼쪽에선 ij의 위쪽에 있지만 오른쪽에선 그 반대가 되는 쌍 (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_0s_i를 이용한 표현은 sorting network라고도 불리우며, Schubert calculus (Bruhat order, etc.)나 quasisymmetric function 등과 관련되어 있다.

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

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

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

참고로 앞서 언급한 sorting network의 개수, 즉 w_0n(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)

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

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중