Abondance des digraphes $z$-Šoltés

Informations fondamentales

• ID de l'article: 2501.00102
• Titre: Abondance des digraphes $z$-Šoltés
• Auteur: Stijn Cambie (KU Leuven Campus Kulak-Kortrijk)
• Classification: math.CO (Mathématiques combinatoires)
• Date de soumission: 30 décembre 2024
• Lien de l'article: https://arxiv.org/abs/2501.00102

Résumé

Cet article démontre l'existence d'une infinité de digraphes de Šoltés, qui constituent l'analogue dirigé des graphes de Šoltés. De plus, il fournit un exemple de digraphe de Šoltés possédant un groupe d'automorphismes trivial.

Contexte et motivation de la recherche

Contexte du problème

1. Définition des graphes de Šoltés: Originaires de l'article de Šoltés de 1991, les graphes de Šoltés sont des graphes dont la distance totale diminue d'une valeur fixe exactement lors de la suppression de n'importe quel sommet.
2. Généralisation aux digraphes: Cet article étend ce concept aux digraphes, en définissant un digraphe $z$-Šoltés comme un digraphe dont la distance totale diminue d'exactement $z$ lors de la suppression de n'importe quel sommet.
3. Cas particuliers: Lorsque $z=0$, on parle de digraphe de Šoltés; lorsque $z≤0$, on parle de digraphe de Šoltés négatif.

Motivation de la recherche

1. Perfectionnement théorique: Répondre à la question 13 de la référence 5 concernant l'existence d'une infinité de graphes de Šoltés négatifs de degré minimum au moins 3.
2. Perspective des digraphes: Renforcer la compréhension du problème original en confirmant cette conjecture dans le cas des digraphes.
3. Preuve d'abondance: Démontrer non seulement l'existence d'une infinité de digraphes de Šoltés négatifs, mais aussi d'une infinité de digraphes de Šoltés.

Contributions principales

1. Théorème principal: Preuve que pour chaque entier $z$, il existe une infinité de digraphes $D$ tels que pour tout sommet $v$, on ait $W(D) - W(D \setminus v) = z$.
2. Infinité des digraphes de Šoltés: Comme corollaire du théorème principal, preuve de l'existence d'une infinité de digraphes de Šoltés.
3. Constructions explicites: Fourniture d'exemples concrets de digraphes de Šoltés, notamment $D(11,\{1\}) \cong C_{11}$ et $D(85,\{4\})$.
4. Exemple non-vertex-transitif: Construction d'un digraphe de Šoltés d'ordre 3306 possédant un groupe d'automorphismes trivial, ce qui réfute fortement l'analogue dirigé d'une conjecture connexe.

Détails méthodologiques

Définitions fondamentales

Définition 4: Pour un sous-ensemble $S \subseteq [n-2] = \{1,2,\ldots,n-2\}$, on définit le digraphe cyclique $D(n,S)$ avec ensemble de sommets $V = [n]$ et ensemble d'arcs dirigés: $E = \{(i, i-1) | i \in [n]\} \cup \{(i, i+k) | i \in [n], k \in S\}$ où les nombres sont interprétés modulo $n$.

Stratégie de construction

1. Cas de valeurs positives pour digraphes denses: La proposition 5 démontre que lorsque $\delta^-(D) + \delta^+(D) \geq n \geq 4$, on a $W(D) - W(D \setminus v) > 0$.
2. Cas de valeurs négatives pour digraphes creux: La proposition 6 démontre que lorsque $\max S \leq \frac{1}{9}n^{1/2}$ et $n$ est suffisamment grand, on a $W(D_{n,S}) - W(D_{n,S} \setminus v) < 0$.

Stratégie principale de preuve

La preuve se décompose en trois étapes clés:

Étape 1 (Affirmation 7): Choix de $n \sim 6m^2$ tel que $D(n,[m])$ satisfasse $z-9m \leq W(D) - W(D-v) \leq z-3$.

Étape 2 (Affirmation 8): Par suppression de certains grands éléments de $[m]$, construction de $D(n,[m-\ell] \cup \{m-1,m\})$ telle que la différence soit proche de $z$ et paire.

Étape 3: Par suppression précise d'un nombre approprié d'éléments impairs, obtention finale de $W(D) - W(D \setminus v) = z$.

Configuration expérimentale

Exemples concrets vérifiés

1. Exemples à petite échelle: $D(11,\{1\}) \cong C_{11}$ et $D(85,\{4\})$ sont tous deux des digraphes de Šoltés.
2. Construction à grande échelle: Construction d'un digraphe de Šoltés non-vertex-transitif d'ordre 3306 possédant un groupe d'automorphismes trivial.

