Matroid and Rainbow Matching

Abstract

변이 색칠된 그래프가 주어져 있을 때 모두 다른 색을 가지는 부합(matching)을 rainbow matching이라고 한다. n개의 색으로 변이 색칠된 완전 이분 그래프의 rainbow matching의 최대 크기에 대한 추측이 Ryser, Brualdi, Stein에 의해 제기되었다. 최대 크기의 하한(lower bound)에 대해서 어디까지 연구되었는지 알아보고, 군(group)의 Cayley table으로 추측을 제한한 문제(Hall-Paige)와 2009년의 결과(Wilcox-Bray-Evan)에 대해서 알아보았다. 그 결과에 대한 응용으로 group으로 문제를 제한한 경우에서 rainbow matching의 최대 크기에 대한 하한을 얻었고, dihedral group에 대해서 Ryser-Brualdi-Stein 추측이 참인 것을 확인해 보았다. 또한 기본적인 Matroid이론과 Ryser-Brualdi 추측의 Matroid로의 확장에 대한 연구에 대해서 알아보았다.

A rainbow matching of an edge-colored graph is a matching which edges have all distinct colors. It is natural to ask about the maximum size of rainbow matching of a given edge-colored graph. This paper gives a survey on the problem, especially on the complete bipartite graphs $K_{n,n}$ which is equivalent to the Ryser-Brualdi-Stein conjecture on the Latin squares. An introduction to matroid theory and generalized versions of Ryser-Brualdi-Stein conjecture on the matroids are surveyed. The Ryser conjecture on the Cayley tables of groups is called the Hall-Paige conjecture which was solved by Wilcox, Bray, and Evan in 2009. We give applications of the theorem. One of the application gives a lower bound for the maximum size of a rainbow matching when the bipartite graph is induced by a group. Also, we showed that there is an $n-1$ partial transversal for the Cayley table of a dihedral group, which means that the Brualdi-Stein conjecture on the dihedral groups is true.