Title: 蘭西數下界的研究
A Study of the Lower Bound of Ramsey Number
Authors: 林劭原
Lin, Shao-Yuan
Fu, Hung-Lin
Keywords: 蘭西數;蘭西理論;循環著色法;ramsey number;ramsey theory;cyclic coloring method
Issue Date: 2017
Abstract: 如果一個圖$G$不含子圖$H$,則$H$為$G$的一個避圖。我們有興趣探討的問題是在給定一個圖$H$之後,是否能找到一個圖$G$,使得$G$和它的補圖$\overline{G}$都不含子圖$H$。 顯然,當$H$為$K_3$時,$C_5$就具有上述提到的性質;同時,就點數比5大的圖$G$而言,不是$G$就是$\overline{G}$一定含$K_3$這個子圖。這樣的結果就對應到大家都知道的蘭西數$R(3,3)=6$。 在這篇論文中,我們首先把研究方向放在循環圖$G$上面。對於給定的一個圖$H$,我們希望能找到循環圖$G$及$\overline{G}$使得$G$和$\overline{G}$都不含有固定點數的完全子圖。接著我們在引伸研究到把完全圖分割成多個循環圖$G_1,G_2,\cdots,G_k$使得他們全部都不含有給定次序的完全子圖。 上述得到的結果,分別提供了對應蘭西數的下界,在很多情況下,這些下界都非常接近預期獲得的蘭西數。
A graph $G$ forbids a graph $H$ if $G$ does not contain $H$ as a subgraph. It is interesting to know whether there are graphs $G$ such that both $G$ and $\overline{G}$(complement of $G$) forbid a given graph $H$. Clearly, if $H \cong K_3$, then $G$ can be chosen as $C_5$. As a matter of fact, there exist no graphs of order longer than 5 such that both $G$ and $\overline{G}$ forbid $K_3$. This fact provides a well-known result $R(3,3)=6$. In this thesis, we first focus on finding circulant graphs $G$ such that both $G$ and $\overline{G}$(also circulant) forbid complete subgraphs. Then, we extend the study to partition a complete graph into circulant graphs $G_1,G_2,\cdots,G_k$ such that neither one of them contains complete subgraphs of prescribed orders. As a consequence, the results we obtain will give a lower bound of a corresponding Ramsey number.
URI: http://etd.lib.nctu.edu.tw/cdrfb3/record/nctu/#GT070452221
Appears in Collections:Thesis