Vérification computationnelle

Pour $D(85,\{4\})$, vérification que lors de la suppression du sommet $v$, la distance de ses voisins gauches à ses voisins droits passe de 2 à 22, illustrant la redistribution des distances.

Résultats expérimentaux

Résultats principaux

1. Preuve du théorème 1: Construction réussie d'une infinité de digraphes $z$-Šoltés pour tout entier $z$.
2. Exemples concrets:
   • $D(85,\{4\})$ est un digraphe de Šoltés concret
   • Construction d'un digraphe de Šoltés 2-régulier, biparti mais non-vertex-transitif d'ordre 960
   • Construction d'un digraphe de Šoltés d'ordre 3306 possédant un groupe d'automorphismes trivial

Vérification des détails techniques

L'annexe B contient des calculs détaillés des valeurs de paramètres spécifiques:

• Lorsque $a = 6m-1$, $r = m$: $W(D-v) - W(D) = \frac{7}{2}m^2 - O(m) > z$
• Lorsque $a = 6m-1$, $r = 0$: $W(D-v) - W(D) = -\frac{5}{2}m^2 - O(m) < z - 9m$

Travaux connexes

Développement historique

1. Travaux originaux de Šoltés: Première introduction du concept connexe par Šoltés en 1991
2. Applications en théorie des graphes: Recherches connexes sur l'indice de Wiener (distance totale)
3. Graphes vertex-transitifs: Analogue dirigé de la conjecture d'Adam et ses contre-exemples

Positionnement de la contribution de cet article

Cet article généralise la propriété de Šoltés de la théorie des graphes aux digraphes, et fournit une preuve systématique d'existence par la méthode de construction de digraphes cycliques.

Conclusions et discussion

Conclusions principales

1. Pour tout entier $z$, il existe une infinité de digraphes $z$-Šoltés
2. En particulier, il existe une infinité de digraphes de Šoltés (cas $z=0$)
3. Il existe des digraphes de Šoltés possédant un groupe d'automorphismes trivial, ce qui réfute fortement la conjecture connexe

Signification théorique

Ces découvertes renforcent l'intuition du cas graphique dans la référence 5, selon laquelle l'essence du problème réside dans la question extrémale de l'existence infinie des graphes de Šoltés négatifs. Si les graphes de Šoltés négatifs sont manifestement abondants, on peut s'attendre à ce que les graphes de Šoltés le soient également.

Directions futures

1. Étude du comptage exact des digraphes $z$-Šoltés non-isomorphes
2. Exploration de propriétés similaires dans d'autres classes de graphes
3. Étude des relations entre la propriété de Šoltés et d'autres paramètres de théorie des graphes

Évaluation approfondie

Avantages

1. Complétude théorique: Résolution systématique du problème de généralisation des graphes de Šoltés aux digraphes
2. Innovation méthodologique: Réalisation du contrôle précis des paramètres par construction ingénieuse de digraphes cycliques
3. Force des contre-exemples: Le contre-exemple construit possédant un groupe d'automorphismes trivial réfute fortement la conjecture connexe
4. Rigueur computationnelle: Les calculs détaillés en annexe garantissent la fiabilité des résultats

Points techniques remarquables

1. Stratégie de construction par étapes: Décomposition de la preuve d'existence complexe en trois étapes contrôlables
2. Optimisation des paramètres: Réalisation d'un équilibre optimal des paramètres par le choix $n \sim 6m^2$
3. Contrôle de la parité: Utilisation ingénieuse de la suppression d'éléments impairs pour réaliser un ajustement précis de la différence

Limitations

1. Complexité de la construction: Bien que l'existence soit prouvée, le processus de construction concrète est assez complexe
2. Problème de comptage: Le comptage exact des graphes non-isomorphes reste difficile
3. Portée applicative: Les résultats sont principalement théoriques, avec une valeur pratique limitée

Évaluation de l'impact

1. Contribution théorique: Fourniture d'une réponse complète au problème de Šoltés en théorie des graphes combinatoires dirigés
2. Valeur méthodologique: La méthode de construction de digraphes cycliques peut s'appliquer à d'autres problèmes similaires
3. Valeur de réfutation: La réfutation de la conjecture connexe possède une signification théorique importante

Références bibliographiques

L'article cite 10 références principales couvrant les travaux originaux sur les graphes de Šoltés, la recherche sur l'indice de Wiener, la théorie des graphes cycliques et les problèmes connexes d'optimisation combinatoire, reflétant le caractère systématique et complet de la recherche.