2025-11-20T08:49:14.495176

Measurable domatic partitions

Hou
Let $Γ$ be a compact Polish group of finite topological dimension. For a countably infinite subset $S\subseteq Γ$, a domatic $\aleph_0$-partition (for its Schreier graph on $Γ$) is a partial function $f:Γ\rightharpoonup\mathbb{N}$ such that for every $x\in Γ$, one has $f[S\cdot x]=\mathbb{N}$. We show that a continuous domatic $\aleph_0$-partition exists, if and only if a Baire measurable domatic $\aleph_0$-partition exists, if and only if the topological closure of $S$ is uncountable. A Haar measurable domatic $\aleph_0$-partition exists for all choices of $S$. We also investigate domatic partitions in the general descriptive graph combinatorial setting.
academic

Measurable domatic partitions

基本信息

  • 论文ID: 2205.05751
  • 标题: Measurable domatic partitions
  • 作者: Edward Hou (California Institute of Technology)
  • 分类: math.LO (Logic), math.CO (Combinatorics)
  • 发表时间: 2022年5月 (arXiv preprint, v2 updated October 2025)
  • 论文链接: https://arxiv.org/abs/2205.05751

摘要

本文研究有限拓扑维数紧致Polish群上的可测支配分割问题。对于紧致Polish群Γ和其可数无穷子集S⊆Γ，支配ℵ₀-分割是一个偏函数f:Γ⇀ℕ，使得对每个x∈Γ都有fS·x=ℕ。作者证明了连续支配ℵ₀-分割存在当且仅当Baire可测支配ℵ₀-分割存在，当且仅当S的拓扑闭包不可数。对于所有S的选择，Haar可测支配ℵ₀-分割都存在。文章还在一般描述图组合学设定下研究了支配分割。

研究背景与动机

问题来源

本研究源于经典的图论支配分割问题在无穷图上的推广。支配分割问题要求将图的顶点着色，使得每个顶点的邻域都包含所有颜色。这个概念最初由Zelinka在有限超立方体图上研究，他证明了n-正则超立方体图Qₙ承认支配n-分割当且仅当n是2的幂。

研究意义

  1. 理论意义: 将经典的有限图支配分割理论推广到无穷情形，特别是在描述集合论框架下研究可测性问题
  2. 交叉学科价值: 连接了图论、拓扑群论、描述集合论和测度论等多个数学分支
  3. 技术创新: 首次系统研究了不同可测性条件下支配分割的存在性

现有方法局限性

  • 经典的有限图支配分割理论无法直接推广到无穷情形
  • 缺乏处理不同可测性要求的统一框架
  • 对Schreier图上支配分割的理解不够深入

核心贡献

  1. 建立了支配ℵ₀-分割存在性的完整刻画: 对于有限维紧致Polish群，证明了连续、Baire可测支配ℵ₀-分割存在的充要条件是生成集S的拓扑闭包不可数
  2. 证明了测度理论支配分割的普遍存在性: 对于任意Polish群和Borel概率测度，证明了μ-可测支配ℵ₀-分割总是存在
  3. 发展了构造开集支配分割的技术: 通过维数理论和Lovász局部引理，给出了构造开集支配有限分割的一般方法
  4. 给出了和集理论的应用: 推广了Erdős-Kunen-Mauldin关于和集的经典结果
  5. 建立了边着色支配分割理论: 研究了支配分割的边着色版本，给出了存在性和非存在性结果

方法详解

任务定义

设G是顶点集V上的有向图，支配k-分割是k个两两不交的支配集的序列，其中支配集D满足对每个顶点v∈V都有D∩N_G(v)≠∅。等价地，支配偏函数f:V⇀k满足对每个顶点v都有fN_G(v)=k。

对于Schreier图Sch(Γ,S,Γ)，其中Γ是Polish群，S⊆Γ是子集，图的边集为{(γ,s·γ):γ∈Γ,s∈S}。

核心技术框架

1. 反支配性结果 (Anti-domaticity)

定理2.1: 设Polish群Γ连续作用在Polish空间X上，S⊆Γ是可数紧致集。对任意Baire可测函数f:X→ω，存在余范畴集使得f在这些点处不是支配的。

证明思路: 利用Baire范畴定理和紧致性，证明连续函数在紧致集上的像必须有界。

2. 开集支配分割构造

定理2.12 (主要技术引理): 设Γ是具有双侧不变度量和有限拓扑维数的局部紧致Polish群。对每个k,n∈ℕ，存在N=N(k,n)使得对任意大小为N的集合F₀,...,Fₙ₋₁⊆Γ，存在两两不交的开集序列D₀,...,Dₖ₋₁，每个Fᵢ·γ都与每个Dⱼ相交。

