Volume 20, No 6, 2013, P. 40-58

UDC 519.1
Isaev M. I., Isaeva K. V.
Asymptotic enumeration of eulerian orientations for graphs with strong mixing properties

Abstract:
We prove an asymptotic formula for the number of Eulerian orientations for graphs with strong mixing properties and with vertices having even degrees. The exact value is determined up to the multiplicative error $O(n^{1+\varepsilon})$, where $n$ is the number of vertices.
Bibliogr. 14.

Keywords: Eulerian orientation, asymptotic analysis, Gaussian integral, algebraic connectivity, Laplacian.

Isaev Mikhail Ismailovich ^1,2
Isaeva Kseniia Valerievna ^1,2
1. Centre de Mathématiques Appliquées, École Polytechnique,
91128 Palaiseau, France
2. Moscow Institute of Physics and Technology,
9 Institute Lane, 141700 Dolgoprudny, Russia
e-mail: Isaev.M.I@gmail.com, Isaeva.K.V@gmail.com