Measurable Domatic Partitions

Basic Information

• Paper ID: 2205.05751
• Title: Measurable Domatic Partitions
• Author: Edward Hou (California Institute of Technology)
• Classification: math.LO (Logic), math.CO (Combinatorics)
• Publication Date: May 2022 (arXiv preprint, v2 updated October 2025)
• Paper Link: https://arxiv.org/abs/2205.05751

Abstract

This paper investigates measurable domatic partitions on compact Polish groups of finite topological dimension. For a compact Polish group Γ and its countably infinite subset S ⊆ Γ, a dominating ℵ₀-partition is a partial function f: Γ ⇀ ℕ such that for each x ∈ Γ, fS·x = ℕ. The author proves that the existence of continuous dominating ℵ₀-partitions is equivalent to the existence of Baire measurable dominating ℵ₀-partitions, which is equivalent to the topological closure of S being uncountable. For all choices of S, Haar measurable dominating ℵ₀-partitions exist. The paper also studies domatic partitions in the general setting of descriptive graph combinatorics.

Research Background and Motivation

Problem Origins

This research extends the classical graph-theoretic domatic partition problem to infinite graphs. The domatic partition problem requires coloring the vertices of a graph such that every vertex's neighborhood contains all colors. This concept was originally studied by Zelinka on finite hypercube graphs, who proved that the n-regular hypercube graph Qₙ admits a dominating n-partition if and only if n is a power of 2.

Research Significance

1. Theoretical Significance: Extends classical finite graph domatic partition theory to the infinite case, particularly studying measurability questions within the framework of descriptive set theory
2. Interdisciplinary Value: Connects multiple mathematical branches including graph theory, topological group theory, descriptive set theory, and measure theory
3. Technical Innovation: First systematic study of the existence of domatic partitions under different measurability conditions

Limitations of Existing Approaches

• Classical finite graph domatic partition theory cannot be directly extended to the infinite case
• Lack of a unified framework for handling different measurability requirements
• Insufficient understanding of domatic partitions on Schreier graphs

Core Contributions

1. Established Complete Characterization of Dominating ℵ₀-Partition Existence: For finite-dimensional compact Polish groups, proved that continuous and Baire measurable dominating ℵ₀-partitions exist if and only if the topological closure of the generating set S is uncountable
2. Proved Universal Existence of Measure-Theoretic Domatic Partitions: For arbitrary Polish groups and Borel probability measures, proved that μ-measurable dominating ℵ₀-partitions always exist
3. Developed Techniques for Constructing Open Set Domatic Partitions: Through dimension theory and the Lovász Local Lemma, provided general methods for constructing open set dominating finite partitions
4. Provided Applications to Sum Set Theory: Generalized classical results of Erdős-Kunen-Mauldin on sum sets
5. Established Edge-Coloring Domatic Partition Theory: Studied edge-coloring versions of domatic partitions, providing both existence and non-existence results

Methodology Details

Task Definition

Let G be a directed graph on vertex set V. A dominating k-partition is a sequence of k pairwise disjoint dominating sets, where a dominating set D satisfies D ∩ N_G(v) ≠ ∅ for each vertex v ∈ V. Equivalently, a dominating partial function f: V ⇀ k satisfies fN_G(v) = k for each vertex v.

For the Schreier graph Sch(Γ, S, Γ), where Γ is a Polish group and S ⊆ Γ is a subset, the edge set is {(γ, s·γ): γ ∈ Γ, s ∈ S}.

Core Technical Framework

1. Anti-Domaticity Results

Theorem 2.1: Let a Polish group Γ act continuously on a Polish space X, and let S ⊆ Γ be a countably compact set. For any Baire measurable function f: X → ω, there exists a comeager set where f is not dominating at those points.

Proof Strategy: Uses the Baire Category Theorem and compactness to show that the image of a continuous function on a compact set must be bounded.

2. Open Set Domatic Partition Construction

Theorem 2.12 (Main Technical Lemma): Let Γ be a locally compact Polish group with a two-sided invariant metric and finite topological dimension. For each k, n ∈ ℕ, there exists N = N(k, n) such that for any sets F₀, ..., Fₙ₋₁ ⊆ Γ of size N, there exist pairwise disjoint open sets D₀, ..., Dₖ₋₁ such that each Fᵢ·γ intersects each Dⱼ.

Proof Strategy:

1. Uses the Gleason-Yamabe theorem to characterize the dimension of locally compact Polish groups
2. Constructs packings of open sets controlling dimension growth
3. Applies the Lovász Local Lemma to handle random colorings

3. Open Pair Property

Definition 2.13: An infinite compact Polish group Γ has the open pair property if for every finite complete family of sets P₀, ..., Pₙ₋₁, there exist two disjoint open sets A₀, A₁ that both dominate all Pᵢ.

Lemma 2.14: Finite-dimensional infinite compact Polish groups have the open pair property.

Technical Innovations

