Sur l'estimation de l'entropie résiduelle de Pauling pour les graphes réguliers de degré croissant

Informations fondamentales

• ID de l'article: 2509.20671
• Titre: On Pauling's residual entropy estimate for regular graphs with growing degree
• Auteurs: Mahdieh Hasheminezhad (Université de Yazd), Mikhail Isaev (UNSW Sydney), Brendan D. McKay (Université nationale australienne), Rui-Ray Zhang
• Classification: math.CO (Mathématiques combinatoires)
• Date de publication: 5 novembre 2025 (arXiv v2)
• Lien de l'article: https://arxiv.org/abs/2509.20671

Résumé

En 1935, Pauling a proposé une estimation du nombre d'orientations eulériennes de graphes lors de l'étude du comportement théorique de la glace d'eau. Le logarithme du nombre d'orientations eulériennes divisé par le nombre de sommets est appelé entropie résiduelle. Dans des travaux antérieurs, les auteurs ont conjecturé que l'entropie résiduelle de séquences de graphes réguliers de degré croissant est asymptotiquement égale à l'estimation de Pauling. Cet article prouve cette conjecture sous des contraintes sur le nombre de cycles courts. Ces contraintes sont satisfaites sous des conditions de valeurs propres faibles et s'appliquent aux séquences de graphes de circonférence croissante et aux produits cartésiens répétés (comme les hypercubes).

Contexte et motivation de la recherche

1. Problème de recherche

Cet article étudie le problème du comptage des orientations eulériennes (Eulerian orientations) de graphes. Pour un graphe d-régulier G (d pair), une orientation eulérienne est une orientation des arêtes telle que le degré entrant égale le degré sortant pour chaque sommet. L'entropie résiduelle est définie comme: $\rho(G) := \frac{1}{n}\log EO(G)$ où EO(G) est le nombre d'orientations eulériennes et n est le nombre de sommets.

2. Importance du problème

• Contexte physique: L'entropie résiduelle joue un rôle important dans les modèles de glace (ice-type models) de la physique statistique, liée au nombre d'états microscopiques des cristaux de glace d'eau
• Signification mathématique: Pour certains réseaux spécifiques (réseau carré, réseau triangulaire, monocouche de glace hexagonale), la valeur exacte de l'entropie résiduelle est connue, mais le comportement asymptotique pour les graphes généraux reste un problème ouvert
• Valeur théorique: Établit des connexions entre les mathématiques combinatoires, la physique statistique et la théorie des probabilités

3. Estimation de Pauling

Pauling a proposé en 1935 une estimation heuristique: en supposant que chaque arête est orientée aléatoirement de manière indépendante, la probabilité que le sommet i ait un degré entrant égal au degré sortant est $2^{-d}\binom{d}{d/2}$. Si les événements pour les n sommets sont indépendants, on obtient: $\hat{\rho}(G) = \log\binom{d}{d/2} - \frac{d}{2}\log 2$

Lieb et Wu ont prouvé que pour tout graphe: $\rho(G) \geq \hat{\rho}(G)$

4. Limitations des recherches existantes

• Les résultats antérieurs (Isaev, McKay, Zhang 5) ne s'appliquent qu'aux graphes possédant de bonnes propriétés d'expansion et $d \geq \log^8 n$
• Les résultats sur les graphes aléatoires (6) dépendent de propriétés à haute probabilité
• Le résultat de Las Vergnas 7 exige que la circonférence croisse plus vite que $\log d$

5. Motivation de la recherche

Conjecture 1.1: Pour une séquence de graphes d-réguliers G(n), si l'entier pair $d = d(n) \to \infty$, alors $\rho(G) = \hat{\rho}(G) + o(1)$

L'objectif de cet article est de prouver cette conjecture sous des conditions plus faibles.

Contributions principales

1. Théorème principal (Théorème 2.1): Prouve la Conjecture 1.1 sous des contraintes sur le nombre de cycles courts fermés:
   • Il existe $\ell_{max} = \omega(\log d)$ et une constante C > 0
   • Pour tous $3 \leq \ell \leq \ell_{max}$: $c_\ell(G) \leq Ce^{-(l+1)}d^{\ell-1}n$
