Partitions domatiques mesurables

Informations fondamentales

• ID de l'article: 2205.05751
• Titre: Partitions domatiques mesurables
• Auteur: Edward Hou (California Institute of Technology)
• Classification: math.LO (Logique), math.CO (Combinatoire)
• Date de publication: Mai 2022 (prépublication arXiv, v2 mise à jour octobre 2025)
• Lien de l'article: https://arxiv.org/abs/2205.05751

Résumé

Cet article étudie le problème des partitions domatiques mesurables sur les groupes polonais compacts de dimension topologique finie. Pour un groupe polonais compact Γ et un sous-ensemble dénombrable infini S⊆Γ, une partition domatique ℵ₀ est une fonction partielle f:Γ⇀ℕ telle que pour chaque x∈Γ, on ait fS·x=ℕ. L'auteur démontre que l'existence d'une partition domatique ℵ₀ continue est équivalente à l'existence d'une partition domatique ℵ₀ mesurable au sens de Baire, ce qui est équivalent à ce que la fermeture topologique de S soit non dénombrable. Pour tous les choix de S, une partition domatique ℵ₀ mesurable au sens de Haar existe. L'article étudie également les partitions domatiques dans le cadre général de la combinatoire descriptive des graphes.

Contexte et motivation de la recherche

Origine du problème

Cette recherche provient de la généralisation du problème classique de partition domatique des graphes aux graphes infinis. Le problème de partition domatique demande de colorer les sommets d'un graphe de sorte que le voisinage de chaque sommet contienne toutes les couleurs. Ce concept a été initialement étudié par Zelinka sur les hypercubes finis, qui a démontré que le graphe hypercube n-régulier Qₙ admet une partition domatique n si et seulement si n est une puissance de 2.

Signification de la recherche

1. Signification théorique: Généraliser la théorie classique des partitions domatiques des graphes finis au cas infini, en particulier étudier les problèmes de mesurabilité dans le cadre de la théorie descriptive des ensembles
2. Valeur interdisciplinaire: Établir des connexions entre la théorie des graphes, la théorie des groupes topologiques, la théorie descriptive des ensembles et la théorie de la mesure
3. Innovation technique: Première étude systématique de l'existence des partitions domatiques sous différentes conditions de mesurabilité

Limitations des méthodes existantes

• La théorie classique des partitions domatiques des graphes finis ne peut pas être directement généralisée au cas infini
• Absence d'un cadre unifié pour traiter les exigences de mesurabilité différentes
• Compréhension insuffisante des partitions domatiques sur les graphes de Schreier

Contributions principales

1. Établissement d'une caractérisation complète de l'existence des partitions domatiques ℵ₀: Pour les groupes polonais compacts de dimension finie, démonstration que la condition nécessaire et suffisante pour l'existence de partitions domatiques ℵ₀ continues ou mesurables au sens de Baire est que la fermeture topologique de l'ensemble générateur S soit non dénombrable
2. Démonstration de l'existence universelle des partitions domatiques mesurables au sens de la théorie de la mesure: Pour tout groupe polonais et toute mesure de probabilité borélienne, démonstration que les partitions domatiques ℵ₀ mesurables au sens de μ existent toujours
3. Développement de techniques de construction de partitions domatiques d'ensembles ouverts: Par la théorie de la dimension et le lemme local de Lovász, fourniture d'une méthode générale pour construire des partitions domatiques finies d'ensembles ouverts
4. Application à la théorie des ensembles sommes: Généralisation des résultats classiques d'Erdős-Kunen-Mauldin sur les ensembles sommes
5. Établissement de la théorie des partitions domatiques avec coloration d'arêtes: Étude de la version avec coloration d'arêtes des partitions domatiques, fourniture de résultats d'existence et de non-existence

Explication détaillée des méthodes

Définition de la tâche

Soit G un graphe orienté sur l'ensemble de sommets V, une partition domatique k est une séquence de k ensembles dominants deux à deux disjoints, où un ensemble dominant D satisfait D∩N_G(v)≠∅ pour chaque sommet v∈V. De manière équivalente, une fonction partielle domatique f:V⇀k satisfait fN_G(v)=k pour chaque sommet v.