证明策略:

  1. 利用Gleason-Yamabe定理刻画局部紧致Polish群的维数
  2. 构造开集的打包，控制维数增长
  3. 应用Lovász局部引理处理随机着色

3. 开对性质 (Open Pair Property)

定义2.13: 无穷紧致Polish群Γ具有开对性质，如果对每个有限完全集族P₀,...,Pₙ₋₁，存在两个不交开集A₀,A₁都支配所有Pᵢ。

引理2.14: 有限维无穷紧致Polish群具有开对性质。

技术创新点

  1. 维数理论的应用: 首次将拓扑维数理论系统应用于支配分割问题，通过控制边界维数实现开集分割
  2. 测度与范畴的统一处理: 发展了同时处理测度论和Baire范畴版本的技术框架
  3. Schreier图的特殊结构: 利用群作用的特殊性质，将抽象图问题转化为群论问题

主要结果

核心定理

定理1.1 (推论2.18): 设Γ是有限维紧致Polish群，S⊆Γ是子集。则Sch(Γ,S,Γ)承认开集支配ℵ₀-分割当且仅当承认Baire可测支配ℵ₀-分割当且仅当S⊆Γ不可数。

定理1.2 (推论2.19): 设S⊆ℝⁿ。则Sch(ℝⁿ,S,ℝⁿ)承认开集或Baire可测支配ℵ₀-分割当且仅当S不可数或S无界。

定理1.3 (推论3.6): 设Γ是Polish群，μ是Γ上的Borel概率测度，S⊆Γ是可数无穷子集。则Sch(Γ,S,Γ)承认μ-可测支配ℵ₀-分割。

应用结果

定理1.5 (推论2.29): 设P⊆ℝⁿ是非空闭完全子集。则存在2^ℵ₀个两两不交的闭子集族{Cᵢ:i<2^ℵ₀}，使得P+Cᵢ=ℝⁿ且Cᵢ+Cⱼ=ℝⁿ对所有i,j<2^ℵ₀成立。

负面结果

定理4.3: 存在全循环无向ℵ₀-正则无环Borel图G在Polish空间上，不承认Baire可测支配3-分割。

定理4.5 (Weilacher): 存在无循环简单无向ℵ₀-正则无环Borel图G，不承认对称Borel支配边2-分割。

技术细节

维数控制技术

通过引理2.8的归纳构造，对于Polish空间X和闭子集M₀,...,Mᵣ₋₁，可以构造开集U使得∂U∩Mᵢ的维数严格小于Mᵢ的维数。这是整个理论的技术核心。

贪心算法

对于光滑Borel图，可以使用贪心算法构造Borel支配ℵ₀-分割。算法在每步为当前顶点选择第一个未着色的邻居进行着色。

随机方法

利用Lovász局部引理的Borel版本，可以在满足一定条件的图上构造可测支配分割。

相关工作

经典支配分割理论

  • Zelinka的有限超立方体图结果
  • 概率方法在支配分割中的应用

描述图组合学

  • Kechris-Marks的综述性工作
  • Borel图上的着色问题
  • 测度论和Baire范畴方法

群论背景

  • Polish群理论
  • Schreier图的性质
  • 群作用的可测性

结论与讨论

主要结论

  1. 对于有限维紧致Polish群，连续和Baire可测支配ℵ₀-分割的存在性完全由生成集的拓扑性质决定
  2. 测度论支配ℵ₀-分割具有普遍存在性
  3. 维数理论是处理支配分割问题的有效工具

局限性

  1. 无穷维情形仍然开放（问题2.20）
  2. 对局部有限图的结果相对有限
  3. Borel支配有限分割的存在性问题复杂

未来方向

  1. 研究无穷维紧致Polish群上的支配分割
  2. 发展更一般的维数控制技术
  3. 探索与其他组合优化问题的联系

深度评价

优点

  1. 理论深度: 将多个数学分支有机结合，建立了深刻的理论联系
  2. 技术创新: 维数理论在支配分割中的应用是全新的
  3. 结果完整: 给出了问题的完整刻画，包括正面和负面结果
  4. 应用价值: 在和集理论中的应用展示了方法的广泛适用性

不足

  1. 技术复杂: 证明技术相当复杂，可能限制了结果的可接近性
  2. 开放问题: 无穷维情形等重要问题仍未解决
  3. 计算复杂性: 没有讨论构造算法的复杂性

影响力

本文在描述图组合学领域具有重要影响，为该领域提供了新的技术工具和研究方向。维数理论方法可能在其他图论问题中找到应用。

适用场景

该方法适用于：

  1. 具有群结构的图上的组合问题
  2. 需要考虑可测性的无穷组合优化问题
  3. 拓扑群上的几何问题

参考文献

论文引用了35篇重要文献，涵盖了描述集合论、拓扑群论、图论和组合学等多个领域的经典和前沿工作。