问题
对角拉姆齐数 R(k,k)( «最小 n:任意 n 点图含 k-团或 k-独立集 »)满足 R(k,k) 与 4k 同阶(Erdős 的随机下界 + Erdős–Szekeres 上界); «比值 » R(k,k)/4k 的 «极限 » 存在吗? «极限常数 » 的 «存在性 » 比本册 03 号( «拉姆齐数的指数 »)更精细一层: «指数 » 已知( «4 »)、 «常数 » 未定、 «极限 » 未证。
主要概念
随机图的两把界
下界: G(n,1/2) 无 k-团与 k-独立集的 «期望 » 论证( «一阶矩 »)给 R(k,k) > (1+o(1))·k·2k/2/e·√2—— «精确 » 地:R > (√2/e)·k·2k/2(1+o(1))。上界:Erdős–Szekeres 的 «递归 » R(k,k) ≤ C(2k−2, k−1) ≈ 4k/√(πk)。 «比值 » 界:[(√2/e)·k3/2·2−k/2, O(1/√k)] 型窗口—— «0.29 到 0 » 的 «窄化 » 未成。
浓度结果
«随机图 Ramsey » 的 «条件 » 浓度( «R(k,k) 集中在 « 窄窗 »» 的 «结果 » 都是 «条件型 »—— «假设 « 边界 » 结构 »); «无条件的 » 窗口结果:Thomason 型 «R(k,k) 的 « 上界 » 精细化 »( «常数 » 逐级压)与 «下界 » 的 «LO 精细化 »( «Lovász » 局部引理型)。
主要命题与证明
命题 1(Erdős–Szekeres 上界,完整递归) R(s,t) ≤ R(s−1,t) + R(s,t−1)。
证明 取点 v: «邻域 » 与 «非邻域 » 分别含 « (s−1,t) » 与 « (s,t−1) » 的 «必含 » 尺寸—— «鸽笼 »: |N(v)| + |N̄(v)| = n−1 ≥ R(s−1,t) + R(s,t−1) − 1 ⟹ 一侧 «超 »。归纳即得。□
命题 2(下界的极限常数下限) liminf R(k,k)/4k ≥ (√2/e)·k3/2·2−k/2 的 «分析 »—— «比值 » 的 «已知窗口 » 随 k «漂移 »: «极限存在 » 的 «证伪域 » 与 «证实域 » 都空。
进展与文献
Erdős–Szekeres 1935; «随机 » 下界的 «多轮 » 精化( «LO »、 «Kim » 的 «非对角 »);Thomason 的 «上界 » 常数系列;Matzke–... 的 «窗口 » 结果;Sawin 的 «极限 » 讨论文( «« 压缩 » 的 « 方法 » 现状 »)。开放核心: «极限存在性 » 需 « « 亚指数 » 世界 » 的 «结构 »( «03 号 » 的 «解决 » 是 «前置 »)—— «目前没有任何方法触及 »(站上口径如实); «非对角 » R(s,t) 的 «极限 » 类比问题独立成趣。