Pour le graphe de Schreier Sch(Γ,S,Γ), où Γ est un groupe polonais, S⊆Γ est un sous-ensemble, l'ensemble d'arêtes est {(γ,s·γ):γ∈Γ,s∈S}.

Cadre technique fondamental

1. Résultats d'anti-domaticité

Théorème 2.1: Soit Γ un groupe polonais agissant continûment sur un espace polonais X, S⊆Γ un ensemble dénombrable compact. Pour toute fonction mesurable au sens de Baire f:X→ω, il existe un ensemble de catégorie résiduelle où f n'est pas domatique.

Stratégie de preuve: Utilisation du théorème de catégorie de Baire et de la compacité pour démontrer que l'image d'une fonction continue sur un ensemble compact doit être bornée.

2. Construction de partitions domatiques d'ensembles ouverts

Théorème 2.12 (Lemme technique principal): Soit Γ un groupe polonais localement compact avec une métrique bilatéralement invariante et de dimension topologique finie. Pour chaque k,n∈ℕ, il existe N=N(k,n) tel que pour tout ensemble de taille N, F₀,...,Fₙ₋₁⊆Γ, il existe une séquence d'ensembles ouverts deux à deux disjoints D₀,...,Dₖ₋₁ tels que chaque Fᵢ·γ intersecte chaque Dⱼ.

Stratégie de preuve:

1. Utilisation du théorème de Gleason-Yamabe pour caractériser la dimension des groupes polonais localement compacts
2. Construction d'empilements d'ensembles ouverts contrôlant la croissance dimensionnelle
3. Application du lemme local de Lovász pour traiter la coloration aléatoire

3. Propriété de paires ouvertes

Définition 2.13: Un groupe polonais compact infini Γ possède la propriété de paires ouvertes si pour toute famille finie complète P₀,...,Pₙ₋₁, il existe deux ensembles ouverts disjoints A₀,A₁ qui dominent tous les Pᵢ.

Lemme 2.14: Les groupes polonais compacts infinis de dimension finie possèdent la propriété de paires ouvertes.

Points d'innovation technique

1. Application de la théorie de la dimension: Première application systématique de la théorie de la dimension topologique au problème des partitions domatiques, réalisant des partitions d'ensembles ouverts par contrôle de la dimension des frontières
2. Traitement unifié de la mesure et de la catégorie: Développement d'un cadre technique traitant simultanément les versions théorie de la mesure et catégorie de Baire
3. Structure spéciale des graphes de Schreier: Utilisation des propriétés spéciales de l'action de groupe pour transformer les problèmes de graphes abstraits en problèmes de théorie des groupes

Résultats principaux

Théorèmes fondamentaux

Théorème 1.1 (Corollaire 2.18): Soit Γ un groupe polonais compact de dimension finie, S⊆Γ un sous-ensemble. Alors Sch(Γ,S,Γ) admet une partition domatique ℵ₀ d'ensembles ouverts si et seulement s'il admet une partition domatique ℵ₀ mesurable au sens de Baire si et seulement si S⊆Γ est non dénombrable.

Théorème 1.2 (Corollaire 2.19): Soit S⊆ℝⁿ. Alors Sch(ℝⁿ,S,ℝⁿ) admet une partition domatique ℵ₀ d'ensembles ouverts ou mesurable au sens de Baire si et seulement si S est non dénombrable ou non borné.

Théorème 1.3 (Corollaire 3.6): Soit Γ un groupe polonais, μ une mesure de probabilité borélienne sur Γ, S⊆Γ un sous-ensemble dénombrable infini. Alors Sch(Γ,S,Γ) admet une partition domatique ℵ₀ mesurable au sens de μ.

Résultats d'application

Théorème 1.5 (Corollaire 2.29): Soit P⊆ℝⁿ un sous-ensemble fermé parfait non vide. Alors il existe 2^ℵ₀ familles de sous-ensembles fermés deux à deux disjoints {Cᵢ:i<2^ℵ₀} telles que P+Cᵢ=ℝⁿ et Cᵢ+Cⱼ=ℝⁿ pour tous i,j<2^ℵ₀.

Résultats négatifs

