34 lines
1.1 KiB
Markdown
34 lines
1.1 KiB
Markdown
---
|
||
title: "Hypergraph Ramsey Number（超图拉姆齐数）"
|
||
created: 2026-05-11
|
||
updated: 2026-05-11
|
||
type: concept
|
||
tags: [combinatorics, hypergraph-theory]
|
||
sources: [[ramsey-numbers-survey]]
|
||
---
|
||
|
||
# Hypergraph Ramsey Number（超图拉姆齐数）
|
||
|
||
## 定义
|
||
|
||
k-一致超图的拉姆齐数 R^{(k)}(s₁,...,s_c) 定义为：对完全 k-一致超图的 c-着色，必存在颜色为 i 的单色 s_i-团的最小顶点数。
|
||
|
||
## 核心特征
|
||
|
||
- **超指数增长**：对于 k ≥ 3，R^{(k)}(s,n) 的增长涉及迭代指数塔（tower function）
|
||
- **双指数界**：2^{c₁ n^{k-2}} < R^{(k)}(s,n) < 2^{2^{c₂ n^{k-2}}}
|
||
|
||
## 与图的根本差异
|
||
|
||
图的 Ramsey 数增长最多是指数的（底数 2–4），而超图 Ramsey 数跃升至双指数甚至更高——揭示了高维组合结构的极端复杂性。
|
||
|
||
## 必要工具
|
||
|
||
- **超图正则性引理**：Szemerédi 正则性引理的高维推广
|
||
- **Gowers 一致性范数**：处理高阶结构的核心分析工具
|
||
|
||
## 相关概念
|
||
|
||
- [[ramsey-numbers|拉姆齐数]]
|
||
- [[szemerédi-regularity-lemma|Szemerédi 正则性引理]]
|