Über Paulings Restentropie-Schätzung für reguläre Graphen mit wachsendem Grad

Grundinformationen

• Paper-ID: 2509.20671
• Titel: On Pauling's residual entropy estimate for regular graphs with growing degree
• Autoren: Mahdieh Hasheminezhad (Yazd University), Mikhail Isaev (UNSW Sydney), Brendan D. McKay (Australian National University), Rui-Ray Zhang
• Klassifizierung: math.CO (Kombinatorik)
• Veröffentlichungsdatum: 5. November 2025 (arXiv v2)
• Paper-Link: https://arxiv.org/abs/2509.20671

Zusammenfassung

1935 stellte Pauling bei der Untersuchung des theoretischen Verhaltens von Wassereis eine Schätzung für die Anzahl der Eulerschen Orientierungen von Graphen auf. Der Logarithmus der Anzahl der Eulerschen Orientierungen dividiert durch die Anzahl der Knoten wird als Restentropie bezeichnet. In früheren Arbeiten vermuteten die Autoren, dass die Restentropie asymptotisch gleich der Pauling-Schätzung für Sequenzen regulärer Graphen mit wachsendem Grad ist. Dieser Artikel beweist diese Vermutung unter Beschränkungen der Anzahl kurzer Zyklen. Diese Beschränkungen gelten unter schwachen Eigenwertbedingungen und sind auf Graphsequenzen mit wachsendem Umfang und wiederholte kartesische Produkte (wie Hyperwürfel) anwendbar.

Forschungshintergrund und Motivation

1. Forschungsfrage

Dieser Artikel untersucht das Zählproblem von Eulerschen Orientierungen (Eulerian orientations) von Graphen. Für einen d-regulären Graphen G (d gerade) ist eine Eulersche Orientierung eine Orientierung der Kanten, bei der der Eingangsgrad gleich dem Ausgangsgrad an jedem Knoten ist. Die Restentropie wird definiert als: $\rho(G) := \frac{1}{n}\log EO(G)$ wobei EO(G) die Anzahl der Eulerschen Orientierungen und n die Anzahl der Knoten ist.

2. Bedeutung des Problems

• Physikalischer Hintergrund: Die Restentropie hat große Bedeutung in Eismodellen (ice-type models) der statistischen Physik und ist mit der Anzahl der Mikrozustände von Wassereiskristallen verbunden
• Mathematische Bedeutung: Für spezifische Gitter (quadratisches Gitter, Dreiecksgitter, hexagonale Eislage) sind die genauen Werte der Restentropie bekannt, aber das asymptotische Verhalten für allgemeine Graphen bleibt ein offenes Problem
• Theoretischer Wert: Verbindet Kombinatorik, statistische Physik und Wahrscheinlichkeitstheorie

3. Pauling-Schätzung

Pauling schlug 1935 eine heuristische Schätzung vor: Angenommen, jede Kante wird unabhängig zufällig orientiert, dann ist die Wahrscheinlichkeit, dass der Eingangsgrad des Knotens i gleich dem Ausgangsgrad ist, $2^{-d}\binom{d}{d/2}$. Wenn die Ereignisse an n Knoten unabhängig sind, ergibt sich: $\hat{\rho}(G) = \log\binom{d}{d/2} - \frac{d}{2}\log 2$

Lieb und Wu bewiesen, dass für jeden Graphen gilt: $\rho(G) \geq \hat{\rho}(G)$

4. Einschränkungen bisheriger Forschung

• Frühere Ergebnisse (Isaev, McKay, Zhang 5) gelten nur für Graphen mit guten Expansionseigenschaften und $d \geq \log^8 n$
• Ergebnisse für Zufallsgraphen (6) hängen von Hochwahrscheinlichkeitseigenschaften ab
• Las Vergnas 7 Ergebnis erfordert, dass der Umfang schneller wächst als $\log d$

5. Forschungsmotivation

Vermutung 1.1: Für eine Sequenz d-regulärer Graphen G(n), wobei die gerade Zahl $d = d(n) \to \infty$, gilt $\rho(G) = \hat{\rho}(G) + o(1)$

Das Ziel dieses Artikels ist es, diese Vermutung unter schwächeren Bedingungen zu beweisen.

Kernbeiträge

1. Hauptsatz (Theorem 2.1): Beweist Vermutung 1.1 unter Beschränkungen der Anzahl kurzer geschlossener Wege mit den Bedingungen:
   • Es existieren $\ell_{max} = \omega(\log d)$ und eine Konstante C > 0
   • Für alle $3 \leq \ell \leq \ell_{max}$: $c_\ell(G) \leq Ce^{-(l+1)}d^{\ell-1}n$
