1.7 KiB
1.7 KiB
title, created, updated, type, tags, sources, confidence
| title | created | updated | type | tags | sources | confidence | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Random Sphere Graph（随机球面图） | 2026-06-29 | 2026-06-29 | concept |
|
|
high |
Random Sphere Graph G_{k,p}(n)
由 Ma, Shen, Xie (2026) 在 Ramsey 数下界研究中引入的新型随机图模型，将经典 probabilistic-method 从离散随机图推广到连续几何测度空间。
定义
在 k 维单位球面 S^k ⊂ R^{k+1} 上：
- 均匀随机采样 n 个点 x₁, ..., x_n ∈ S^k
- 以概率 p 独立连接每对点 (i, j)
- 得到随机图 G_{k,p}(n)
与 Erdős-Rényi 模型的区别
| 维度 | random-graph-theory | G_{k,p}(n) | |------|---------|-----------| | 点集 | 抽象顶点集 [n] | S^k 上的几何点 | | 边独立性 | 仅依赖 p | 依赖 p × 几何位置 | | 测度空间 | 离散 | 连续（球面测度） | | 适用场景 | 一般组合问题 | 几何结构约束问题 |
在 Ramsey 理论中的作用
经典 Erdős (1947) 下界使用 G(n, 1/2) 随机着色 K_n 边，计算出现单色团的概率。本文的随机球面图通过几何测度引入额外的结构约束，使得避免大团的概率可以更精确地控制——从而突破 78 年来的指数壁垒。
技术要点
- 需要球面几何的测度估计（surface measure on S^k）
- 引入 perfect-sequences 来刻画球面上点的邻接结构
- 核心挑战：在高维球面上计算随机事件的概率下界