Structures pour graphes aléatoires avec structure
Contexte
[Vous pouvez ignorer ceci et passer immédiatement aux définitions.]
Les caractéristiques essentielles d'un graphe ou d'un réseau (aléatoire) sont:
la distribution des diplômes $p(d)$ (loi exponentielle, de Poisson ou de puissance)
le degré moyen $\bar{d}$
le coefficient de regroupement moyen $\bar{C}$
la distance moyenne $L$ et diamètre $D$
Des graphiques générés aléatoirement sont souvent nécessaires pour présenter la propriété du petit monde , c'est-à-dire$L\propto \log N$ et $\bar{C}$n'est «pas petit». Il existe plusieurs modèles de graphes aléatoires qui répondent à au moins une de ces conditions:
- Le modèle Watts-Strogatz (avec un réseau annulaire régulier sous-jacent)
- Le modèle Barabasi-Albert (avec attachement préféré)
- Le modèle de configuration (avec des séquences de degrés données, respectivement des distributions)
- Le modèle Newman (intégrant la structure communautaire )
Alors que le modèle Watts-Strogatz et le modèle Barabasi-Albert sont des modifications du modèle Erdős – Rényi , et le modèle Newman est une généralisation spécifique du modèle de configuration, je me demande s'il existe déjà un «méta-modèle» qui tente d'incorporer le le meilleur de tous ces modèles. (Demande de réference.)
En généralisant à la fois le modèle de Watts-Strogatz et de Newman, j'aimerais étudier les graphes aléatoires qui "interpolent entre une structure aléatoire proche des graphes ER et [un graphe régulier arbitraire] " (citation de Wikipedia ).
Pour cela, j'aimerais avoir sous la main une multitude de graphiques réguliers qui peuvent
être systématiquement symbolisé et énuméré,
être facilement générés à partir de leur symbole (c'est-à-dire de leurs matrices de contiguïté), et
possiblement avoir des expressions de forme fermée pour les caractéristiques du petit monde $L$ et $\bar{C}$
Les graphiques réguliers que j'ai en tête peuvent être expliqués le plus facilement par un exemple.
Définitions
Soit une configuration de sommet un graphe qui représente un sommet $\nu$ avec plusieurs voisins immédiats $\nu_0,\nu_2,\dots,\nu_{d-1}$ et un chemin le plus court (de longueur arbitraire) entre chaque paire de voisins consécutifs $\nu_i, \nu_{i+1}$. Une configuration de sommet peut être codifiée par le symbole$(n_1.n_2.\dots.n_k)^m$ qui dit, que $\nu$ a un diplôme $d = m \cdot k$ et est entouré d'un $m$-séquence périodique de $n_i$-faces resp. cycles les plus courts. (Ce n'est rien d'autre que la définition standard des configurations de sommets en géométrie dans le langage de la théorie des graphes.)
Exemple:

On dit qu'un sommet a une configuration de sommet donnée $\Gamma$ lorsque son voisinage avec un chemin le plus court entre voisins est isomorphe à $\Gamma$. On dit qu'un graphe a une configuration de sommets donnée$\Gamma$ lorsque tous ses sommets ont une configuration de sommets $\Gamma$. Une configuration de sommet est dite réalisable quand il y a un graphe qui la possède.
Considérons maintenant les graphes finis dans lesquels tous les sommets ont la même configuration de sommets.
Des questions
Toutes les configurations de sommets $\Gamma$réalisable par des graphes de taille plus ou moins arbitraire? Comment prouver ou réfuter cela?
Cela a à voir avec la question de savoir si toutes les configurations de sommets (au sens de la géométrie) qui ne définissent pas un pavage périodique de la sphère (c'est-à-dire un polyèdre régulier) définissent un pavage périodique du plan euclidien ou hyperbolique.S'il y a des configurations de vertex non réalisables: Comment vérifier si une configuration de vertex donnée est réalisable?
Fait un graphe avec une configuration de sommet donnée $\Gamma$ doit être vertex-transitive?
Puisque le nombre (égal) de sommets de deux graphes transitifs de sommets avec la même configuration de sommets ne garantit pas qu'ils sont isomorphes: Par quels moyens généraux leur "forme" peut-elle être définie, de sorte que deux graphes également définis doivent être isomorphes? (Pour un exemple: voir ci-dessous.)
Existe-t-il un moyen systématique de générer une matrice de contiguïté pour une configuration et une «forme» de sommet réalisables données?
Par «forme», je veux dire ce que Dolbilin et Schulte appellent «complexes de quartier (coronas)» dans leur article The Local Theorem for Monotypic Tilings .
Exemples
Considérez la configuration des sommets $(4)^4$ et une "forme" définie par des nombres $(4, 6)$


Lors de la liaison de sommets sur des côtés opposés de la forme, tous les sommets ont la même configuration de sommets $(4)^4$, de plus le graphe résultant est vertex-transitive:


On trouve le diamètre $D = 5$, coefficient de regroupement $\bar{C} = 0$, et distance moyenne $L =\frac{1}{23}(4\times 1 + 7 \times 2 + 7 \times 3 + 4 \times 4 + 1 \times 5) \approx 2.61$ pour lequel rechercher une expression explicite fermée ou récursive (selon $(n,m)$) semble faisable.
Pour la "forme"


avec la même configuration de sommets et le même nombre de sommets que nous trouvons $D = 5$ et distance moyenne $L =\frac{1}{23}(4\times 1 + 6 \times 2 + 6 \times 3 + 5 \times 4 + 2 \times 5) \approx 2.78$
Pour la "forme"


avec à peu près le même nombre de sommets que nous trouvons $D = 4$ et distance moyenne $L =\frac{1}{24}(4\times 1 + 8 \times 2 + 8 \times 3 + 4 \times 4 ) \approx 2.5$.
Si vous voulez un coefficient de cluster $\bar{C} = 1/2$ vous pouvez commencer par une configuration de sommet $(3.n)^m$, par exemple $(3.4)^2$:

Malheureusement, cette configuration n'est pas qualifiée car elle ne dalle pas un plan mais la sphère (donnant naissance au cuboctaèdre ). Alors tu dois choisir$(3.4)^3$au moins. Pour dessiner une belle "forme" d'une certaine taille qui peut être transformée en un graphe fini avec une configuration de sommet$(3.4)^m$, $m > 2$, nécessite une géométrie hyperbolique . Trouver une matrice de contiguïté est encore plus difficile, comme je suppose (voir question 5). Aussi le diamètre$D$ et distance moyenne $L$ (comme expressions fermées).
Alternativement, on peut ajouter un bord à la moitié de la $n\cdot m$ $4$-cycle (choisi au hasard) du $(4)^4$ graphique - réduisant ainsi le diamètre $D$ et distance moyenne $L$.
Réponses
La configuration de sommet suivante a une notation $(3.4.4.4)^1$ et devrait fournir des contre-exemples à la question 1 (existence de graphes de taille arbitraire) et à la question 3 (sommet-transitivité).

Il n'y a qu'un nombre fini de graphes qui réalisent cette configuration, et tous sont finis avec au plus 24 sommets. Exactement deux d'entre eux sont planaires, le graphique des bords du rhombicuboctaèdre (à gauche) et le graphique des bords du pseudo-rhombicuboctaèdre étroitement lié (à droite). Seul le premier est vertex-transitive.

Tous les autres graphes peuvent être obtenus à partir de ceux-ci en identifiant les sommets. Par exemple, l'identification des sommets antipodaux dans le graphe de gauche donne un "polyèdre projectif":

J'ai mis en évidence la configuration des sommets dans la bonne image car ce n'est pas évident dans ce dessin.
Je pense que ce sont tous les graphiques avec cette configuration. Je me trompe peut-être, mais il n'y a certainement pas de tels graphes avec plus de 24 sommets.
Plus généralement, vous pourriez être intéressé par le théorème local de
- "The Local Theorem for Monotypic Tilings" par Dolbilin et Schulte
qui concerne la question de savoir quand certaines restrictions locales impliquent une symétrie globale. Habituellement, cela donne l'unicité et la transitivité des sommets, mais cela ne s'applique que si la topologie est "simplement connectée" (donc, pour les pavages de la sphère, plan euclidien / hyperbolique, mais pas pour le tore, comme vous l'avez vu dans votre question que le graphique n'est pas unique pour$(4)^4$).
Au début de la section 3 (sous le théorème 3.1), ils déclarent que la configuration $(3.5.5.5)^1$peut être réalisé comme un graphe infini, mais pas comme un vertex-transitive. J'ai essayé de retracer cette affirmation, mais ils se réfèrent uniquement au livre "Tilings and Patterns" qui contient littéralement des milliers de pavages, et je n'ai pas été en mesure de trouver celui souhaité.
Enfin, la configuration suivante $(3.4.5)^1$ ne devrait pas du tout être réalisable:

Pour voir cela, notez que le graphe doit contenir une "face triangulaire" (puisque la configuration le fait). Chacun des trois bords de ce triangle est partagé soit avec un quadrilatère, soit avec un pentagone. Wlog suppose que deux arêtes sont partagées avec une quadrange. Mais ces deux arêtes partagent un sommet, et donc ce sommet ne peut pas être de type$(3.4.5)^1$.
En général, il semble assez délicat de distinguer les configurations réalisables des configurations non réalisables. En règle générale, il semble que les visages impairs posent un problème, tout comme ils l'ont fait dans l'exemple précédent. Donc, par exemple une configuration$(\mathbf 5.8.10)^1$ ne peut pas exister non plus pour la même raison, car il y a une face pentagonale qui délimite deux types différents de faces, et il n'y a pas de type de face répété à un sommet.
Puisque vous mentionnez (dans les commentaires) que vous êtes le plus intéressé $(3.n)^m$ (en supposant $n\ge 3$, $m\ge 2$):
Cette configuration existe toujours, est unique et vertex-transitive (en supposant une "topologie simplement connectée", que nous pouvons traduire par "le graphe est planaire").
C'est fini seulement pour $(3.3)^2$( octaèdre ),$(3.4)^2$( cuboctaèdre ) et$(3.5)^2$( icosidodécaèdre ). Vous pouvez le considérer comme "planaire" pour$\smash{(3.3)^3}$( carrelage triangulaire ) et$\smash{(3.6)^2}$( pavage trihexagonal ) et hyperbolique dans tous les autres cas.
L'unicité et la symétrie sont essentiellement une conséquence du théorème local (et du théorème d'extension connexe) mentionné précédemment. Mais en termes simples: si vous essayez de construire un graphe avec une telle configuration de sommets, et que vous partez de n'importe quel sommet, puis que vous essayez de terminer la configuration de vertex autour de l'un des autres sommets, vous ne pouvez le faire que d'une manière unique (vraiment, essayez-le sur papier). Étant donné que vous ne faites aucun choix dans aucune des étapes (éventuellement infinies), le résultat est unique.