星星森林的邊拉姆西數

Abstract

對於圖 G_1, G_2, ..., G_r和 F，如果當 F的邊被著上 1, 2, ..., r這些顏色時，總是存在 i使得著顏色 i的邊中包含圖 G_$的話，則記作 F -> (G_1, G_2, ..., G_r)。在所有滿足 F -> (G_1, G_2, ..., G_r)的 F中，所含邊數的最小值稱為邊拉姆西數，記作 r(G_1, G_2, ..., G_r)。 假設 G_1 = U_{i=1}^{m}{K_{1,a_i}}，G_2 = U_{i=1}^{n}{K_{1, b_i}}且 a_1 >= a_2 >= ... >= a_m，b_1 >= b_2 >= ... >= b_n，令 l_s = max_{i+j=s+1}{(a_i+b_j-1)}，Burr, Erdos, Faudree, Rousseau 和 Schelp [4]猜測 $r(G_1, G_2) = sum_{s=1}^{m+n-1}{l_s}。這篇論文的目的是研究這個猜想在 a_1,b_1以外的數都等於 1時的情形。

For graphs G_1, G_2, ..., G_r and F, we write F -> (G_1, G_2, ..., G_r)$ to mean that if the edges of F are colored by 1, 2, ..., r then there exists some i such that the edges of color i contains a copy of G_i. The size Ramsey number r(G_1, G_2, ..., G_r) is the least number of edges of a graph F for which F -> (G_1, G_2, ..., G_r). Suppose G_1 = U_{i=1}^{m}{K_{1,a_i}} with a_1 >= a_2 >= ... >= a_m and G_2 = U_{i=1}^{n}{K_{1, b_i}} with b_1 >= b_2 >= ... >= b_n. Let l_s = max_{i+j=s+1}{(a_i+b_j-1)}. Burr, Erdos, Faudree, Rousseau and Schelp [4] conjectured that r(G_1, G_2) = sum_{s=1}^{m+n-1}{ell_s}. The purpose of this thesis is to study the conjecture for the case when a_i = b_j = 1 for 2 <= i <= m and $2 <= j <= n.