49 lines
1.7 KiB
Markdown
49 lines
1.7 KiB
Markdown
---
|
||
title: "Random Sphere Graph（随机球面图）"
|
||
created: 2026-06-29
|
||
updated: 2026-06-29
|
||
type: concept
|
||
tags: [random-graph, ramsey-theory, geometric-measure, probabilistic-method]
|
||
sources: [[ramsey-sphere-lowerbound]]
|
||
confidence: high
|
||
---
|
||
|
||
# Random Sphere Graph G_{k,p}(n)
|
||
|
||
> 由 Ma, Shen, Xie (2026) 在 Ramsey 数下界研究中引入的新型随机图模型，将经典 [[probabilistic-method|概率方法]] 从离散随机图推广到连续几何测度空间。
|
||
|
||
## 定义
|
||
|
||
在 k 维单位球面 S^k ⊂ R^{k+1} 上：
|
||
|
||
1. 均匀随机采样 n 个点 x₁, ..., x_n ∈ S^k
|
||
2. 以概率 p 独立连接每对点 (i, j)
|
||
3. 得到随机图 G_{k,p}(n)
|
||
|
||
## 与 Erdős-Rényi 模型的区别
|
||
|
||
| 维度 | [[random-graph-theory|G(n,p)]] | 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|完美序列]] 来刻画球面上点的邻接结构
|
||
- 核心挑战：在高维球面上计算随机事件的概率下界
|
||
|
||
## 相关概念
|
||
|
||
- [[ramsey-sphere-lowerbound|Ramsey 下界指数改进]]
|
||
- [[probabilistic-method|概率方法]]
|
||
- [[random-graph-theory|随机图理论]]
|
||
- [[perfect-sequences|完美序列]]
|
||
- [[ramsey-theory|Ramsey 理论]]
|