超图尺寸 Ramsey 数的新界
《Discrete Mathematics》:New bounds on the size-Ramsey numbers of hypergraphs
【字体:
大
中
小
】
时间:2026年09月20日
来源:Discrete Mathematics 1.1
编辑推荐:
摘要
我们得到了k-均匀超图的尺寸Ramsey数的两个新界。首先,我们证明当 $k \geq 4$ 且 $n \geq k$ 时,$\hat{R}(K_n^{(k)}) \geq \hat{R}(K_{n-2}^{(k-2)}) \binom{k}{2} \binom{R(
摘要
我们得到了k-均匀超图的尺寸Ramsey数的两个新界。首先,我们证明当 $k \geq 4$ 且 $n \geq k$ 时,$\hat{R}(K_n^{(k)}) \geq \hat{R}(K_{n-2}^{(k-2)}) \binom{k}{2} \binom{R(K_n^{(k)})}{2}$,这推广了Dudek、La Fleur、Mubayi和R?dl(2017)的结果。其次,将Tikhomirov(2024)的结果推广到超图,我们得到了存在一个正常数 $c = c(k)$,使得对于每个 $n$,都存在一个阶至多为 $n$、最大度为 $k+1$ 的k-均匀超图 $G$,使得 $\hat{R}(G) = \Omega(n^{\exp(c \log n)})$。这改进了Dudek、La Fleur、Mubayi和R?dl在同一论文中得到的先前下界 $\hat{R}(G) = \Omega(n (\log n)^c)$。
引言
设 $G$ 和 $H$ 为图,记 $H \to G$ 表示 $H$ 的每一种2-边着色都产生 $G$ 的某个单色副本。Ramsey数 $R(G)$ 是满足 $K_n \to G$ 的最小 $n$。自然地,我们可以最小化边数。记 $E(G)$ 为其边集。定义尺寸Ramsey数 $\hat{R}(G)$ 为满足 $H \to G$ 的图 $H$ 的最小边数,即
$$\hat{R}(G) = \min\{|E(H)| : H \to G\}.$$
1978年,Erd?s、Faudree、Rousseau和Schelp [13] 开创了尺寸Ramsey数的研究。由于 $K_{R(G)} \to G$,我们得到平凡的上界 $\hat{R}(G) \leq \binom{R(G)}{2}$。Chvátal(见例如[13])证明了 $\hat{R}(K_n) = \binom{R(K_n)}{2}$。
稀疏图的尺寸Ramsey数引起了广泛关注。设 $P_n$ 为阶为 $n$ 的路径。回答Erd?s [12] 的一个问题,Beck [3] 证明了 $\hat{R}(P_n) = O(n)$。据我们所知,目前的界如下:
$$(3.75 - o(1))n \leq \hat{R}(P_n) \leq \frac{7}{4}n,$$
其中下界由Bal和DeBiasio [1] 得到,上界由Dudek和Pra?at [11] 得到。路径尺寸Ramsey数的线性性被推广到了有界度树,由Friedman和Pippenger [14] 完成,被推广到了圈,由Haxell、Kohayakawa和?uczak [16] 完成。Beck [4] 提出了一个问题:对于有界度的图 $G$,$\hat{R}(G)$ 是否总是关于 $G$ 的大小线性的?R?dl和Szemerédi [23] 对此给出了否定的回答,他们证明了存在阶为 $n$、最大度为3、尺寸Ramsey数为 $\Omega(n(\log n)^{1/60})$ 的图。他们还猜想,对于固定的整数 $\Delta$,存在 $\varepsilon > 0$ 使得
$$\Omega(n^{1+\varepsilon}) = \max_G \hat{R}(G) = O(n^{2-\varepsilon}),$$
其中最大值在所有阶为 $n$、最大度至多为 $\Delta$ 的图 $G$ 上取。上界由Kohayakawa、R?dl、Schacht和Szemerédi [19] 证明。近期有一些相关的进一步结果,例如有关于三次图 [7]、网格 [8] 等,但下界仍然广泛开放,尽管Tikhomirov [24] 取得了一些新进展,他证明了存在阶为 $n$、最大度为3、尺寸Ramsey数为 $\Omega(n^{\exp(c \log n)})$ 的图。关于尺寸Ramsey数的更多近期结果,见例如 [5]、[6]、[9]、[17]、[18]。
顶点集为 $V(G)$ 的k-均匀超图 $G$(简称k-图)是 $V(G)$ 的k元素子集(称为边)的一个族。k-图 $G$ 的Ramsey数 $R(G)$ 和尺寸Ramsey数 $\hat{R}(G)$ 定义类似。对于每个k-图 $G$,我们有
$$\hat{R}(G) \leq \binom{R(G)}{k}.$$
超图的尺寸Ramsey数直到最近才开始被研究,Dudek、La Fleur、Mubayi和R?dl [10] 开创了这一研究方向。与图的尺寸Ramsey数不同,即使 $G$ 是 $k \geq 3$ 时的完全k-图 $K_n^{(k)}$,我们也不知道 $\hat{R}(G)$ 的精确值。事实上,McKay [22] 证明了 $\hat{R}(K_4^{(3)}) \leq \binom{133}{3} - 1 = \binom{R(K_4^{(3)})}{3} - 1$,所以对于 $k \geq 3$ 一般情况下 $\hat{R}(K_n^{(k)}) = \binom{R(K_n^{(k)})}{k}$ 不成立。
**问题 1.1**(Dudek、La Fleur、Mubayi和R?dl [10])
设 $k \geq 3$,令 $N = R(K_n^{(k)})$。定义 $K_N^{(k)-}$ 为从 $K_N^{(k)}$ 中删除一条边后得到的k-图。$K_N^{(k)-} \to K_n^{(k)}$ 是否成立?
然而,我们仅从 [10] 知道
$$\hat{R}(K_n^{(3)}) \geq \Omega(n^2 \binom{R(K_n^{(3)})}{2}).$$
在本文中,我们首先将上述结果推广如下。我们相信这个下界不是紧的,因此没有尝试优化常数。
**定理 1.2** 设 $k \geq 4$ 且 $n \geq k$。则
$$\hat{R}(K_n^{(k)}) \geq \hat{R}(K_{n-2}^{(k-2)}) \binom{k}{2} \binom{R(K_n^{(k)})}{2}.$$
Dudek、La Fleur、Mubayi和R?dl [10] 也研究了有界度超图。特别地,他们得到了存在有 $n$ 个顶点、最大度为 $k+1$ 的k-图 $G$,使得
$$\hat{R}(G) = \Omega(n (\log n)^c).$$
关于文献中的更多近期结果,见例如 [2]、[15]、[20]、[21]、[25]。
在本文中,我们也将改进(1)如下。
**定理 1.3** 对于任何 $k \geq 3$,存在一个正常数 $c = c(k)$,使得对于每个 $n$,都存在一个阶至多为 $n$、最大度为 $k+1$ 的k-图 $G$,使得 $\hat{R}(G) = \Omega(n^{\exp(c \log n)})$。
**部分证明片段**
**定理1.2的证明**
设 $k \geq 4$ 且 $n \geq k$。我们可以假设 $n > k$,因为当 $n = k$ 时断言是平凡的。设 $R = R(K_n^{(k)})$,$D = \hat{R}(K_{n-2}^{(k-2)})$。我们将证明,如果在 $V(H)$ 上定义的k-图 $H$ 满足 $|E(H)| < D\binom{k}{2}\binom{R}{2}$,则 $H \nrightarrow K_n^{(k)}$。
反设存在一个k-图 $H$ 满足(2)且 $H \to K_n^{(k)}$。在所有这样的反例中,选择边数最少的一个。
设 $\partial_2 H$ 为 $H$ 的2-阴影,即 $V$ 的所有至少被 $H$ 的一条边所包含的2元素子集的集合。我们也用 $\partial_2 H$ 表示……
**定理1.3的证明**
定理1.3的证明思路主要来自 [10]、[23]、[24]。我们首先给出 $(k-1)$ 元k-树的一般定义。
设 $k \geq 2$,$m \geq 1$ 为整数。首先,令 $B_1(k)$ 为深度为1的 $(k-1)$ 元k-树,它由一条边 $e = \{v_1, v_2, \ldots, v_k\}$ 组成。我们可以固定一个顶点 $v_i$,记为 $v_1$,将其标记为根。我们总是称其他 $k-1$ 个顶点为叶子。在第二步中,对于 $B_1(k)$ 的每个叶子,我们添加 $k-1$ 个新顶点以形成一条新边。这就构成了深度为2的 $(k-1)$ 元k-树 $B_2(k)$……
**致谢**
作者感谢刘子之提出的许多有益建议,以及审稿人给出的深刻意见,这些意见促使我们补充了原证明中不完整的讨论,并大大提升了论文的质量。
陈文 | 林启忠
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号