1. Application of Dimension Theory: First systematic application of topological dimension theory to domatic partition problems, achieving open set partitions through boundary dimension control
2. Unified Treatment of Measure and Category: Develops technical framework simultaneously handling measure-theoretic and Baire category versions
3. Special Structure of Schreier Graphs: Exploits special properties of group actions, transforming abstract graph problems into group-theoretic problems

Main Results

Core Theorems

Theorem 1.1 (Corollary 2.18): Let Γ be a finite-dimensional compact Polish group and S ⊆ Γ be a subset. Then Sch(Γ, S, Γ) admits an open set dominating ℵ₀-partition if and only if it admits a Baire measurable dominating ℵ₀-partition if and only if S ⊆ Γ is uncountable.

Theorem 1.2 (Corollary 2.19): Let S ⊆ ℝⁿ. Then Sch(ℝⁿ, S, ℝⁿ) admits an open set or Baire measurable dominating ℵ₀-partition if and only if S is uncountable or unbounded.

Theorem 1.3 (Corollary 3.6): Let Γ be a Polish group, μ a Borel probability measure on Γ, and S ⊆ Γ a countably infinite subset. Then Sch(Γ, S, Γ) admits a μ-measurable dominating ℵ₀-partition.

Application Results

Theorem 1.5 (Corollary 2.29): Let P ⊆ ℝⁿ be a non-empty closed perfect subset. Then there exist 2^ℵ₀ pairwise disjoint families of closed subsets {Cᵢ: i < 2^ℵ₀} such that P + Cᵢ = ℝⁿ and Cᵢ + Cⱼ = ℝⁿ for all i, j < 2^ℵ₀.

Negative Results

Theorem 4.3: There exists a vertex-transitive undirected ℵ₀-regular acyclic Borel graph G on a Polish space that does not admit a Baire measurable dominating 3-partition.

Theorem 4.5 (Weilacher): There exists an acyclic simple undirected ℵ₀-regular acyclic Borel graph G that does not admit a symmetric Borel dominating edge 2-partition.

Technical Details

Dimension Control Techniques

Through inductive construction in Lemma 2.8, for a Polish space X and closed subsets M₀, ..., Mᵣ₋₁, one can construct an open set U such that ∂U ∩ Mᵢ has strictly smaller dimension than Mᵢ. This is the technical core of the entire theory.

Greedy Algorithm

For smooth Borel graphs, one can use a greedy algorithm to construct Borel dominating ℵ₀-partitions. The algorithm colors the first uncolored neighbor of the current vertex at each step.

Probabilistic Methods

Using the Borel version of the Lovász Local Lemma, one can construct measurable domatic partitions on graphs satisfying certain conditions.

Related Work

Classical Domatic Partition Theory

• Zelinka's results on finite hypercube graphs
• Probabilistic methods in domatic partitions

Descriptive Graph Combinatorics

• Comprehensive work by Kechris-Marks
• Coloring problems on Borel graphs
• Measure-theoretic and Baire category methods

Group-Theoretic Background

• Polish group theory
• Properties of Schreier graphs
• Measurability of group actions

Conclusions and Discussion

Main Conclusions

1. For finite-dimensional compact Polish groups, the existence of continuous and Baire measurable dominating ℵ₀-partitions is completely determined by the topological properties of the generating set
2. Measure-theoretic dominating ℵ₀-partitions possess universal existence
3. Dimension theory is an effective tool for addressing domatic partition problems

Limitations

1. The infinite-dimensional case remains open (Problem 2.20)
2. Results for locally finite graphs are relatively limited
3. The existence problem for Borel dominating finite partitions is complex

Future Directions

1. Study domatic partitions on infinite-dimensional compact Polish groups
2. Develop more general dimension control techniques
3. Explore connections with other combinatorial optimization problems

In-Depth Evaluation

Strengths

1. Theoretical Depth: Organically combines multiple mathematical branches, establishing profound theoretical connections
2. Technical Innovation: The application of dimension theory to domatic partitions is entirely novel
3. Complete Results: Provides complete characterization of the problem, including both positive and negative results
4. Applied Value: Applications to sum set theory demonstrate the broad applicability of the methods

Weaknesses

1. Technical Complexity: The proof techniques are quite complex, potentially limiting accessibility of the results
2. Open Problems: Important questions such as the infinite-dimensional case remain unresolved
3. Computational Complexity: Does not discuss the complexity of constructive algorithms

Impact

This paper has significant impact in the field of descriptive graph combinatorics, providing new technical tools and research directions. The dimension-theoretic methods may find applications in other graph-theoretic problems.

Applicable Scenarios

The methods are applicable to:

1. Combinatorial problems on graphs with group structure
2. Infinite combinatorial optimization problems requiring measurability considerations
3. Geometric problems on topological groups

References

The paper cites 35 important references covering classical and cutting-edge work in descriptive set theory, topological group theory, graph theory, and combinatorics.