Théorème 4.3: Il existe un graphe borélien acyclique ℵ₀-régulier non orienté totalement cyclique G sur un espace polonais qui n'admet pas de partition domatique 3 mesurable au sens de Baire.

Théorème 4.5 (Weilacher): Il existe un graphe borélien simple acyclique non orienté ℵ₀-régulier qui n'admet pas de partition domatique d'arêtes 2 symétrique et mesurable au sens de Borel.

Détails techniques

Technique de contrôle de la dimension

Par la construction inductive du lemme 2.8, pour un espace polonais X et des sous-ensembles fermés M₀,...,Mᵣ₋₁, on peut construire un ensemble ouvert U tel que la dimension de ∂U∩Mᵢ soit strictement inférieure à celle de Mᵢ. Ceci est le cœur technique de toute la théorie.

Algorithme glouton

Pour les graphes boréliens lisses, on peut utiliser un algorithme glouton pour construire une partition domatique ℵ₀ mesurable au sens de Borel. L'algorithme choisit à chaque étape le premier voisin non coloré du sommet courant pour le colorer.

Méthode probabiliste

En utilisant la version borélienne du lemme local de Lovász, on peut construire des partitions domatiques mesurables sur les graphes satisfaisant certaines conditions.

Travaux connexes

Théorie classique des partitions domatiques

• Résultats de Zelinka sur les hypercubes finis
• Application de la méthode probabiliste aux partitions domatiques

Combinatoire descriptive des graphes

• Travaux de synthèse de Kechris-Marks
• Problèmes de coloration sur les graphes boréliens
• Méthodes théorie de la mesure et catégorie de Baire

Contexte théorique des groupes

• Théorie des groupes polonais
• Propriétés des graphes de Schreier
• Mesurabilité des actions de groupes

Conclusion et discussion

Conclusions principales

1. Pour les groupes polonais compacts de dimension finie, l'existence de partitions domatiques ℵ₀ continues ou mesurables au sens de Baire est entièrement déterminée par les propriétés topologiques de l'ensemble générateur
2. Les partitions domatiques ℵ₀ mesurables au sens de la théorie de la mesure possèdent une existence universelle
3. La théorie de la dimension est un outil efficace pour traiter les problèmes de partitions domatiques

Limitations

1. Le cas de dimension infinie reste ouvert (Problème 2.20)
2. Les résultats sur les graphes localement finis sont relativement limités
3. Le problème d'existence des partitions domatiques finies mesurables au sens de Borel est complexe

Directions futures

1. Étude des partitions domatiques sur les groupes polonais compacts de dimension infinie
2. Développement de techniques plus générales de contrôle de la dimension
3. Exploration des connexions avec d'autres problèmes d'optimisation combinatoire

Évaluation approfondie

Avantages

1. Profondeur théorique: Combinaison organique de plusieurs branches mathématiques, établissant des connexions théoriques profondes
2. Innovation technique: L'application de la théorie de la dimension aux partitions domatiques est entièrement nouvelle
3. Complétude des résultats: Fourniture d'une caractérisation complète du problème, incluant résultats positifs et négatifs
4. Valeur applicative: Les applications à la théorie des ensembles sommes démontrent l'applicabilité générale de la méthode

Insuffisances

1. Complexité technique: Les techniques de preuve sont considérablement complexes, ce qui peut limiter l'accessibilité des résultats
2. Problèmes ouverts: Des questions importantes comme le cas de dimension infinie restent non résolues
3. Complexité computationnelle: Aucune discussion sur la complexité des algorithmes de construction

Influence

Cet article exerce une influence importante dans le domaine de la combinatoire descriptive des graphes, fournissant de nouveaux outils techniques et directions de recherche. La méthode de théorie de la dimension pourrait trouver des applications dans d'autres problèmes de théorie des graphes.

Scénarios d'application

Cette méthode s'applique à:

1. Problèmes combinatoires sur les graphes possédant une structure de groupe
2. Problèmes d'optimisation combinatoire infinie nécessitant de considérer la mesurabilité
3. Problèmes géométriques sur les groupes topologiques

Références

L'article cite 35 références importantes couvrant les domaines classiques et contemporains de la théorie descriptive des ensembles, théorie des groupes topologiques, théorie des graphes et combinatoire.