Sulla stima dell'entropia residua di Pauling per grafi regolari con grado crescente

Informazioni di base

• ID articolo: 2509.20671
• Titolo: On Pauling's residual entropy estimate for regular graphs with growing degree
• Autori: Mahdieh Hasheminezhad (Yazd University), Mikhail Isaev (UNSW Sydney), Brendan D. McKay (Australian National University), Rui-Ray Zhang
• Classificazione: math.CO (Matematica combinatoria)
• Data di pubblicazione: 5 novembre 2025 (arXiv v2)
• Link articolo: https://arxiv.org/abs/2509.20671

Riassunto

Nel 1935, Pauling propose una stima del numero di orientamenti euleriani di grafi durante lo studio del comportamento teorico del ghiaccio d'acqua. Il logaritmo del numero di orientamenti euleriani diviso per il numero di vertici è denominato entropia residua. In articoli precedenti, gli autori hanno congetturato che l'entropia residua di sequenze di grafi regolari con grado crescente sia asintoticamente uguale alla stima di Pauling. Questo articolo dimostra tale congettura sotto vincoli sul numero di cicli brevi. Questi vincoli valgono sotto deboli condizioni di autovalori e si applicano a sequenze di grafi con circonferenza crescente e prodotti cartesiani ripetuti (come gli ipercubi).

Contesto di ricerca e motivazione

1. Problema di ricerca

Questo articolo studia il problema del conteggio degli orientamenti euleriani (Eulerian orientations) di grafi. Per un grafo d-regolare G (d pari), un orientamento euleriano è un orientamento degli spigoli tale che ogni vertice abbia grado entrante uguale al grado uscente. L'entropia residua è definita come: $\rho(G) := \frac{1}{n}\log EO(G)$ dove EO(G) è il numero di orientamenti euleriani e n è il numero di vertici.

2. Importanza del problema

• Sfondo fisico: L'entropia residua ha importanza significativa nei modelli di ghiaccio (ice-type models) della fisica statistica, correlata al numero di microstati dei cristalli di ghiaccio d'acqua
• Significato matematico: Per reticoli specifici (reticolo quadrato, reticolo triangolare, monostrato di ghiaccio esagonale), il valore esatto dell'entropia residua è noto, ma il comportamento asintotico per grafi generali rimane un problema aperto
• Valore teorico: Connette la matematica combinatoria, la fisica statistica e la teoria della probabilità

3. Stima di Pauling

Pauling nel 1935 propose una stima euristica: assumendo che ogni spigolo sia orientato casualmente in modo indipendente, la probabilità che il vertice i abbia grado entrante uguale al grado uscente è $2^{-d}\binom{d}{d/2}$. Se gli eventi per n vertici fossero indipendenti, si otterrebbe: $\hat{\rho}(G) = \log\binom{d}{d/2} - \frac{d}{2}\log 2$

Lieb e Wu hanno dimostrato che per qualsiasi grafo: $\rho(G) \geq \hat{\rho}(G)$

4. Limitazioni della ricerca esistente

• I risultati precedenti (Isaev, McKay, Zhang 5) valgono solo per grafi con buone proprietà di espansione e $d \geq \log^8 n$
• I risultati su grafi casuali (6) dipendono da proprietà ad alta probabilità
• Il risultato di Las Vergnas 7 richiede che la circonferenza cresca più velocemente di $\log d$

5. Motivazione della ricerca

Congettura 1.1: Per una sequenza di grafi d-regolari G(n), se l'intero pari $d = d(n) \to \infty$, allora $\rho(G) = \hat{\rho}(G) + o(1)$

L'obiettivo di questo articolo è provare tale congettura sotto condizioni più deboli.

Contributi principali

1. Teorema principale (Theorem 2.1): Dimostra la Congettura 1.1 sotto vincoli sul numero di tracce chiuse brevi, con condizioni:
   • Esiste $\ell_{max} = \omega(\log d)$ e una costante C > 0
   • Per tutti $3 \leq \ell \leq \ell_{max}$: $c_\ell(G) \leq Ce^{-(l+1)}d^{\ell-1}n$