2. Corollaire sur les conditions de valeurs propres (Corollaire 2.2): Si au plus $nd^{-\omega(1)}$ valeurs propres se situent en dehors de $[-d^{1-\delta}, d^{1-\delta}]$ (pour une certaine constante δ > 0), alors la conjecture est vraie
3. Corollaire sur les conditions de circonférence (Corollaire 2.3): Pour les séquences de graphes d-réguliers avec $g \to \infty$, la conjecture est vraie (sans exiger $d \to \infty$)
4. Corollaire sur les produits cartésiens (Corollaire 2.4): Pour les produits cartésiens $G_t = H_1^{(t)} \square \cdots \square H_t^{(t)}$, la conjecture est vraie lorsque la somme des carrés des degrés satisfait $\sum_{i=1}^t (h_i^{(t)})^2 = O(d_t^{2-\delta})$, s'appliquant particulièrement aux hypercubes $Q_d$
5. Innovation technique: Transforme le problème en analyse de la fonction génératrice des moments du nombre de cycles fermés induits par des partitions eulériennes aléatoires

Explication détaillée de la méthode

Définition de la tâche

Étant donné un graphe d-régulier G (d pair), calculer l'entropie résiduelle $\rho(G) = \frac{1}{n}\log EO(G)$ et prouver qu'elle est asymptotiquement égale à l'estimation de Pauling $\hat{\rho}(G)$.

Cadre de la méthode principale

1. Représentation par partitions eulériennes

Définition: Une partition eulérienne P est une partition des arêtes du graphe en plusieurs cycles fermés. L'appairage des arêtes de chaque sommet détermine de manière unique une partition eulérienne.

Formule clé: $\rho(G) = \hat{\rho}(G) + \frac{1}{n}\log \mathbb{E} 2^{|T(P)|}$ où P est une partition eulérienne uniformément aléatoire et T(P) est l'ensemble des cycles fermés induits par P.

Équivalence: La conjecture est équivalente à prouver que $\mathbb{E} 2^{|T(P)|} = e^{o(n)}$

2. Stratégie de décomposition des cycles fermés

Définir $k = \lfloor\min\{\ell_{max}/2, \log^2 d\}\rfloor$, diviser les cycles fermés en:

• Cycles fermés longs $L_k(P)$: nombre de cycles fermés contenant plus de k sommets distincts
• Cycles fermés courts $S_k(P)$: nombre de cycles fermés contenant au plus k sommets distincts

Utiliser l'inégalité de Hölder: $\mathbb{E} 2^{|T(P)|} = \mathbb{E} 2^{L_k(P)+S_k(P)} \leq \left(\mathbb{E} 2^{\frac{7}{2}L_k(P)}\right)^{2/7}\left(\mathbb{E} 2^{\frac{7}{5}S_k(P)}\right)^{5/7}$

Composantes techniques

3. Contrôle des cycles fermés longs (Lemme 3.4)

Lemme clé (Lemme 3.1): Pour tout entier pair m et λ ≥ 0, $\mathbb{E} e^{\lambda X(m)} \leq (Bm)^{(e^\lambda-1)/2}$ où $X(m)$ est la somme de variables aléatoires de Bernoulli indépendantes de paramètres $1/(2j-1)$ (j=1,...,m/2).

Indépendance des appairages (Lemme 3.2): Dans un appairage aléatoire, le nombre de cycles fermés distincts passant par le sommet v suit la distribution X(m) et est indépendant de l'appairage des autres sommets.

Borne de la fonction génératrice des moments (Lemme 3.3): Pour un sous-ensemble U de sommets, $\mathbb{E} e^{\lambda Y(U)} = d^{O(|U|)}$

Borne finale: En choisissant un sous-ensemble aléatoire $|U| = \lfloor n/k\rfloor$, en utilisant $L_k \leq 2Y(U)$ avec probabilité au moins 1/2, on obtient: $\mathbb{E} e^{\lambda L_k} \leq (edk)^{O(n/k)} = e^{o(n)}$

4. Contrôle des cycles fermés courts (Lemme 4.5)

Utiliser la méthode de commutation (Switching method) (Théorème 4.1) — un outil puissant de comptage combinatoire.

Définition de la commutation: Étant donnée une partition eulérienne P et un cycle fermé T, une T-commutation modifie l'appairage à chaque sommet traversé par T:

• Le sommet v est visité t fois par T, correspondant aux paires d'arêtes $(e_1,e_1'),\ldots,(e_t,e_t')$
• Sélectionner t paires d'arêtes supplémentaires $(e_{t+1},e_{t+1}'),\ldots,(e_{2t},e_{2t}')$
• Remplacer par le nouvel appairage $\{e_1,e_{t+1}\},\ldots,\{e_t,e_{2t}\}$ et $\{e_1',e_{t+1}'\},\ldots,\{e_t',e_{2t}'\}$

Graphe de commutation: Construire un multigraphe orienté Γ:

• Sommets: $\mathbf{m} = (m_3,\ldots,m_L)$, représentant les classes de partitions eulériennes ayant exactement $m_\ell$ cycles fermés de longueur ℓ
• Arêtes: une arête orientée de couleur ℓ de $(\mathbf{m},\mathbf{m}')$ représente l'existence d'une ℓ-commutation de C(m) vers C(m')

Estimation clé (Lemme 4.3):

• Nombre de ℓ-commutations à partir de P ∈ C(m): $\geq \|\mathbf{m}\|_1(d-2L)^\ell/L$
• Nombre de ℓ-commutations atteignant P' ∈ C(m'): $\leq c_{k,\ell}$

