Category: Math

  • 그래프 이론 용어 우리말 번역

    그래프 이론에서 널리 사용되는 용어들을 우리 말로 번역하는 적절한 표준이 아직 없습니다. 10여년 전에 성균관대 이상구 교수님께서 제작한 “그래프이론 용어사전” 웹사이트가 있습니다만, matching이나 k-connected같은 현대적이고 널리 (제) 연구에 쓰이는 그래프이론 용어가 나오지 않습니다. 오죽하면, 2000년에 고 이창우 교수님이 Introduction to Combinatorics라는 책을 쓰셨는데, 서문을 읽어보면 한국어 용어를 몰라 영어를 잘 못하는데도 불구하고 영어로 책을 쓰게 되었다고 적혀있습니다. (저도 어쩌다보니 보게 된 책일 뿐, 그래프이론 공부를 위해서는 딱히 추천하는 책은 아닙니다.)

    content
    한국어 용어가 없어서 영어로 써버린 어느 책.

    KAIST에서는 수업을 영어로 하니 우리 말로 그래프 이론 용어를 강의할 일이 거의 없습니다. 가끔 대중강연이나 고등학생 상대 강연, 그리고 연구비 신청서를 쓸 때 우리 말로 그래프 이론 용어를 쓰게 되는데 그때마다 불편합니다.
    대한수학회 용어사전에서 matching을 ‘부합’으로 번역하였다며, 2014년 12월에는 위키피디아 한국어판에서 매칭이라는 용어를 모두 부합으로 바꿔버리는 황당한 일이 있었습니다. 가만히 있다가는 정말 엉뚱한 용어들이 등장할 것 같은 위기감에서 이 글을 씁니다.
    한편, 1990년대에만 해도 고등학교 교과과정에는 그래프이론이 전혀 등장하지 않았습니다. 하지만 2000년대 중반에 교과과정 개편을 통해 그래프이론이 살짝 나오는 것 같습니다. (하지만, 전공자인 제가 보기에는 고교에서 가르치는 주제의 선택이 그리 마음에 들지 않습니다. 고교 수준이라면  굳이 행렬의 n승과 인접행렬의 관계, 해밀턴 회로 같은 것은 다루지 말고, 수학적 귀납법 가르칠 때 수학적 귀납법의 응용으로 홀의 결혼정리나 그래프 채색 문제를 소개하는 것이 왜 그래프가 유용한지 더 설명하고 수학적 사고를 키우는 교육으로 좋다고 생각합니다.)
    고등학교에서 그래프 이론을 배우지 않은 연구자들이 배우고 나온 학생들과 대화하기 위해서는 고교에서 사용되는 용법을 아는 것도 필요하리라 생각합니다. 이 글에서는 같은 단어에 대해 어떻게 사용되고 있는지, 어떤 것이 좋을지 시간날 때마다 정리해볼까 합니다. ?가 붙어있는 번역은 저도 확신이 서지 않는 것이며, 괄호안에 적힌 것들은 그렇게도 사용된다는 뜻입니다. 굵은 글씨는 제가 추천하는 번역입니다.
    의견 환영합니다. 제가 고교교과서를 가지고 있지 않으므로 고교교과과정에 나오는 용어가 다른 것이 있다면 제보도 부탁드립니다.

    • 기본 용어
      • graph: 그래프
      • vertex: 꼭짓점 (꼭지점, 점)
        고등학교 교과서에서 꼭짓점으로 표현하고 있습니다.
      • edge:  (선)
        고등학교 교과서에서 으로 표현하고 있습니다.
      • degree: 차수 (고교 교과서에 나옵니다.)
      • complete graph: 완전그래프
        (어감으로는 완전 그래프보다는 꽉찬 그래프가 좋을 것 같긴 합니다.)
      • complete bipartite graph: 완전이분그래프
      • complement graph: 뒤집은 그래프?
      • loop: 고리? (루프)
      • line graph: 선그래프? 변그래프?
      • adjacency matrix: 인접행렬 (종속행렬)
        고교교과서에서 인접행렬이라고 부르고 있습니다.
      • incidence matrix: ?
      • hypergraph: 하이퍼그래프?
    • subgraph 관련
      • subgraph: 부분그래프
      • induced subgraph: 유도된 부분그래프? (유도부분그래프?)
      • spanning subgraph: 생성부분그래프?
        사실 왜 생성이라고 해야할지 알 수 없습니다.
      • minor: 마이너
      • contraction: 축약
      • deletion: 지우기
      • topological minor: 위상적 마이너?
    • tree 관련
      • tree: 수형도 (나무, 트리)
        고교 교과서에 수형도로 나오는 것 같습니다.
      • spanning tree: 생성수형도? (생성나무?)
        어떤 분 박사논문에서 신장트리라는 표현을 본 적도 있습니다. 수학사랑의 사전에서는 minimal spanning tree가 생성수형도라고 잘못 적혀있습니다. spanning tree는 모두 minimal하기 때문에 minimal이라는 단어는 그래프에서는 의미가 없고, 보통은 변에 어떤 값을 주었을 때 minimum spanning tree를 찾게 됩니다.
      • minimum spanning tree: 최소생성수형도
      • forest: 숲?
      • leaf: 잎?
    • 연결성 관련
      • path: 경로
      • trail: 트레일?
        안타깝게도 고교교과서에서는 trail을 경로로 번역하고 있습니다.
      • cycle: 회로 (싸이클)
      • circuit: 닫힌 트레일?
        안타깝게도 고교교과서에서는 circuit을 회로로 번역하고 있습니다.
      • walk: 보행?
      • connected graph: 연결된 그래프 (연결그래프?)
      • 2-connected graph: 이중연결된 그래프 
      • 3-connected graph: 삼중연결된 그래프
      • k-connected graph: k중연결된 그래프 (k-꼭짓점 연결 그래프)
        k-연결된 그래프는 어떨까 하는 생각도 듭니다만, 이중연결된 그래프, 삼중연결된 그래프라고 표현하면 이연결, 삼연결 그래프보다 훨씬 이해가 쉽지 않을까 합니다.
      • 2-edge-connected graph: 변으로 2중 연결된 그래프?
      • 3-edge-connected graph: 변으로 3중 연결된 그래프?
      • k-edge-connected graph: 변으로 k중 연결된 그래프? (k-변 연결 그래프)
        이것의 번역은 고민됩니다.
      • (connected) component: 연결성분? (연결부분?)
      • edge cut: 변 절단?
      • vertex cut: 꼭짓점 절단?
      • cut vertex: 절단 꼭짓점? (절단점?)
      • cycle space: 회로공간?
      • bond: 결합?
      • bond space: 결합공간?
    • matching 관련
      • matching: 짝맞추기 (매핑, 짝지우기)
        대한수학회 용어사전에서 부합이라고 번역해두어서 위키피디아에 부합이라고 하지만 아무도 그렇게 쓰는 사람을 본 적이 없습니다.
      • perfect matching: 완벽한 짝맞추기
    • 색칠 관련
      • perfect graph: 완벽한 그래프
      • bipartite graph: 이분그래프
      • chromatic number: 채색수 (색칠수?, 착색수?)
      • edge-chromatic number, chromatic index: 변채색수? (변착색수?)
        (어감이 별로 좋지 않네요. ㅠㅠ)
      • list chromatic number: 목록 채색수?
      • chromatic polynomial: 채색다항식
      • k-degenerate graph: k-퇴화 그래프?
      • nowhere-zero k-flow: 전혀 0이 없는 k-플로우?
    • 평면그래프 관련
      • dual graph: 쌍대 그래프?
      • planar graph: 평면 그래프
        plane graph와 planar graph의 정의가 다른데, 이 부분을 어떻게 처리할 지 고민입니다. 엄밀하게 하자면 plane graph를 평면그래프로, planar graph는 평면에 그릴 수 있는 그래프로 해야 맞겠지만, 여전히 만족스럽지 못합니다.
    • 분해 관련
      • ear decomposition: 귀 분해?
      • block decomposition: 블락 분해?
      • tree-decomposition: 수형도 분해?
      • path-decomposition: 경로 분해? 일자형 분해?
      • branch-decomposition: 가지 분해?
      • tree-width: ?
      • path-width: ?
      • branch-width: ?
      • clique-width?
      • tree-depth: ?
      • rank-width: ?
    • vertex-transitive graph: ?
  • KMO 여름학교/겨울학교 강의노트

    KMO 여름학교/겨울학교 강의노트

    KMO logo2008년부터 대한수학회 주최 한국수학올림피아드(KMO) 여름학교와 겨울학교에서 조합수학 분야 강의를 해왔습니다. 그 중 유인물을 나눠준 적이 몇 번 있는데 그것들을 여기에 공유하고자 합니다.

    • 2008년 제21기 겨울학교 (KAIST, 1월 7일-1월 22일) (유인물 없음)
    • 2008년 제18기 여름학교 유인물 (KAIST, 7월 28일-8월 8일)
      • 비둘기집의 원리와 램지 이론 / 수학적 귀납법 / 그래프이론
    • 2009년 제19기 여름학교 (배재대, 8월 4일-8월 13일) (유인물 없음)
    • 2010년 제23기 겨울학교 (한남대, 1월 6일-1월 21일) (유인물 없음)
    • 2010년 제20기 여름학교 (충남대, 8월 2일-8월 13일) (유인물 없음)
    • 2011년 제24기 겨울학교 (KAIST, 1월 6일-1월 21일) (유인물 없음)
    • 2011년 제21기 여름학교 유인물 (KAIST, 8월 1일-8월 12일)
      • 수학적 귀납법
    • 2012년 제25기 겨울학교 (KAIST, 1월 4일-1월 19일) (유인물 없음)
    • 2012년 제22기 여름학교 유인물 (충남대, 7월 26일-8월 7일)
      • 수학적 귀납법
    • 2013년 제26기 겨울학교 유인물 (KAIST, 1월 8일-1월 21일)
      • partial order, well-quasi-order, Dilworth 정리, antichain
    • 2014년 제23기 여름학교 (KAIST, 7월 23일-8월 1일) (유인물 없음)
    • 2015년 제28기 겨울학교 유인물 (KAIST, 1월 2일-1월 15일)
      • 확률론적 방법론
    • 2015년 제24기 여름학교 유인물 (KAIST, 8월 3일-14일)
      • 수학적 귀납법
    • 2016년 제29기 겨울학교 (KAIST, 1월 6일-19일) (유인물 없음)
    • 2016년 제25기 여름학교 (KAIST, 8월 1일-12일) (유인물 없음)
    • 2017년 제30기 겨울학교 (KAIST, 1월 4일-17일) (유인물 없음)
    • 2017년 제26기 여름학교 (KAIST, 7월 31일-8월 11일) (유인물 없음)
    • 2018년 제31기 겨울학교 (KAIST, 1월 3일-1월 16일) (유인물 없음)

    한편 1993년 1월에 있었던 제6기 한국수학올림피아드 겨울학교에 고등학생으로 참가하여 필기했던 노트도 공유합니다. 누락되거나 빠진 페이지가 있을 수 있습니다.

  • Dynamic survey on rank-width

    Note added on Jan. 2019: An improved version of this article has been published as a journal paper in Discrete Applied Mathematics.

    Dynamic survey on rank-width and related width parameters of graphs

    Sang-il Oum

    Aug 19, 2013

     

    This is an incomplete on-going survey on rank-width and its related parameters. I intend to expand it slowly.
    By no means, this will be complete.
    Please feel free to leave comments or give me suggestions.

     

    1  Definitions

    Rank-width was introduced by Oum and Seymour [35].
    Clique-width is defined and investigated first by Courcelle and Olariu [5] published in 2000, but the operations for clique-width has been introduced by Courcelle, Engelfriet, and Rozenberg [4] in 1993.
    NLC-width was introduced by Wanke [40] in 1994.
    Boolean-width was introduced by Bui-Xuan, Telle, and Vatshelle [2].

     

    2  Well-quasi-ordering

    Oum [31] proved that graphs of bounded rank-width are well-quasi-ordered under taking pivot-minors.
    This result has been generalized to

    1. skew-symmetric or symmetric matrices over a fixed finite field
      by Oum [34],

       
    2. σ-symmetric matrices over a fixed finite field by Kante [20].
       
     

    3  Forbidden vertex-minors

    Oum [29] showed that if a graph has rank-width k, then so is its vertex-minor.
    This, together with the well-quasi-ordering theorem [31] implies that
    for each k, there exists a list of finitely many graphs such that a graph has rank-width at most k if and only if none of its vertex-minors is isomorphic to a graph in the list.

     

    Oum [29] showed that for each k, the forbidden vertex-minor for rank-width at most k has at most (6k+1−1)/5 vertices.
    So in theory, we can enumerate all of them by an algorithm for fixed k.

     

    However, it is not clear how to find the list of forbidden vertex-minors
    for graphs of linear rank-width at most k,
    as there are no analogous upper bound on the size of forbidden vertex-minors. Jeong, Kwon, and Oum [16]
    showed that there are at least 3Ω(3k) forbidden vertex-minors for linear rank-width at most k.

     

    4  Hardness

    Computing rank-width is NP-hard. It can be easily deduced by combining the following known facts. This reduction is mentioned in [30].

    1. Seymour and Thomas [37] proved that computing branch-width is NP-hard.
      Kloks, Kratochvíl, and Müller [21] even showed that it is NP-hard to compute branch-width of interval graphs.

       
    2. Hicks and McMurray Jr. [13] and independently Mazoit and Thomassé [26] showed that if a graph G is not a forest, then the branch-width of the cycle matroid M(G) is equal to the branch-width of G.
       
    3. Oum [29] showed that the branch-width of a binary matroid is equal to the rank-width of its fundamental graph. Every graphic matroid is binary.
       

    It is not known to me whether computing linear rank-width is NP-hard.

     

    Computing clique-width is NP-hard, shown by Fellows, Rosamond, Rotics, and Szeider [8].

     

    Computing the relative clique-width is also NP-complete, shown by Müller and Urner [27]. The relative clique-width [24] is a clique-width restricted to a fixed decomposition tree.

     

    Gurski and Wanke [12] proved that computing NLC-width is
    also NP-hard via a reduction from the tree-width.

     

    5  Finding an approximate rank-decomposition for a fixed k

     

    Oum and Seymour [35] provided an algorithm to
    find a rank-decomposition of width at most 3k+1 or confirm that the input graph has rank-width bigger than k
    in time O(8k n9 logn).
    (Here, n is the number of vertices of the input graph.)
    The running time was later improved by Oum [30]
    to O(8k n4).

     

    This allows us to find a rank-decomposition of width at most c′ times rank-width
    if the rank-width is at most clogn in polynomial time.
    This is used in the quantum information theory (see Van den Nest, Dür, Vidal, and Briegel [38]) for their study on measurement-based quantum computation.

     

    If we do not mind having bigger function in k, then in the same paper [30], it is possible to find a rank-decomposition of width 3k−1 or
    confirm that the rank-width is bigger than k in time O(f(k)n3).

     

    We do not know whether there is an algorithm to find an approximate rank-decomposition of width O(k) in time O(c1k nc) for c ≤ 3
    when an input graph has rank-width at most k.

     

    These algorithms can be used as a tool to construct an expression for clique-width decomposition, which are essential in many algorithmic applications.

     

    6  Deciding rank-width at most k for fixed k

    There is a general algorithm of Oum and Seymour [36] which can construct a branch-decomposition of any symmetric submodular function in time O(n8k+c), and if we apply it to rank-width, we get an algorithm of running time O(n8k+12logn).
    Note that a simple general algorithm for path-width of any symmetric submodular function
    was developed by Nagamochi [28], which is applicable to linear rank-width in time O(n2k+4).

     

    Courcelle and Oum [6] first constructed an algorithm to decide, for fixed k, whether rank-width is at most k in time O(f(k)n3). But their algorithm uses the monadic second-order logic formula and does not provide an explicit rank-decomposition even if it exists.

     

    This problem was solved later.
    Hlinený and Oum [14] constructed an algorithm to decide whether rank-width is at most k
    and find a rank-decomposition of width at most k, if it exists, in time O(f(k)n3).
    Here, f(k) is growing very fast with k, because the algorithm uses the monadic second-order logic as well as the list of forbidden minors for branch-width at most k for matroids representable over a fixed finite field.
    Geelen, Gerards, Robertson, and Whittle [11] proved that the forbidden minors for matroids of branch-width at most k have at most (6k−1)/5 elements. This implies that we can construct an explicit algorithm for testing rank-width at most k and constructing a rank-decomposition of width at most k if it exists. (If there was no upper bound, then it may be impossible to enumerate all forbidden minors.)

     

    One can also decide whether the linear rank-width is at most k in time O(n3) by using the well-quasi-ordering theorem [31] and monadic second-order logic formula to test vertex-minors [6]. But it is not known how to find the list of forbidden vertex-minors.

     
     

    Wahlström [39] showed that deciding whether clique-width is at most k and finding a k-expression can be done in time O*((2k+1)n).

     

    Espelage, Gurski, and Wanke [7] constructed an algorithm to decide whether a graph has clique-width at most k for graphs of bounded tree-width.

     

    7  Relation to Tree-width

     

    Kante [19] showed that rank-width is at most 4k+2 if the tree-width is k.
    Later,
    Oum [32] showed that rank-width is at most k+1 if tree-width is k.
    In fact, it is shown that

    if G has branch-width k,
    then the incidence graph of G has rank-width k or k−1,
    unless k=0.
     

    Corneil and Rotics [3] showed that the clique-width is at most 3·2k−1 if the tree-width is k.
    Moreover, they proved that for each k, there is a graph G having tree-width k and clique-width at least 2k/2−1.
    This also implies that there are graphs having rank-width at most k+1 and clique-width at least 2k/2−1 for each k.

     

    Kwon and Oum [22] proved that every graph of rank-width k
    is a pivot-minor of a graph of tree-width at most 2k.
    They also proved that every graph of linear rank-width k is a pivot-minor of a graph of path-width k+1.
    In other words,
    a set I of graphs has bounded rank-width
    if and only if it is a set of pivot-minors of graphs of bounded tree-width.

     

    Fomin, Oum, and Thilikos [10] showed that when graphs are planar, or H-minor-free, then
    having bounded tree-width is equivalent to having bounded rank-width.
    For instance, if a graph G is planar and has rank-width k,
    then tree-width is at most 72k−2.
    If G of rank-width k
    has no Kr minor with r > 2, then tree-width is at most 2O(rloglogr)k.
    This is already proven in Courcelle and Olariu [5] without explicit bounds because they use logical tools.

     

    8  Exact Algorithms

    There are small number of papers dealing with computing exact value of rank-width or related width parameters.

     
    Width Parameter Running time Paper
    Rank-width O*(2n) Oum [33]
    Linear rank-width O*(2n) forklore (trivial)

    The running time to compute clique-width exactly seems open.

     

    Müller and Urner [27] proved that NLC-width can be computed in time O(3n n) for an n-vertex graph.
    When they gave a talk at GROW2007 about this result, they further claimed that clique-width can be computed in time O*(3n) by finding a polynomial-time algorithm to compute relative clique-width [24] but later Ruth Urner emailed me that there was a mistake.

     

    Branch-width of graphs can be computed in time O*((2√3)n), shown by Fomin, Mazoit, and Todinca [9].

     

    9  Random graphs

    Lee, Lee, and Oum [23] showed that asymptotically almost surely the Erdös-Rényi random graph G(n,p) has rank-width n/3−O(1) if p is a constant between 0 and 1.
    Furthermore, [1/(n)] << p ≤ [1/2], then the rank-width is [(n)/3]−o(n),
    and if p = c/n and c > 1, then rank-width is at least r n for some r = r(c).

     

    Since the clique-width is at least rank-width, this also gives a lower bound for clique-width.

     

    Adler, Bui-Xuan, Rabinovich, Renault, Telle, and Vatshelle [1] claimed that boolean-width of G(n,p) for fixed 0 < p < 1 is Θ(log2 n) asymptotically almost surely.

     
    Remark.
    Johansson [17] (also in his Ph.D. thesis
    [18]) claimed in a conference paper that NLC-width
    and clique-width of a random graph G(n,p) for a fixed 0 < p < 1 is
    Ω(n) almost surely. But we believe that the proof is incorrect.

     

    In 2009, Marecek [25] studied the rank-width
    of G(n,1/2), though I believe that the first version of his paper on
    arxiv1 is
    incorrect; Later versions have different proofs.

     

    10  Explicit graphs

    Jelínek [15] proved that an n×n grid has rank-width n−1.

     

    11  Software

    Philipp Klau Krause implemented a simple dynamic programming algorithm
    to compute the rank-width of a graph2.
    This software is now included in the open source mathematics software
    package called SAGE; see the
    manual3.

     

    Apparently Friedmanský wrote Master’s thesis on “implementation of
    optimization of a graph algorithm for computing rank-width”4 under the
    supervision of Robert Ganian.

     

    Acknowledgment

    I would like to thank careful readers who kindly emailed me
    suggestions for this survey.

    • August 2013: Jisu Jeong found a typo.
       
    • August 2013: Chiheon Kim pointed out a mistake on the statement
      on the consequence of a theorem by Corneil and Rotics.

       
    • July 2013: J. Marecek explained his paper on arxiv.
       
    • July 2013: F. Gurski provided a journal version of his paper
      with E. Wanke cited
      in the survey.

       
     
     

    References

    [1]
    Isolde Adler, Binh-Minh Bui-Xuan, Yuri Rabinovich, Gabriel Renault, Jan Arne
    Telle, and Martin Vatshelle.
    On the Boolean-width of a graph: structure and applications.
    In Graph-theoretic concepts in computer science, volume 6410 of
    Lecture Notes in Comput. Sci., pages 159-170. Springer, Berlin, 2010.
    doi:10.1007/978-3-642-16926-7_16.

     
    [2]
    Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle.
    Boolean-width of graphs.
    Theoret. Comput. Sci., 412(39):5187-5204, 2011.
    doi:10.1016/j.tcs.2011.05.022.

     
    [3]
    Derek G. Corneil and Udi Rotics.
    On the relationship between clique-width and treewidth.
    SIAM J. Comput., 34(4):825-847 (electronic), 2005.
    doi:10.1137/S0097539701385351.

     
    [4]
    Bruno Courcelle, Joost Engelfriet, and Grzegorz Rozenberg.
    Handle-rewriting hypergraph grammars.
    J. Comput. System Sci., 46(2):218-270, 1993.
    doi:10.1016/0022-0000(93)90004-G.

     
    [5]
    Bruno Courcelle and Stephan Olariu.
    Upper bounds to the clique width of graphs.
    Discrete Appl. Math., 101(1-3):77-114, 2000.
    doi:10.1016/S0166-218X(99)00184-5.

     
    [6]
    Bruno Courcelle and Sang-il Oum.
    Vertex-minors, monadic second-order logic, and a conjecture by
    Seese.
    J. Combin. Theory Ser. B, 97(1):91-126, 2007.
    doi:10.1016/j.jctb.2006.04.003.

     
    [7]
    Wolfgang Espelage, Frank Gurski, and Egon Wanke.
    Deciding clique-width for graphs of bounded tree-width.
    Journal of Graph Algorithms and Applications, 7(2):141-180,
    2003.

     
    [8]
    Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider.
    Clique-width is NP-complete.
    SIAM J. Discrete Math., 23(2):909-939, 2009.
    doi:10.1137/070687256.

     
    [9]
    Fedor Fomin, Frédéric Mazoit, and Ioan Todinca.
    Computing branchwidth via efficient triangulations and blocks.
    Discrete Appl. Math., 157(12):2726-2736, 2009.
    doi:10.1016/j.dam.2008.08.009.

     
    [10]
    Fedor V. Fomin, Sang-il Oum, and Dimitrios M. Thilikos.
    Rank-width and tree-width of H-minor-free graphs.
    European J. Combin., 31(7):1617-1628, 2010.
    doi:10.1016/j.ejc.2010.05.003.

     
    [11]
    James F. Geelen, A. M. H. Gerards, Neil Robertson, and Geoff Whittle.
    On the excluded minors for the matroids of branch-width k.
    J. Combin. Theory Ser. B, 88(2):261-265, 2003.

     
    [12]
    Frank Gurski and Egon Wanke.
    Line graphs of bounded clique-width.
    Discrete Math., 307(22):2734-2754, 2007.
    doi:10.1016/j.disc.2007.01.020.

     
    [13]
    Illya V. Hicks and Nolan B. McMurray Jr.
    The branchwidth of graphs and their cycle matroids.
    J. Combin. Theory Ser. B, 97(5):681-692, 2007.
    doi:10.1016/j.jctb.2006.12.007.

     
    [14]
    Petr Hlinený and Sang-il Oum.
    Finding branch-decompositions and rank-decompositions.
    SIAM J. Comput., 38(3):1012-1032, 2008.
    doi:10.1137/070685920.

     
    [15]
    Vít Jelínek.
    The rank-width of the square grid.
    Discrete Appl. Math., 158(7):841-850, 2010.
    doi:10.1016/j.dam.2009.02.007.

     
    [16]
    Jisu Jeong, O-joung Kwon, and Sang-il Oum.
    Excluded vertex-minors for graphs of linear rank-width at most k.
    In Natacha Portier and Thomas Wilke, editors, 30th International
    Symposium on Theoretical Aspects of Computer Science (STACS 2013)
    , volume 20
    of Leibniz International Proceedings in Informatics (LIPIcs), pages
    221-232, Kiel, Germany, 2013. Schloss Dagstuhl. Leibniz-Zent. Inform.
    URL: http://drops.dagstuhl.de/opus/volltexte/2013/3936, doi:10.4230/LIPIcs.STACS.2013.221.

     
    [17]
    Öjvind Johansson.
    Clique-decomposition, NLC-decomposition, and modular
    decomposition-relationships and results for random graphs.
    In Proceedings of the Twenty-ninth Southeastern International
    Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL,
    1998)
    , volume 132, pages 39-60, 1998.

     
    [18]
    Öjvind Johansson.
    Graph decomposition using node labels.
    PhD thesis, Royal Institute of Technology, 2001.

     
    [19]
    Mamadou Moustapha Kanté.
    Vertex-minor reductions can simulate edge contractions.
    Discrete Appl. Math., 155(17):2328-2340, 2007.
    doi:10.1016/j.dam.2007.06.011.

     
    [20]
    Mamadou Moustapha Kanté.
    Well-quasi-ordering of matrices under Schur complement and
    applications to directed graphs.
    European J. Combin., 33(8):1820-1841, 2012.
    doi:10.1016/j.ejc.2012.03.034.

     
    [21]
    Ton Kloks, Jan Kratochvíl, and Haiko Müller.
    Computing the branchwidth of interval graphs.
    Discrete Appl. Math., 145(2):266-275, 2005.
    doi:10.1016/j.dam.2004.01.015.

     
    [22]
    O-joung Kwon and Sang-il Oum.
    Graphs of small rank-width are pivot-minors of graphs of small
    tree-width.
    Discrete Appl. Math., 2013.
    doi:10.1016/j.dam.2013.01.007.

     
    [23]
    Choongbum Lee, Joonkyung Lee, and Sang-il Oum.
    Rank-width of random graphs.
    J. Graph Theory, 70(3):339-347, July/August 2012.
    doi:10.1002/jgt.20620.

     
    [24]
    Vadim Lozin and Dieter Rautenbach.
    The relative clique-width of a graph.
    J. Combin. Theory Ser. B, 97(5):846-858, 2007.
    doi:10.1016/j.jctb.2007.04.001.

     
    [25]
    Jakub Marecek.
    Some probabilistic results on width measures of graphs.
    Unpublished, 08 2009.
    arXiv:0908.1772v1.

     
    [26]
    Frédéric Mazoit and Stéphan Thomassé.
    Branchwidth of graphic matroids.
    In Anthony Hilton and John Talbot, editors, Surveys in
    Combinatorics 2007
    , volume 346 of London Math. Soc. Lecture Note Ser.,
    pages 275-286. Cambridge Univ. Press, Cambridge, 2007.

     
    [27]
    Haiko Müller and Ruth Urner.
    On a disparity between relative cliquewidth and relative NLC-width.
    Discrete Appl. Math., 158(7):828-840, 2010.
    doi:10.1016/j.dam.2009.06.024.

     
    [28]
    Hiroshi Nagamochi.
    Linear layouts in submodular systems.
    In Kun-Mao Chao, Tsan-sheng Hsu, and Der-Tsai Lee, editors,
    ISAAC ’12
    , volume 7676 of Lecture Notes in Comput. Sci., pages
    475-484. Springer Berlin Heidelberg, 2012.
    doi:10.1007/978-3-642-35261-4_50.

     
    [29]
    Sang-il Oum.
    Rank-width and vertex-minors.
    J. Combin. Theory Ser. B, 95(1):79-100, 2005.
    doi:10.1016/j.jctb.2005.03.003.

     
    [30]
    Sang-il Oum.
    Approximating rank-width and clique-width quickly.
    ACM Trans. Algorithms, 5(1):Art. 10, 20, 2008.
    doi:10.1145/1435375.1435385.

     
    [31]
    Sang-il Oum.
    Rank-width and well-quasi-ordering.
    SIAM J. Discrete Math., 22(2):666-682, 2008.
    doi:10.1137/050629616.

     
    [32]
    Sang-il Oum.
    Rank-width is less than or equal to branch-width.
    J. Graph Theory, 57(3):239-244, 2008.
    doi:10.1002/jgt.20280.

     
    [33]
    Sang-il Oum.
    Computing rank-width exactly.
    Inform. Process. Lett., 109(13):745-748, 2009.
    doi:10.1016/j.ipl.2009.03.018.

     
    [34]
    Sang-il Oum.
    Rank-width and well-quasi-ordering of skew-symmetric or symmetric
    matrices.
    Linear Algebra Appl., 436(7):2008-2036, 2012.
    doi:10.1016/j.laa.2011.09.027.

     
    [35]
    Sang-il Oum and Paul Seymour.
    Approximating clique-width and branch-width.
    J. Combin. Theory Ser. B, 96(4):514-528, 2006.
    doi:10.1016/j.jctb.2005.10.006.

     
    [36]
    Sang-il Oum and Paul Seymour.
    Testing branch-width.
    J. Combin. Theory Ser. B, 97(3):385-393, 2007.
    doi:10.1016/j.jctb.2006.06.006.

     
    [37]
    Paul Seymour and Robin Thomas.
    Call routing and the ratcatcher.
    Combinatorica, 14(2):217-241, 1994.
    doi:10.1007/BF01215352.

     
    [38]
    M. Van den Nest, W. Dür, G. Vidal, and H. J. Briegel.
    Classical simulation versus universality in measurement-based quantum
    computation.
    Phys. Rev. A, 75:012337, Jan 2007.
    doi:10.1103/PhysRevA.75.012337.

     
    [39]
    Magnus Wahlström.
    New plain-exponential time classes for graph homomorphism.
    Theory Comput. Syst., 49(2):273-282, 2011.
    doi:10.1007/s00224-010-9261-z.

     
    [40]
    Egon Wanke.
    k-NLC graphs and polynomial algorithms.
    Discrete Appl. Math., 54(2-3):251-266, 1994.
    doi:10.1016/0166-218X(94)90026-4.
     

    Footnotes:

     

    1https://arxiv.org/pdf/0908.1772v1.pdf

     

    2http://pholia.tdi.informatik.uni-frankfurt.de/~philipp/software/rw.shtml

     

    3http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/rankwidth.html

     

    4http://is.muni.cz/th/172614/fi_m/thesis.pdf

  • 올해 아벨상은 헝가리 수학자 세머레디(Szemerédi)교수

    올해 아벨상은 헝가리 수학자 세머레디(Szemerédi)교수

    Szemeredi1헝가리 출신 수학자  세머레디 교수(71)가 수학계의 노벨상이라고 할 수 있는 아벨상 2012년 수상자로 결정되었다. 아벨상은 수학자 아벨의 이름을 따서 노르웨이 왕실에서 매년 매우 큰 업적을 남긴 수학자에게 수여하는 상으로 6백만 노르웨이 크로네, 원화로 약 11억원의 상금이 있는 명예로운 상이며 2003년에 첫 상이 수여되었다. 2년후 서울에서 열릴 국제수학자대회(ICM)에서 수여되는 필즈상은 40세 이하의 수학자만 받을 수 있지만, 아벨상은 노벨상처럼 나이 제한이 없다.
    세머레디 교수의 전공분야는 이산수학 혹은 조합수학이라 불리는데, 특히 극단 조합론(Extremal Combinatorics) 분야를 많이 연구하였다. 수많은 공저자를 가진 수학자로 잘 알려진 에르디시의 영향으로 헝가리 수학자들이 전통적으로 강한 분야이다.
    200여편의 논문을 쓰고 아울러 70이 넘은 지금도 여전히 연구에 매진하는 세머레디 교수의 연구결과를 모두 소개하는 것은 매우 어렵다. 하지만 수학의 다른 분야에 비해 상대적으로 이산수학의 문제들은 풀기는 매우 어렵더라도 누구나 쉽게 이해할 수 있는 경우가 많다. 이 글에서는 세머레디의 가장 잘 알려지고 중요한 업적인 등차수열이 있을지에 관한 연구와 그 과정에서 파생되었으나 수많은 응용을 낳은 “규칙성 보조정리”라는 것에 관해 다루고자 한다.

    긴 등차수열 찾기

    3, 6, 9, 12, 15나 5, 8, 11, 14처럼 같은 수를 계속 더해서 나오는 수들을 나열한 것을 등차수열이라고 한다. 이제 철수와 영희가 다음과 같은 게임을 한다고 하자.

    1부터 15까지 수 중 1/3을 영희가 마음대로 뽑았을때  그 중에 3개의 서로 다른 수로 이루어진 등차수열이 있으면 철수가 이기고, 그러한 등차수열이 없으면 영희가 이긴다.

    예컨데 영희가 2, 4, 5, 8, 12를 뽑는다면 이 중에 4, 8, 12가 길이가 3인 등차수열이 되므로 영희가 지게 되지만, 1, 3, 6, 7, 10을 뽑는다면 여기에는 길이가 3인 등차수열이 없어서 철수가 이기게 된다. 어쨌든 이 경우 영희 입장에서는 1, 3, 6, 7, 10만 뽑기만 하면 이길 수 있으니 철수에게는 매우 불리한 게임이다.
    철수를 위해서 이번에는 15를 100정도의 큰 수로 바꿨다고 생각해보자. 이때는 철수가 이길 수 있을까? 100도 부족하다면 그보다 훨씬 더 큰 충분히 큰 수 N으로 바꾼다면 철수가 이길 수 있을까?
    영국의 수학자인 로스는 1953년에 N이 충분히 크다면 이 게임에서는 항상 철수가 이긴다는 것을 증명하였고, 이 업적으로 1958년에 필즈상을 받았다. 로스는 심지어 1/3 대신 1%든 0.001%든지 아무리 작은 비율로 게임을 만들더라도 N이 충분히 크기만 하다면 1부터 N까지 수 중에 그 비율의 수를 아무렇게나 뽑더라도 그 수 중에는 길이 3인 등차수열이 있어서 철수가 이기게 된다고 증명하였다.
    세머레디는 1975년, 이 로스의 결과에서 3을 10이든 10000이든 어떤 수로 바꿔도 N만 더 크게 잡으면 된다는 것을 증명하였다. 예를 들어 1부터 N까지 수 중에 0.1%를 어떻게 뽑든지간에 N이 충분히 크기만 하다면 길이가 100인 등차수열이 반드시 있다는 것이다.
    이 문제는 원래 헝가리의 두 수학자 에르디시와 튜란이 1936년에 물어본 것인데, 세머레디가 증명하기 전까지 무려 39년동안 미해결 문제로 남아있었다. 놀라운 점은 이 세머레디의 증명은 복잡하긴 해도 현대수학의 깊은 지식이 없이도 읽을 수 있을 정도의 기본적인 수학만 사용한다는 것이다.
    영국 캠브리지 대학의 그린 교수(35)와 미국 UCLA의 타오 교수(36)는 세머레디의 아이디어를 확장하여 2, 3, 5, 7, 11과 같은 소수들의 수열에는 원하는 길이의 등차수열이 항상 있다는 것을 증명하였다. 이 결과는 타오 교수가 2008년에 필즈상을 받을 때 언급된 중요한 업적 중 하나이다. 이처럼 세머레디의 결과는 현재까지도 많이 연구되고 다뤄지는 중요한 연구들의 시금석이 되었다.

    아무리 불규칙해보여도 충분히 크기만 하면 피할 수 없는 규칙이 있다

    숫자를 많이 모으기만 해도 원하는 길이의 등차수열이 항상 있다는 세머레디의 결과는 이산수학에서 알려진 다른 여러 결과들과 유사한 점들이 많다. 예를 들어 충분히 많은 점을 찍으면 그 점 중에 100개를 잘 뽑으면 그 점들로 만들어지는 100각형의 모든 내각이 180도보다 작게 만들수 있다거나, 충분히 숫자를 많이 나열하면 그 중에 점을 잘 뽑으면 숫자가 증가하거나 감소하는 숫자 10개짜리 수열을 만들수 있다거나 하는 식의 정리들은 20세기 초반부터 알려져있었다.
    세머레디의 다른 중요한 업적으로 흔히 “세머레디의 규칙성 보조정리”(regularity lemma)라고 불리는 것이 있다. 이것은 앞에 설명한 등차수열에 관한 결과를 증명하는데 사용된 것인데 이산수학, 정수론, 이론 전산 분야에 많은 파급 효과를 가지고 왔다.
    이산수학 특히 그래프이론에서 흔히 다루게 되는 그래프라는 것은 꼭지점들과 그 꼭지점을 잇는 선으로 구성된 수학적 대상인데, 그래프이론에서는 그 선이 어떻게 구부러지는지에 관심있는게 아니라 꼭지점 어느 것과 어느 것이 이어졌는지에만 관심을 갖는다. 예를 들어 수도권 지하철 노선도를 나타낼때 실제 역의 위치를 그대로 지도에 그리는게 아니라 지하철역을 점으로, 두 역이 지하철 노선에서 이웃하면 선으로 이은 방식으로 간단한 그림으로 표현한다. 이렇게 하여 역과 역의 연결관계를 손쉽게 파악할 수 있고 쉽게 갈아타는 역을 찾을 수 있다.
    세머레디의 규칙성 보조정리는 이러한 그래프에 관한 정리이다. 아주 대충 이 정리의 특수 경우를 설명하자면, 꼭지점이 충분히 많은 모든 그래프는 꼭지점들을 10가지 분류로 비슷한 크기로 잘 나누되, 서로 다른 분류에 속한 꼭지점들 사이에 있는 선의 수는 마치 두 분류 사이에 선이 생길 빈도를 미리 정해놓고 그 빈도에 맞게 주사위를 던져 선을 그은 것에서 많이 벗어나지 않는다는 식이다. 물론 10을 다른 숫자로 바꾸는 것도 가능하다. 이것을 이용하면 꼭지점 수가 충분히 큰 모든 그래프에 대해 대략의 구조가 항상 존재한다는 것을 알 수 있어서 이것을 이용하여 수많은 문제들이 해결되었다.
    이 규칙성 보조정리는 현재도 수많은 응용과 확장, 다양한 증명방법이 연구되고 있다. 특히 정답을 할 확률이 어떤 확률 이상이 되는 것이 보장된다는 식의 확률적 알고리듬을 만드는 연구에서 이 규칙성 보조정리가 중요하게 사용되고 있다.

    한국에서도 필즈상, 아벨상 수상자가 나오길 기원하며

    이번 아벨상 수상은 인구 천만명 정도의 헝가리 출신 수학자로는 2005년 랙스 교수에 이어 2번째 수상자이며 헝가리 신문들은 인터넷 뉴스에서 톱 뉴스로 다루었다고 한다. 헝가리의 수학적 전통은 매우 오래된 것으로, 백년 넘는 역사를 자랑하는 수학경시대회도 있고, 한때는 헝가리 공중파 TV에서 TV수학경시대회를 열어 중계방송을 하고, 최종 결선에 출연한 학생은 마치 연예 프로그램의 스타가 될 정도로 국가적 관심을 받았다고 한다. 헝가리 수학계에 큰 영향을 끼친 수학자 에르디시는 수학에 재능있는 영재들을 일찍부터 발굴하고 수학계로 이끌었는데, 그 중에 현재까지 수학계에 널리 알려진 대가들이 많다. 세머레디 역시 에르디시에 의해 재능이 발견된 학생이었다고 한다.
    인구 4천5백만인 한국에서는 아직 아벨상이나 필즈상 수상자가 나오지 않았다. 하지만 우리나라에서 수학이 제대로 교육되고 연구된 전통은 이제 고작 수십년밖에 안 된 것이고 최근들어 매구 급속도로 수학계가 발전하고 있으며, 이를 인정받아 국제수학자대회를 2014년 서울에서 개최하게 되는 등 추세를 볼때 앞으로 훌륭한 수학자들이 많이 탄생할 것으로 생각된다. 헝가리에 비해 늦게 시작하였지만 한국에서도 수학에 재능있는 많은 학생들이 발굴되고 육성되어 큰 발자취를 남기는 한국인 수학 대가들이 많이 탄생하기를 바란다.
    (2012.3. 한겨레 사이언스온에 투고)