2. Corollario su condizioni di autovalori (Corollary 2.2): Se al massimo $nd^{-\omega(1)}$ autovalori si trovano al di fuori di $[-d^{1-\delta}, d^{1-\delta}]$ (per una costante δ > 0), allora la congettura vale
3. Corollario su condizioni di circonferenza (Corollary 2.3): Per sequenze di grafi d-regolari con circonferenza $g \to \infty$, la congettura vale (non richiede $d \to \infty$)
4. Corollario su prodotti cartesiani (Corollary 2.4): Per prodotti cartesiani $G_t = H_1^{(t)} \square \cdots \square H_t^{(t)}$, la congettura vale quando la somma dei quadrati dei gradi soddisfa $\sum_{i=1}^t (h_i^{(t)})^2 = O(d_t^{2-\delta})$, in particolare per ipercubi $Q_d$
5. Innovazione tecnica: Trasforma il problema in un'analisi della funzione generatrice dei momenti del numero di tracce chiuse indotte da partizioni euleriane casuali

Spiegazione dettagliata dei metodi

Definizione del compito

Dato un grafo d-regolare G (d pari), calcolare l'entropia residua $\rho(G) = \frac{1}{n}\log EO(G)$ e provare che è asintoticamente uguale alla stima di Pauling $\hat{\rho}(G)$.

Struttura del metodo principale

1. Rappresentazione mediante partizioni euleriane

Definizione: Una partizione euleriana P è una partizione degli spigoli del grafo in diverse tracce chiuse. L'accoppiamento di spigoli di ogni vertice determina univocamente una partizione euleriana.

Formula chiave: $\rho(G) = \hat{\rho}(G) + \frac{1}{n}\log \mathbb{E} 2^{|T(P)|}$ dove P è una partizione euleriana uniformemente casuale e T(P) è l'insieme di tracce chiuse indotte da P.

Equivalenza: La congettura è equivalente a provare $\mathbb{E} 2^{|T(P)|} = e^{o(n)}$

2. Strategia di decomposizione delle tracce chiuse

Definire $k = \lfloor\min\{\ell_{max}/2, \log^2 d\}\rfloor$, dividere le tracce chiuse in:

• Tracce lunghe $L_k(P)$: numero di tracce chiuse contenenti più di k vertici distinti
• Tracce brevi $S_k(P)$: numero di tracce chiuse contenenti al massimo k vertici distinti

Utilizzare la disuguaglianza di 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}$

Componenti tecniche

3. Controllo delle tracce lunghe (Lemma 3.4)

Lemma chiave (Lemma 3.1): Per m pari e λ ≥ 0, $\mathbb{E} e^{\lambda X(m)} \leq (Bm)^{(e^\lambda-1)/2}$ dove $X(m)$ è la somma di variabili casuali di Bernoulli indipendenti con parametri $1/(2j-1)$ (j=1,...,m/2).

Indipendenza degli accoppiamenti (Lemma 3.2): Negli accoppiamenti casuali, il numero di tracce chiuse distinte attraverso il vertice v segue la distribuzione X(m) ed è indipendente dagli accoppiamenti di altri vertici.

Limite della funzione generatrice dei momenti (Lemma 3.3): Per un sottoinsieme di vertici U, $\mathbb{E} e^{\lambda Y(U)} = d^{O(|U|)}$

Limite finale: Scegliere un sottoinsieme casuale di $|U| = \lfloor n/k\rfloor$, utilizzare il fatto che $L_k \leq 2Y(U)$ con probabilità almeno 1/2, ottenere: $\mathbb{E} e^{\lambda L_k} \leq (edk)^{O(n/k)} = e^{o(n)}$

4. Controllo delle tracce brevi (Lemma 4.5)

Utilizzare il metodo di switching (Theorem 4.1) — uno strumento potente di conteggio combinatorio.

Definizione di switching: Data una partizione euleriana P e una traccia chiusa T, uno T-switching modifica l'accoppiamento in ogni vertice attraversato da T:

• Il vertice v è visitato t volte da T, corrispondente alle coppie di spigoli $(e_1,e_1'),\ldots,(e_t,e_t')$
• Selezionare t coppie di spigoli aggiuntive $(e_{t+1},e_{t+1}'),\ldots,(e_{2t},e_{2t}')$
• Sostituire con il nuovo accoppiamento $\{e_1,e_{t+1}\},\ldots,\{e_t,e_{2t}\}$ e $\{e_1',e_{t+1}'\},\ldots,\{e_t',e_{2t}'\}$

Grafo di switching: Costruire un multigrafo orientato Γ:

• Vertici: $\mathbf{m} = (m_3,\ldots,m_L)$, rappresentando classi di partizioni euleriane con esattamente $m_\ell$ tracce chiuse di lunghezza ℓ
• Spigoli: uno spigolo orientato colorato ℓ da $(\mathbf{m},\mathbf{m}')$ rappresenta l'esistenza di uno ℓ-switching da C(m) a C(m')

Stima chiave (Lemma 4.3):

• Numero di ℓ-switching da P ∈ C(m): $\geq \|\mathbf{m}\|_1(d-2L)^\ell/L$
• Numero di ℓ-switching verso P' ∈ C(m'): $\leq c_{k,\ell}$

Funzione di peso: $\hat{\alpha}(e) \leq \frac{2c_{k,\ell}L^2}{d^\ell m}$

Applicazione di Theorem 4.1: Definire $M_0 := 2CnL^2/d, \quad Y = \bigcup_{m>M} C_m, \quad Z = \bigcup_{m\leq M_0} C_m$

Poiché $\hat{\alpha}(e) < 1/2$ per tutti gli spigoli con $\|\mathbf{m}\|_1 > M_0$, ottenere: $|Y| \leq 2e^{-M+M_0}|Z|$

Limite di probabilità della coda: $\mathbb{P}(S_k(P) > M) \leq 2e^{-M+M_0}$

Limite dei momenti: Attraverso la rappresentazione integrale, $\mathbb{E} e^{\lambda S_k(P)} \leq e^{\lambda M_0} + \frac{2e^{\lambda M_0}}{1-\lambda} = e^{o(n)}$ dove $\lambda = \frac{7}{5}\log 2 \approx 0.97 < 1$.

Punti di innovazione tecnica

1. Eleganza della strategia di decomposizione: Attraverso la scelta di k si bilancia il contributo delle tracce lunghe e brevi, la scelta degli esponenti della disuguaglianza di Hölder (7/2 e 7/5) è attentamente progettata
2. Applicazione innovativa del metodo di switching:
   • Trasforma il problema di conteggio delle partizioni euleriane in un problema di flusso su grafi orientati
   • Utilizza il vincolo sul numero di tracce brevi per controllare i pesi di switching
   • Attraverso Theorem 4.1 ottiene il decadimento esponenziale della probabilità della coda
3. Indebolimento delle condizioni:
   • Da $d \geq \log^8 n$ a $d \to \infty$
   • Da forte espansività a vincoli sul numero di tracce brevi
   • La condizione di autovalori richiede solo $nd^{-\omega(1)}$ outlier
4. Struttura unificata: Tratta simultaneamente circonferenza crescente, vincoli di autovalori, prodotti cartesiani e altre situazioni

Impostazione sperimentale

Proprietà della dimostrazione teorica

Questo articolo è un articolo puramente teorico e non contiene esperimenti numerici o computazionali. Tutti i risultati sono dimostrazioni matematiche rigorose.

Esempi di applicazione

L'articolo verifica la congettura attraverso corollari su le seguenti classi di grafi:

1. Grafi con circonferenza crescente (Corollary 2.3)
2. Grafi con vincoli spettrali (Corollary 2.2)
3. Ipercubi $Q_d$ (d pari)
4. Prodotti cartesiani iterati: convergono localmente a reticoli di dimensione superiore
5. Grafi regolari casuali (risultati citati da 6)

Risultati sperimentali

Risultati principali

Verifica delle condizioni di Theorem 2.1:

1. Grafi con circonferenza g → ∞:
   • Il numero di tracce chiuse di lunghezza ℓ < g è zero, soddisfa automaticamente le condizioni
   • Vale anche per d = O(1)
2. Grafi con vincoli di autovalori:
   • Il numero di cammini chiusi $\leq \sum_i \lambda_i^\ell$
   • Se al massimo $nd^{-f(n)}$ autovalori si trovano al di fuori di $[-d^{1-\delta}, d^{1-\delta}]$
   • Scegliendo $\ell_{max} = \frac{1}{2}f(n)\log d$, le condizioni sono soddisfatte
3. Prodotti cartesiani:
   • Utilizzare la disuguaglianza di Hoeffding per controllare la distribuzione degli autovalori
   • Per $\sum_i (h_i^{(t)})^2 = O(d_t^{2-\delta})$, le condizioni sono soddisfatte
   • Ipercubi: $h_i = 1$, soddisfa $\sum h_i^2 = t = o(d_t^2)$

Risultati tecnici

Limite delle tracce lunghe (Lemma 3.4): $\mathbb{E} e^{\lambda L_k(P)} = e^{o(n)}, \quad \forall \lambda \geq 0, \, k \gg \log d$

Limite delle tracce brevi (Lemma 4.5): $\mathbb{E} 2^{\frac{7}{5}S_k(P)} = e^{o(n)}$

Catena di disuguaglianze chiave