论文标题
粉丝完整的拉姆齐号码
Fan-complete Ramsey numbers
论文作者
论文摘要
对于图形$ g $和$ h $，我们认为Ramsey数字$ r（g，h）$具有紧密的下限，即$ r（g，h）\ geq（χ（g）-1）-1）（| h | -1）+1，$χ（g）$表示$ g $ g $ g $ g $ g $ g $ g $ g $和$ | $ | $ | $ | $ h $ h $ h $ h $ h $ h vertices in $ h vertices in n $ h n n $ h.我们说$ h $是$ g $ - 如果平等成立。 让$ g+h $是从图$ g $和$ h $获得的加入图，通过在$ g $和$ h $的脱节顶点集之间添加所有边缘。令$ nh $表示$ n $ disshoint副本的联合图为$ h $。我们表明$ k_1+nh $是$ k_p $ - 如果$ n $足够大的话。特别是，如果$ n \ geq 27p^2 $，Fan-Graph $ f_n = k_1 + n k_2 $是$ k_p $ - good，则改善了由于Li and Rousseau（1996年）的$ n $的先前塔式下限。此外，对于$ g = k_p（a_1，a_1，a_2，\ dots，a_p）$，我们给出了Ramsey Number $ r（g，k_1+f）$的更严重的下限不等式，完整的$ p $ -partite Graph带有$ A_1 = 1 = 1 $ and $ a_1 = 1 $ and $ a_i and $ a_i \ a_i \ leq a____________________ \ leq a__ {i+1} $。特别是，他和福克斯（Fox）的稳定性 - 饱和引理（2021），我们表明，对于任何固定的图形$ h $，\ begin \ begin {align*} r（g，k_1+nh）= \ left \ left \ left {\ okent {arnay} $ n | h |+a_2-1 $均匀或$ a_2-1 $均匀，} \\（p-1）（n | h |+a_2-2）+1＆\ textrm {否则，} \ end} \ end {array} \正确的。 \ end {align*}其中$ g = k_p（1，a_2，\ dots，a_p）$，$ a_i $满足某些温和条件，而$ n $足够大。 $ h = k_1 $的特殊情况回答了伯尔的问题（1981）关于$ r（g，k_ {1，n}）$ from $ g $ goodness的差异（g，k_ {1，n}）$。我们获得的$ n $的所有界限都不是塔式的。
For graphs $G$ and $H$, we consider Ramsey numbers $r(G,H)$ with tight lower bounds, namely, $r(G,H) \geq (χ(G)-1)(|H|-1)+1,$ where $χ(G)$ denotes the chromatic number of $G$ and $|H|$ denotes the number of vertices in $H$. We say $H$ is $G$-good if the equality holds. Let $G+H$ be the join graph obtained from graphs $G$ and $H$ by adding all edges between the disjoint vertex sets of $G$ and $H$. Let $nH$ denote the union graph of $n$ disjoint copies of $H$. We show that $K_1+nH$ is $K_p$-good if $n$ is sufficiently large. In particular, the fan-graph $F_n=K_1 + n K_2$ is $K_p$-good if $n\geq 27p^2$, improving previous tower-type lower bounds for $n$ due to Li and Rousseau (1996). Moreover, we give a stronger lower bound inequality for Ramsey number $r(G, K_1+F)$ for the case of $G=K_p(a_1, a_2, \dots, a_p)$, the complete $p$-partite graph with $a_1=1$ and $a_i \leq a_{i+1}$. In particular, using a stability-supersaturation lemma by Fox, He and Wigderson (2021), we show that for any fixed graph $H$, \begin{align*} r(G,K_1+nH) = \left\{ \begin{array}{ll} (p-1)(n |H|+a_2-1)+1 & \textrm{if $n|H|+a_2-1$ is even or $a_2-1$ is even,}\\ (p-1)(n |H|+a_2-2)+1 & \textrm{otherwise,} \end{array} \right. \end{align*} where $G=K_p(1,a_2, \dots, a_p)$ with $a_i$'s satisfying some mild conditions and $n$ is sufficiently large. The special case of $H=K_1$ gives an answer to Burr's question (1981) about the discrepancy of $r(G, K_{1,n})$ from $G$-goodness for sufficiently large $n$. All bounds of $n$ we obtain are not of tower-types.