2. Eigenwertbedingungen-Folgerung (Corollary 2.2): Wenn höchstens $nd^{-\omega(1)}$ Eigenwerte außerhalb von $[-d^{1-\delta}, d^{1-\delta}]$ liegen (für eine Konstante δ > 0), dann gilt die Vermutung
3. Umfang-Folgerung (Corollary 2.3): Für d-reguläre Graphsequenzen mit Umfang $g \to \infty$ gilt die Vermutung (ohne dass $d \to \infty$ erforderlich ist)
4. Kartesisches Produkt-Folgerung (Corollary 2.4): Für kartesische Produkte $G_t = H_1^{(t)} \square \cdots \square H_t^{(t)}$, wenn die Summe der Quadrate der Grade $\sum_{i=1}^t (h_i^{(t)})^2 = O(d_t^{2-\delta})$ erfüllt, gilt die Vermutung, besonders für Hyperwürfel $Q_d$
5. Technische Innovation: Transformiert das Problem in eine Analyse der momenterzeugenden Funktion der Anzahl geschlossener Wege, die durch zufällige Eulersche Partitionen induziert werden

Methodische Erklärung

Aufgabendefinition

Gegeben ein d-regulärer Graph G (d gerade), berechne die Restentropie $\rho(G) = \frac{1}{n}\log EO(G)$ und beweise, dass sie asymptotisch gleich der Pauling-Schätzung $\hat{\rho}(G)$ ist.

Kernmethodisches Rahmenwerk

1. Eulersche Partitionsdarstellung

Definition: Eine Eulersche Partition P ist eine Partition der Kanten des Graphen in mehrere geschlossene Wege. Die Kantenpaarung an jedem Knoten bestimmt eindeutig eine Eulersche Partition.

Schlüsselformel: $\rho(G) = \hat{\rho}(G) + \frac{1}{n}\log \mathbb{E} 2^{|T(P)|}$ wobei P eine gleichmäßig zufällige Eulersche Partition ist und T(P) die Menge der geschlossenen Wege ist, die durch P induziert werden.

Äquivalenz: Die Vermutung ist äquivalent zum Beweis, dass $\mathbb{E} 2^{|T(P)|} = e^{o(n)}$

2. Strategie der Zerlegung geschlossener Wege

Definiere $k = \lfloor\min\{\ell_{max}/2, \log^2 d\}\rfloor$, teile geschlossene Wege auf in:

• Lange geschlossene Wege $L_k(P)$: Anzahl der geschlossenen Wege mit mehr als k verschiedenen Knoten
• Kurze geschlossene Wege $S_k(P)$: Anzahl der geschlossenen Wege mit höchstens k verschiedenen Knoten

Verwende die Hölder-Ungleichung: $\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}$

Technische Komponenten

3. Kontrolle langer geschlossener Wege (Lemma 3.4)

Schlüssel-Lemma (Lemma 3.1): Für gerade m und λ ≥ 0, $\mathbb{E} e^{\lambda X(m)} \leq (Bm)^{(e^\lambda-1)/2}$ wobei $X(m)$ die Summe unabhängiger Bernoulli-Zufallsvariablen mit Parametern $1/(2j-1)$ (j=1,...,m/2) ist.

Paarungsunabhängigkeit (Lemma 3.2): Bei zufälliger Paarung folgt die Anzahl verschiedener geschlossener Wege durch Knoten v der Verteilung X(m) und ist unabhängig von der Paarung anderer Knoten.

Momentenerzeugende Funktionsgrenzen (Lemma 3.3): Für eine Knotenteilmenge U, $\mathbb{E} e^{\lambda Y(U)} = d^{O(|U|)}$

Endgültige Grenze: Wähle eine zufällige Teilmenge mit $|U| = \lfloor n/k\rfloor$, nutze $L_k \leq 2Y(U)$ mit Wahrscheinlichkeit mindestens 1/2, erhalte: $\mathbb{E} e^{\lambda L_k} \leq (edk)^{O(n/k)} = e^{o(n)}$

4. Kontrolle kurzer geschlossener Wege (Lemma 4.5)

Verwende die Switching-Methode (Theorem 4.1) – ein kraftvolles kombinatorisches Zählwerkzeug.

Switching-Definition: Gegeben eine Eulersche Partition P und ein geschlossener Weg T, modifiziert T-switching die Paarung an jedem Knoten, den T durchquert:

• Knoten v wird von T t-mal besucht, entsprechend Kantenpaaren $(e_1,e_1'),\ldots,(e_t,e_t')$
• Wähle t zusätzliche Kantenpaare $(e_{t+1},e_{t+1}'),\ldots,(e_{2t},e_{2t}')$
• Ersetze durch neue Paarung $\{e_1,e_{t+1}\},\ldots,\{e_t,e_{2t}\}$ und $\{e_1',e_{t+1}'\},\ldots,\{e_t',e_{2t}'\}$

Switching-Graph: Konstruiere einen gerichteten Multigraphen Γ:

• Knoten: $\mathbf{m} = (m_3,\ldots,m_L)$, repräsentiert Eulersche Partitionsklassen mit genau $m_\ell$ geschlossenen Wegen der Länge ℓ
• Kanten: Gerichtete Kanten der Farbe ℓ von $(\mathbf{m},\mathbf{m}')$ repräsentieren die Existenz eines ℓ-Switchings von C(m) zu C(m')

Schlüsselschätzung (Lemma 4.3):

• Anzahl der ℓ-Switchings ausgehend von P ∈ C(m): $\geq \|\mathbf{m}\|_1(d-2L)^\ell/L$
• Anzahl der ℓ-Switchings ankommend bei P' ∈ C(m'): $\leq c_{k,\ell}$

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

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

Da $\hat{\alpha}(e) < 1/2$ für alle Kanten mit $\|\mathbf{m}\|_1 > M_0$, erhalte: $|Y| \leq 2e^{-M+M_0}|Z|$

Tail-Wahrscheinlichkeitsgrenzen: $\mathbb{P}(S_k(P) > M) \leq 2e^{-M+M_0}$

Momentengrenzen: Durch Integraldarstellung, $\mathbb{E} e^{\lambda S_k(P)} \leq e^{\lambda M_0} + \frac{2e^{\lambda M_0}}{1-\lambda} = e^{o(n)}$ wobei $\lambda = \frac{7}{5}\log 2 \approx 0.97 < 1$.

Technische Innovationspunkte

1. Eleganz der Zerlegungsstrategie: Durch die Wahl von k wird ein Gleichgewicht zwischen langen und kurzen geschlossenen Wegen erreicht, die Exponentenwahl in der Hölder-Ungleichung (7/2 und 7/5) ist sorgfältig gestaltet
2. Innovative Anwendung der Switching-Methode:
   • Transformiert das Zählproblem von Eulerschen Partitionen in ein Flussproblem auf gerichteten Graphen
   • Nutzt die Beschränkung der Anzahl kurzer geschlossener Wege zur Kontrolle der Switching-Gewichte
   • Erreicht durch Theorem 4.1 exponentielle Abnahme der Tail-Wahrscheinlichkeiten
3. Abschwächung der Bedingungen:
   • Von $d \geq \log^8 n$ abgeschwächt zu $d \to \infty$
   • Von starken Expansionseigenschaften abgeschwächt zu Beschränkungen der Anzahl kurzer geschlossener Wege
   • Eigenwertbedingung erfordert nur $nd^{-\omega(1)}$ Ausreißer
4. Einheitliches Rahmenwerk: Behandelt gleichzeitig wachsenden Umfang, Eigenwertbeschränkungen, kartesische Produkte und andere Fälle

Experimentelle Einrichtung

Eigenschaften des theoretischen Beweises

Dieser Artikel ist ein rein theoretischer Artikel und enthält keine numerischen oder rechnerischen Experimente. Alle Ergebnisse sind strenge mathematische Beweise.

Anwendungsbeispiele

Der Artikel verifiziert die Vermutung durch Folgerungen für die folgenden Graphklassen:

1. Graphen mit wachsendem Umfang (Corollary 2.3)
2. Spektral beschränkte Graphen (Corollary 2.2)
3. Hyperwürfel $Q_d$ (d gerade)
4. Zirkuläre kartesische Produkte: Konvergieren lokal gegen hochdimensionale quadratische Gitter
5. Zufällige reguläre Graphen (Ergebnisse aus 6)

Experimentelle Ergebnisse

Hauptergebnisse

Verifikation der Bedingungen von Theorem 2.1:

1. Graphen mit Umfang g → ∞:
   • Anzahl der geschlossenen Wege der Länge ℓ < g ist 0, erfüllt automatisch die Bedingung
   • Gilt auch für d = O(1)
2. Spektral beschränkte Graphen:
   • Anzahl geschlossener Wege $\leq \sum_i \lambda_i^\ell$
   • Wenn höchstens $nd^{-f(n)}$ Eigenwerte außerhalb von $[-d^{1-\delta}, d^{1-\delta}]$ liegen
   • Wähle $\ell_{max} = \frac{1}{2}f(n)\log d$, Bedingung ist erfüllt
3. Kartesische Produkte:
   • Nutze Hoeffding-Ungleichung zur Kontrolle der Eigenwertverteilung
   • Für $\sum_i (h_i^{(t)})^2 = O(d_t^{2-\delta})$ ist die Bedingung erfüllt
   • Hyperwürfel: $h_i = 1$, erfüllt $\sum h_i^2 = t = o(d_t^2)$

Technische Ergebnisse

Grenzen für lange geschlossene Wege (Lemma 3.4): $\mathbb{E} e^{\lambda L_k(P)} = e^{o(n)}, \quad \forall \lambda \geq 0, \, k \gg \log d$

Grenzen für kurze geschlossene Wege (Lemma 4.5): $\mathbb{E} 2^{\frac{7}{5}S_k(P)} = e^{o(n)}$

Schlüsselungleichungskette