Combinatorial structure and algorithm
 

조합적 구조 및 알고리듬

Core Researchers : Gi-Sang Cheon (천기상), Suh-Ryung Kim (김서령), Jeong Han Kim (김정한),

                              Jang Soo Kim (김장수)

   조합 및 그래프이론은 순수수학 그 자체뿐만 아니라 수학을 도구로 하는 다양한 학문 분야와의 활발한 연구로 그 중요성이 더욱 커지고 있다. 현재 또는 미래 인터넷을 설명할 수 있는 여러 가지 그래프 모델을 분류하기 위해서는 그 모델들을 상호 비교할 수 있어야 한다. 인터넷 그래프의 Scale-free 현상이 밝혀진 이후 Erdos와 Renyi가 제안한 고전적인 랜덤그래프 모델과는 다른 많은 랜덤그래프 모델들이 제시되었고 그 모델들에 대한 고찰과 연구가 진행되고 있다. 이에 따라 여러 가지 방법으로 정의된 랜덤그래프 모델들이 Erdos-Renyi 모델과는 얼마나 다른지 판별하는 방법은 매우 중요하다. 따라서 랜덤그래프 모델들을 비교하여 서로 다름 또는 같음을 분별하는 방법을 연구할 예정이다. 경쟁그래프는 유향그래프인 네트워크 구조의 심층적 모델링을 가능하게 하는 이론이기 때문에, 고차원 데이터 분석에 획기적인 접근법을 제시할 수 있을 것이며 많은 적용 분야의 후속 연구들이 파생될 수 있을 것이다. 특히, 네트워크 관계의 일차적 모델링으로 부터 교차 그래프, 경쟁그래프 등 이차적 구조 패턴을 모델링하는 새로운 그래프 구조화를 이용한 분석방법과 적용 연구가 더욱 촉진될 것으로 보인다. 현재 그래프 이론을 데이터 구조에 적용한 연구들이 일차적 모델링을 이용한 것에 그치고 있는 경우가 많으므로, 숨겨진 구조를 다시 네트워크로 모델링하여 변수들에 대한 여러 차원의 모델을 구축하는 새로운 접근법은 그래프 이론의 적용 연구에 새로운 방향을 제시할 수 있을 것이다.  

    The importance of the combinatorics and graph theory has been growing due to the interdisciplinary research where mathematical tools are used as well as their own importance in pure mathematics. To classify various types of graph models for explaining current or future network, we should be able to mutually compare those models. Since the observation of the scale-free phenomena in internet graph, many random graph models have been introduced, which are different from classical random graph models suggested by Erdos and Renyi, and further speculations and researches are ongoing. Hence, it is extremely important to differentiate the random graph models which are defined in various ways from the Erdos-Renyi model. It is one of our research projects to develop an efficient method to compare different random graph models and classify them. Especially, competition graphs are tools to model the structure of the networks which can be understood as directed graphs, and thus we expect that the competition graphs could be used in high dimensional data analysis, and further subsequence research subjects could be derived in applications. The group research focuses on the analysis of combinatorial objects and algorithms occurring in mathematics and other applied fields. Specifically, the research subjects include combinatorial study for analyzing mass data structure and algorithms, combinatorial interpretation and computation of the Selberg integrals, and study on random graph models and the competition number of the graphs.