그 유명한 WQO theorem

Theorem.(Robertson, Seymour) 그래프는 minor relation에 대해 well-quasi ordered되어있다.

Corollary. P가 minor closed graph property라면 input graph G가 P를 가지는 지 판별하는 O(n^3) 알고리즘이 존재한다.


아는사람은 알겠지만 Graph minors 라는 이름으로 Robertson과 Seymour가 논문을 계속 시리즈로 내고 있음

Graph minor 1이 1983년인데(https://doi.org/10.1016/0095-8956(83)90079-5) Graph minor 23이였나 22였나가 2010년에 나온걸로암

아무튼 이 시리즈 논문에서 20편인가 그쯤에서 그 이전까지의 결과들을 싸바싸바해서 증명한게 저 위에있는 정리임


quasi ordering은 partial ordering에서 a<=b, b<=a 이면 a=b 조건이 빠진 것을 말함

이런 quasi ordering이 well이라는 것은 무한히 많은 원소 x_1, x_2, ....이 있으면 x_i<=x_j인 i

동치조건으로 infinite antichain이랑 infinite (strict) descending sequence가 없는 것임


그래서 그래프가 minor에 WQO라는 사실로 뭘 알 수 있냐 할 수 있는데 여기서 나오는 사실이 만약 P가 minor closed property라면 finite set of graph G_1, ..., G_n이 있어서 G가 P를 가짐 iff G가 minor로 G_1, ..., G_n을 모두 안가짐

그래프가 planer인지랑 K_5랑 K_3,3을 minor로 안가지는 것이 필요충분이라는 사실을 아마 알텐데 이런게 다른거에서 성립한다는 말임

그리고 하나 더 알려진 사실이 H가 고정되어있으면 input G에 대해 G가 H를 minor로 가지는 지 O(n^3)에 계산이 가능함

그래서 저 corollary가 나옴

그래서 님들이 그래프를 클라인병에다가 구멍두개뚤린 도넛을 붙인 다양체에 그려보고 싶은 또라이같은 생각을 해도 어쨌거나 그걸 검사하는게 O(n^3)에 된다는 말임

물론 그 O(n^3)알고리즘이 뭔지는 모름 ^^(그냥 토러스에 하는게 적어도 12000개...로 알고있었는데 찾아보니 갱신되었네. 아무튼 적어도 17523개를 검사해야됨. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p16 Full list는 아직도 모름. 다행히도 토러스는 예쁜 알고리즘이 있긴 하지만)


나는 별로 안좋아하는 정린데 교수님이 좋아하시는거같음

끝