Fonction de poids: $\hat{\alpha}(e) \leq \frac{2c_{k,\ell}L^2}{d^\ell m}$

Application du Théorème 4.1: Définir $M_0 := 2CnL^2/d, \quad Y = \bigcup_{m>M} C_m, \quad Z = \bigcup_{m\leq M_0} C_m$

Puisque $\hat{\alpha}(e) < 1/2$ pour toutes les arêtes avec $\|\mathbf{m}\|_1 > M_0$, on obtient: $|Y| \leq 2e^{-M+M_0}|Z|$

Borne de probabilité de queue: $\mathbb{P}(S_k(P) > M) \leq 2e^{-M+M_0}$

Borne des moments: Par représentation intégrale, $\mathbb{E} e^{\lambda S_k(P)} \leq e^{\lambda M_0} + \frac{2e^{\lambda M_0}}{1-\lambda} = e^{o(n)}$ où $\lambda = \frac{7}{5}\log 2 \approx 0.97 < 1$.

Points d'innovation technique

1. Subtilité de la stratégie de décomposition: Par le choix de la valeur k équilibrant les contributions des cycles longs et courts, l'utilisation de l'inégalité de Hölder avec les exposants choisis (7/2 et 7/5) est soigneusement conçue
2. Application innovante de la méthode de commutation:
   • Transforme le problème de comptage des partitions eulériennes en problème de flux sur un graphe orienté
   • Utilise la contrainte sur le nombre de cycles courts pour contrôler les poids de commutation
   • Obtient la décroissance exponentielle de la probabilité de queue via le Théorème 4.1
3. Affaiblissement des conditions:
   • De $d \geq \log^8 n$ affaibli à $d \to \infty$
   • De propriétés d'expansion fortes affaiblies à contraintes sur le nombre de cycles courts
   • Les conditions de valeurs propres ne nécessitent que $nd^{-\omega(1)}$ valeurs propres aberrantes
4. Cadre unifié: Traite simultanément plusieurs cas: graphes de circonférence croissante, graphes avec contraintes spectrales, produits cartésiens, etc.

Configuration expérimentale

Nature de la preuve théorique

Cet article est un article purement théorique qui ne contient pas d'expériences numériques ou informatiques. Tous les résultats sont des preuves mathématiques rigoureuses.

Exemples d'application

L'article vérifie la conjecture sur les classes de graphes suivantes via des corollaires:

1. Graphes de circonférence croissante (Corollaire 2.3)
2. Graphes avec contraintes spectrales (Corollaire 2.2)
3. Hypercubes $Q_d$ (d pair)
4. Produits cartésiens itérés: convergence locale vers des réseaux de dimension supérieure
5. Graphes réguliers aléatoires (résultats cités de 6)

Résultats expérimentaux

Résultats principaux

Vérification des conditions du Théorème 2.1:

1. Graphes avec circonférence g → ∞:
   • Le nombre de cycles fermés de longueur ℓ < g est zéro, satisfaisant automatiquement les conditions
   • La conjecture est vraie même pour d = O(1)
2. Graphes avec contraintes de valeurs propres:
   • Le nombre de promenades fermées $\leq \sum_i \lambda_i^\ell$
   • Si au plus $nd^{-f(n)}$ valeurs propres se situent en dehors de $[-d^{1-\delta}, d^{1-\delta}]$
   • En choisissant $\ell_{max} = \frac{1}{2}f(n)\log d$, les conditions sont satisfaites
3. Produits cartésiens:
   • Utilise l'inégalité de Hoeffding pour contrôler la distribution des valeurs propres
   • Pour $\sum_i (h_i^{(t)})^2 = O(d_t^{2-\delta})$, les conditions sont satisfaites
   • Hypercubes: $h_i = 1$, satisfaisant $\sum h_i^2 = t = o(d_t^2)$

Résultats techniques

Borne des cycles fermés longs (Lemme 3.4): $\mathbb{E} e^{\lambda L_k(P)} = e^{o(n)}, \quad \forall \lambda \geq 0, \, k \gg \log d$

Borne des cycles fermés courts (Lemme 4.5): $\mathbb{E} 2^{\frac{7}{5}S_k(P)} = e^{o(n)}$

Chaîne d'inégalités clés