Cumulant expansion for counting Eulerian orientations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910754538520576 |
|---|---|
| author | Isaev, Mikhail McKay, Brendan D. Zhang, Rui-Ray |
| author_facet | Isaev, Mikhail McKay, Brendan D. Zhang, Rui-Ray |
| contents | An Eulerian orientation is an orientation of the edges of a graph such that every vertex is balanced: its in-degree equals its out-degree. Counting Eulerian orientations corresponds to the crucial partition function in so-called ``ice-type models'' in statistical physics and is known to be hard for general graphs. For all graphs with good expansion properties and degrees larger than $\log^{8} n$, we derive an asymptotic expansion for this count that approximates it to precision $O(n^{-c})$ for arbitrary large $c$, where $n$ is the number of vertices. The proof relies on a new tail bound for the cumulant expansion of the Laplace transform, which is of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_15473 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Cumulant expansion for counting Eulerian orientations Isaev, Mikhail McKay, Brendan D. Zhang, Rui-Ray Combinatorics 05C30, 05A16, 60C05 An Eulerian orientation is an orientation of the edges of a graph such that every vertex is balanced: its in-degree equals its out-degree. Counting Eulerian orientations corresponds to the crucial partition function in so-called ``ice-type models'' in statistical physics and is known to be hard for general graphs. For all graphs with good expansion properties and degrees larger than $\log^{8} n$, we derive an asymptotic expansion for this count that approximates it to precision $O(n^{-c})$ for arbitrary large $c$, where $n$ is the number of vertices. The proof relies on a new tail bound for the cumulant expansion of the Laplace transform, which is of independent interest. |
| title | Cumulant expansion for counting Eulerian orientations |
| topic | Combinatorics 05C30, 05A16, 60C05 |
| url | https://arxiv.org/abs/2309.15473 |