蘭西數下界的研究

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.