论文标题
图形理论的两个问题
Two problems in graph Ramsey theory
论文作者
论文摘要
我们研究了Ramsey理论的两个问题。在1970年代初期，埃尔德（Erd）和奥尼尔（O'Neil）考虑了拉姆齐数字的概括。 Given integers $n,k,s$ and $t$ with $n \ge k \ge s,t \ge 2$, they asked for the least integer $N=f_k(n,s,t)$ such that in any red-blue coloring of the $k$-subsets of $\{1, 2,\ldots, N\}$, there is a set of size $n$ such that either each of its $ s $ -subsets包含一些红色$ k $ -subset中，或者其$ t $ -subsets中的每一个都包含在某些蓝色$ k $ -subset中。 Erdős和O'Neil在$ k \ ge s+t-1 $时找到了$ f_k（n，s，t）$的确切公式。在可以说的更有趣的情况下，$ k = s+t-2 $，他们显示了$ 2^{ - \ binom {k} {2}}} n <\ log f_k（n，s，s，t）<2n $，用于足够大的$ n $。我们的主要结果缩小了这些下限和上限之间的差距，确定$ f_ {s+t-2}（n，s，t）$的对数达到乘法因子。 最近，达马斯迪（Damásdi），凯塞格（Keszegh），马利克（Malec），汤普金斯（Malec），王和扎莫拉（Zamora）在拉姆西理论中启动了对饱和问题的调查，其中人们试图最大程度地减少$ n $，以至于存在一个$ r $ ed $ -k_n $的$ k_n $，以$ k_n $ to to to to to to to to to to $ r $ r $ r $ r $ r $ k_ $ k__ $ k__ $ k_ n+k_ n+k_ n+k_ n+k_} $ k_k $。我们为此问题获得了基本急剧的界限。
We study two problems in graph Ramsey theory. In the early 1970's, Erdős and O'Neil considered a generalization of Ramsey numbers. Given integers $n,k,s$ and $t$ with $n \ge k \ge s,t \ge 2$, they asked for the least integer $N=f_k(n,s,t)$ such that in any red-blue coloring of the $k$-subsets of $\{1, 2,\ldots, N\}$, there is a set of size $n$ such that either each of its $s$-subsets is contained in some red $k$-subset, or each of its $t$-subsets is contained in some blue $k$-subset. Erdős and O'Neil found an exact formula for $f_k(n,s,t)$ when $k\ge s+t-1$. In the arguably more interesting case where $k=s+t-2$, they showed $2^{-\binom{k}{2}}n<\log f_k(n,s,t)<2n$ for sufficiently large $n$. Our main result closes the gap between these lower and upper bounds, determining the logarithm of $f_{s+t-2}(n,s,t)$ up to a multiplicative factor. Recently, Damásdi, Keszegh, Malec, Tompkins, Wang and Zamora initiated the investigation of saturation problems in Ramsey theory, wherein one seeks to minimize $n$ such that there exists an $r$-edge-coloring of $K_n$ for which any extension of this to an $r$-edge-coloring of $K_{n+1}$ would create a new monochromatic copy of $K_k$. We obtain essentially sharp bounds for this problem.
