M I Isaev

K V Isaeva

On the class of graphs with strong mixing properties

We study three mixing properties of a graph: large algebraic connectivity, large Cheeger constant (isoperimetric number) and large spectral gap from 1 for the second largest eigenvalue of the transition probability matrix of the random walk on the graph. We prove equivalence of this properties (in some sense). We give estimates for the probability for a random graph to satisfy these properties. In addition, we present asymptotic formulas for the numbers of Eulerian orientations and Eulerian circuits in an undirected simple graph.

Introduction

Let G be an undirected simple graph with vertex set V G and edge set EG. We define n × n matrix Q by

Q jk =    -1, {v j , v k } ∈ EG, d j , j = k, 0, otherwise, (1)
where n = |V G| and d j denotes the degree of v j ∈ V G. The matrix Q = Q(G) is called the Laplacian matrix of the graph G. The eigenvalues λ 1 ≤ λ 2 ≤ . . . ≤ λ n of the matrix Q are always non-negative real numbers and λ 1 = 0. The eigenvalue λ 2 = λ 2 (G) is called the algebraic connectivity of the graph G.

The original theory related to algebraic connectivity was produced by Fiedler, see [START_REF] Fiedler | Algebraic connectivity of graphs[END_REF], [START_REF] Fiedler | Laplacian of graphs and algebraic connectivity[END_REF]. The number λ 2 (G) is a discrete analogue of the smallest positive eigenvalue of the Laplace differential operator on the Riemannian manifold.

(For more information on the spectral properties of the Laplace matrix see, for example, [START_REF] Mohar | The Laplacian spectrum of graphs, Graph Theory, Combinatorics, and Applications[END_REF] and references therein.) Let F γ be the set of simple graphs G satisfying the following property:

Property 1. The algebraic connectivity λ 2 (G) ≥ γ|V G|.

For a subset of vertices A ⊆ V G let ∂A denote the set of all edges connecting a vertex in A and a vertex outside A:

∂A = {{u, v} ∈ EG : u ∈ A, v ∈ V G \ A} . (2)
The Cheeger constant (or isoperimetric number) of G, denoted i(G), is defined by

i(G) = min |∂A| |A| : A ⊂ V G, 0 < |A| ≤ |V G| 2 . (3)
The number i(G) is a discrete analogue of the (Cheeger) isoperimetric constant in the theory of Riemannian manifolds and it has many interesting interpretations (for more detailed information see, for example, [START_REF] Mohar | Isoperimetric numbers of graphs[END_REF] and references therein). Let C γ be the set of simple graphs G satisfying the following property:

Property 2. The Cheeger constant (isoperimetric number) i(G) ≥ γ|V G|.

Let P = P (G) be the transition probability matrix of the random walk on the graph G.

P jk = 1 dj , {v j , v k } ∈ EG, 0, otherwise, (4)
The eigenvalues of P are such that

1 = χ 1 ≥ χ 2 . . . ≥ χ n ≥ -1. (5)
The graph G is connected if and only if the random walk is an irreducible Markov chain. In this case, there exists a unique stationary distribution and multiplicity of the eigenvalue χ 1 = 1 is equal to one. (For more information on random walks on graphs see, for example, [START_REF] Lovasz | Random walks on graphs: A survey[END_REF] and references therein.) Let M γ be the set of simple graphs G satisfying the following property:

Property 3. The spectral gap 1 -χ 2 (G) ≥ γ and min

j d j ≥ γ|V G|
Graphs of F γ , C γ , M γ have strong mixing properties. We call F γ ∩ C γ ∩ M γ as the class of γ-mixing graphs. Actually (see Section 2 of the present work), Properties 1-3 are equivalent in the following sense: if a graph satisfies one of these properties with γ = γ 0 > 0, then it satisfies all Properties 1-3 with some γ > 0 depending only on γ 0 .

In Section 3 we estimate the probability of a random graph to be γ-mixing. We consider the following model (Gilbert's random graph model): every possible edge occurs independently with some fixed probability 0 < p < 1. It turned out that in this model almost all graphs (asymptotically) are γ-mixing with some γ > 0 depending only on p.

In Section 4 we construct some general family of graphs, satisfying Properties 1-3 (see Example 3 and Remark 4.1). For example, the family of complete bipartite graphs {K n,n } is the special case of our general family. We also give some other examples.

In addition, we consider two enumeration problems: counting the number of Eulerian orientations (EO) and counting the number of Eulerian circuits (EC) in an undirected simple graph. It is known that both of these problems are complete for the class #P , see [START_REF] Brightwell | Note on Counting Eulerian Circuits[END_REF], [START_REF] Mihail | On the number of Eulerian orientations of a graph[END_REF].

Recently, in [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian circuits[END_REF], [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian orientations of graphs[END_REF] the asymptotic behaviour of the numbers of Eulerian orientations and Eulerian circuits was determined for γ-mixing graphs (more precisely, for graphs satisfying Property 1).

In Section 5 we present the asymptotic formulas for EO, EC and compare them against the exact values for small graphs. Actually, if the graph G is γ-mixing then for any ε > 0 the error term |δ(G)| ≤ Cn -1/2+ε , where C > 0 depends only on ε and γ. We plan to give the proofs of these formulas in a subsequent paper.

Equivalence of Properties 1-3

We recall that for a simple graph G with n vertices:

λ 2 (G) ≤ n n -1 min j d j , (6a)
λ 2 (G) ≥ 2 min j d j -n + 2, ( 6b
)
λ 2 (G) 2 ≤ i(G) ≤ λ 2 (G)(2 max j d j -λ 2 (G)), (7)
λ 2 (G) ≤ λ 2 (G 1 ) + 1, (8a)
λ 2 (G) ≤ λ 2 (G ′ ), (8b)
where G 1 arises from G by removing one vertex and all adjacent edges, G ′ is an arbitrary graph such that V G ′ = V G and EG ⊂ EG ′ . Estimates ( 6), [START_REF] Kirchhoff | Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird[END_REF] were obtained in [START_REF] Fiedler | Algebraic connectivity of graphs[END_REF]. Estimates [START_REF] Fiedler | Laplacian of graphs and algebraic connectivity[END_REF] were given in [START_REF] Mohar | Isoperimetric numbers of graphs[END_REF]. Using [START_REF] Fiedler | Laplacian of graphs and algebraic connectivity[END_REF] and the inequality d j ≤ n, we find that for any γ 0 > 0

F γ0 ⊂ C γ1 and C γ0 ⊂ F γ1 , (9)
where γ 1 > 0 depends only on γ 0 . In order to complete the proof of the equivalence of Properties 1-3 we need the following lemma. For x ∈ R n and n × n matrix M let us denote

x = √ x T x, M = sup x∈R n , x =1 M x . ( 10
) Lemma 1. Let a, b 1 , b 2 > 0. Let A be symmetric positive semidefinite n × n matrix such that for some w ∈ R n , w = 0, A w = 0 (11a)
and for any u ∈ R n such that u T w = 0

A u ≥ a u . ( 11b
)
Then for any symmetric n × n matrix B such that

B ≤ b 1 and w T B w ≥ b 2 w 2 (11c)
the following statement holds:

det(A -λB) = 0, λ = 0 =⇒ λ ≥ ρ ( 12
)
for some ρ = ρ(a, b 1 , b 2 ) > 0.
The proof of Lemma 1 is given at the end of this section.

Note that

P = I -D -1 Q, ( 13
)
where Q and P are the same as in ( 1) and ( 4), respectively, I denotes the identity matrix and D is the diagonal matrix defined by 13), we find that:

D jj = d j . Let A 1 = 1 n Q, B 1 = 1 n D and w 1 = [1, . . . , 1] T . Using (
det(A 1 -λI) = 0 ⇐⇒ det(Q -λnI) = 0; (14) det(A 1 -λB 1 ) = 0 ⇐⇒ det(P -(1 -λ)I) = 0; (15)
for any u ∈ R n such that u T w 1 = 0

u T A 1 u ≥ 1 n λ 2 (G) u T u; (16)
B 1 ≤ 1 n max j d j ≤ 1, w T 1 B 1 w 1 ≥ 1 n min j d j w T 1 w 1 . (17)
Combining Property 1, (6a), ( 14)-( 17) and Lemma 1, we get that for any γ 0 > 0

F γ0 ⊂ M γ2 , (18)
where γ 2 > 0 depends only on γ 0 .

Let

A 2 = D -1 2 QD -1 2 , B = nD -1 and w 2 = D 1 2 w 1 ,
where D s is the diagonal matrix defined by D s jj = (d j ) s . Using [START_REF] Mohar | Isoperimetric numbers of graphs[END_REF], we find that:

det(A 2 -λI) = 0 ⇐⇒ det(P -(1 -λ)I) = 0; (19) det(A 2 -λB 2 ) = 0 ⇐⇒ det(Q -λnI) = 0; (20) for any u ∈ R n such that u T w 2 = 0 u T A 2 u ≥ (1 -χ 2 (G)) u T u; (21)
B 2 ≤ n min j d j , w T 2 B 1 w 2 = n w T 1 w 1 ≥ w T 2 w 2 . ( 22
)
Combining Property 3, ( 19)-( 22) and Lemma 1, we get that for any γ 0 > 0

M γ0 ⊂ F γ3 , (23)
where γ 3 > 0 depends only on γ 0 . Putting together (9), ( 18) and (23), we obtain the desired assertion:

Theorem 1. Let F γ , C γ , M γ be defined as in Section 1. Then for any γ 0 > 0

F γ0 ∪ C γ0 ∪ M γ0 ⊂ F γ ∩ C γ ∩ M γ , ( 24
)
where γ > 0 depends only on γ 0 .

Now it remains to prove Lemma 1. Proof of Lemma 1. Let det(A -λB) = 0. Then for some v ∈ R n , v = 0,

A v = λB v. ( 25
) Let v = v + v ⊥
, where v w and v T ⊥ w = 0. Due to (11a), we have that

v T A v = 0. ( 26
)
Since λ = 0, using (25), we get that

v T B v = -v T B v ⊥ . (27)
Using (11c), ( 27) and the CauchySchwarz inequality, we find that

b 1 v v ⊥ ≥ v B v ⊥ ≥ | v T B v ⊥ | = | v T B v | ≥ b 2 v 2 . ( 28
)
Thus we have that

v ⊥ ≥ b 2 b 2 1 + b 2 2 v . (29)
Using (11b), (11c) and (29), we find that:

A v ≥ a v ⊥ , B v ≤ b 1 v ≤ b 1 b 2 1 + b 2 2 b 2 v ⊥ . (30)
Combining ( 25) and (30), we obtain that

λ ≥ ab 2 b 1 b 2 1 + b 2 2 . ( 31
)
3 Probability for a random graph to be γ-mixing

Let ξ be a random variable belonging to the binomial distribution B(M, p):

Pr(ξ = k) = M ! k!(M -k)! p k (1 -p) M-k , 0 < p < 1, M ∈ N. ( 32
) Note that Pr(ξ ≤ αM ) ≤ c -M (33)
for some α > 0, c > 1 depending only on p. This follows, for example, from the following estimate: for 1

≤ k ≤ p(M+1) p+2 Pr(ξ = k) Pr(ξ = k -1) = M -k + 1 k p 1 -p ≥ 2 p+2 (M + 1) p p+2 (M + 1) p 1 -p ≥ 2. ( 34
)
Let G be a random graph belonging to Gilbert's random graph model G(n, p):

∀ 1≤i<j≤n Pr({v i , v j } ∈ EG) = p, 0 < p < 1, (independently for each {i, j}). ( 35
)
For a subset of vertices A ⊂ V G, using (33), we find that

Pr(|∂A| ≤ α|A|(n -|A|)) ≤ c -|A|(n-|A|) . (36)
Using (36), we get that

Pr(i(G) ≤ αn 2 ) ≤ A⊂V G, 0<|A|≤ n 2 Pr(|∂A| ≤ α|A| n 2 ) ≤ ≤ n/2 k=1 |A|=k Pr(|∂A| ≤ α|A|(n -|A|)) ≤ ≤ n/2 k=1 n! k!(n -k)! c -k(n-k) ≤ n/2 k=1 n! k!(n -k)! (c -n/2 ) k ≤ ≤ (1 + c -n/2 ) n -1 ≤ β -n (37)
for some β > 1 depending only on p. Due to (37) and Theorem 1, we obtain that probability for a random graph (in Gilbert's model G(n, p)) to be γ-mixing is at least 1-β -n , where γ = γ(p) > 0 and β = β(p) > 1.

Some basic properties and examples

We note that, due to (6b) and Theorem 1,

if min j d j ≥ σ|V G| for some σ > 1/2 =⇒ the graph G is γ-mixing for some γ = γ(σ) > 0. ( 38
)
Example 1. Let K n and Kn be two complete graphs with n vertices. We define G

n by V G (1) n = V K n ∪ V Kn , EG (1) n = EK n ∪ E Kn ∪ E + , where E + = {{v i , ṽi }, i = 1, . . . n}.

(39)

• Case 2. |A| > c 0 n/2. Let V 1 , V 2 ⊂ V G 0 such that v j ∈ V 1 ⇐⇒ | v i j : v i j ∈ A | ≥ c 0 n 2m , (47)
v j ∈ V 2 ⇐⇒ | v i j : v i j / ∈ A | ≥ c j n 2 . ( 48
)
Due to c 0 n/2 < |A| ≤ Cn/2, we have that

V 1 ∪ V 2 = V G 0 , |V 1 | > 0, |V 2 | > 0. ( 49
) Since G 0 is connected, we can find v j1 ∈ V 1 , v j2 ∈ V 2 such that {v j1 , v j2 } ∈ EG 0 .
Estimating the number of edges in ∂A, matching these vertices, we obtain that

|δA| ≥ c 0 c j2 n 2 4m ≥ c 2 0 n 2mC |A| = c 2 0 |V G (3) n | 2mC 2 |A|. ( 50
)
Combining ( 46), ( 50) and Theorem 1, we obtain that the family V G

(3) n

satisfies Properties 1-3 with γ > 0, depending only on G 0 , c 1 , . . . , c m . We note that Example 3 can be modified so that the constants c 1 , . . . , c m > 0 are not necessarily natural numbers. We assumed that just for simplicity of the proof.

Asymptotic estimates for γ-mixing graphs

An Eulerian orientation of G is an orientation of its edges such that for every vertex the number of incoming edges and outgoing edges are equal. We denote EO(G) the number of Eulerian orientations. Eulerian orientations of the complete graph K n are called regular tournaments.

An Eulerian circuit in G is a closed walk which uses every edge of G exactly once. Let EC(G) denote the number of these up to cyclic equivalence.

We recall that EO(G) = EC(G) = 0, if the degree of at least one vertex of G is odd (for more information see, for example, [START_REF] Biggs | Graph Theory[END_REF]). In this section we always assume that every vertex has even degree.

Let consider two enumeration problems: counting the number of Eulerian orientations and counting the number of Eulerian circuits in an undirected simple graph. It is known that both of these problems is complete for the class #P , see [START_REF] Brightwell | Note on Counting Eulerian Circuits[END_REF], [START_REF] Mihail | On the number of Eulerian orientations of a graph[END_REF].

The results presented in this section are based on estimates of [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian circuits[END_REF], [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian orientations of graphs[END_REF]. We plan to give detailed proofs in a subsequent paper.

Eulerian orientations

We recall that the problem of counting Eulerian orientations can be reduced to counting perfect matching for some class of bipartitute graphs for which it can be done approximately with high probability in polynomial time, see [START_REF] Mihail | On the number of Eulerian orientations of a graph[END_REF]. However, the degree of the polynomial is large, so, in fact, these algorithms have a very big work time for the error term O(n -1/2 ).

For γ-mixing graphs we have the following asymptotic formula:

Proposition 1. Let G be an undirected simple graph with n vertices v 1 , v 2 , . . . , v n having even degrees. Let G be a γ-mixing graph for some γ > 0. Then

EO(G) = (1 + δ(G))   2 |EG|+ n-1 2 π -n-1 2 1 t(G) {vj ,v k }∈EG P jk  , P jk = 1 - 1 4(d j + 1) 2 - 1 2(d j + 1)(d k + 1) - 1 4(d k + 1) 2 , ( 51
)
where d j denotes the degree of vertex v j , t(G) denotes the number of spanning trees of the graph G and for any ε > 0

|δ(G)| ≤ Cn -1/2+ε , (52)
where constant C > 0 depends only on γ and ε.

Remark 2. We note that, according to the Kirchhoff Matrix-Tree-Theorem, see [START_REF] Kirchhoff | Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird[END_REF], we have that

t(G) = 1 n λ 2 λ 3 • • • λ n = det M 11 , (53)
where M 11 results from deleting the first row and the first column of Q.

Remark 3. For the complete graph

λ 2 (K n ) = n, EK n = n(n-1) 2 , t(K n ) = n n-2 , {vj ,v k }∈EKn P jk = 1 - 1 4n 2 - 1 2n 2 - 1 4n 2 n(n-1) 2 = = e ln(1-1 n 2 ) n(n-1) 2 = e -1/2 + O(n -1 ). ( 54
)
The result of Proposition 1 for this case is reduced to the result of [START_REF] Mckay | The asymptotic numbers of regular tournaments, eulirian digraphs and eulirian oriented graphs[END_REF] on counting regular tournaments in the complete graph.

We plan to give the proof of Proposition 1 in a subsequent paper. In the present work we just compare the answers given by formula (51) against the exact values for small graphs. Let

Error(G) = EO approx (G) -EO(G) EO(G) , (55)
where EO approx (G) is taken according to right-hand side of (51). The following charts show the dependence of Error(G) on the ratio λ 2 (G)/n, where λ 2 (G) is the algebraic connectivity and n = |V G| = 6, 7, 8, 9:

The charts show, in particular, that Error decreases significantly with respect to the ratio λ 2 (G)/n.

Eulerian circuits

To our knowledge (in contrast to the coundting of eulerian orientations) approximate polynomial algorithms for counting the number of Eulerian circuits have been obtained only in the literature fore some special classes of graphs having low density, see [START_REF] Chebulu | Exact counting of Euler tours for generalized series-parallel graphs[END_REF] and [START_REF] Tetali | Random sampling of Euler tours[END_REF]. However, we have the formula for EC(G) similar to (51) for γ-mixing graphs. This formula is more complicated, so we need some additional notations. Let

W = Q-1 = (Q + J) -1 , ( 56
)
where Q is the Laplacian matrix and J denotes the matrix with every entry 1. Let α = (α 1 , . . . , α n ) ∈ R n be defined by

α j = W jj (57)
Let β = Q α and

C 1 = exp   - n-1 j=1 n k=j+1 β j W jk β k   , (58)
C 2 = exp   - n j=1 β 2 j 2(d j + 1)   , (59)
where

d j is the degree of v j ∈ V G. Let R( θ) = tr(Λ( θ)W Λ( θ)W ), (60)
where tr(•) is the trace fucntion, Λ( θ) denotes the diagonal matrix whose diagonal elements are equal to components of the vector Q θ. Let e (k) = (e

(k) 1 , . . . , e (k)
n ) ∈ R n be defined by e (k) j = δ jk , where δ jk is the Kronecker delta. Let r k = R( e (k) ),

C 3 = exp   n j=1 r j 2(d j + 1)   . (61)
Finally, let

C 4 = {vj ,v k }∈EG P jk , (62)
where P jk is the same as in (51).

where constant C ′ > 0 depends only on γ and ε.

Remark 4. One can obtain for the case of G = K n that

C 1 C 2 C 3 C 4 = 1 + O(n -1 ) (65)
Using Remark 5.2 and Stirling's formula for factorials, the result of Proposition 2 for this case can be reduced to the result of [START_REF] Mckay | Asymptotic enumeration of eulerian circuits in the complete graph[END_REF] on counting Eulerian circuits in the complete graph.

We plan to give the proof of Proposition 2 in a subsequent paper. In the present work we just compare the answers given by formula (63) against the exact values for small graphs. Let

Error ′ (G) = EC approx (G) -EC(G) EC(G) , (66)
where EC approx (G) is taken according to right-hand side of (63). The following charts show the dependence of Error ′ (G) on the ratio λ 2 (G)/n, where λ 2 (G) is the algebraic connectivity and n = |V G| = 6, 7, 8, 9:

The charts show, in particular, that Error ′ decreases significantly with respect to the ratio λ 2 (G)/n.

Remark 1 .

 1 Combining (8), Theorem 1 and Example 3, one can prove Properties 1-3 for a large number of classic examples (including {K n }, {K n,n } and many others).

Proposition 2 .

 2 Let G be an undirected simple graph with n vertices v 1 , v 2 , . . . , v n having even degrees. Let G be a γ-mixing graph for some γ > 0. Then EC(G) = (1 + δ ′ (G)) where C 1 , C 2 , C 3 , C 4 are defined according to (58), (59), (61), (62), respectively, d j is the degree of vertex v j , t(G) is the number of spanning trees of G and for any ε > 0|δ ′ (G)| ≤ C ′ n -1/2+ε ,

Acknowledgements

This work was carried out under the supervision of S.P. Tarasov and supported in part by RFBR grant no 11-01-00398a.

For G = G [START_REF] Biggs | Graph Theory[END_REF] n we have that for all j = 1, . . . , 2n

Thus the family {G

n } does not satisfy Property 2 (and hence Properties 1,3). We note also that even the vertex and the edge connectivity is large for this family of graphs.

Example 2. Let K n be the complete graph with n vertices. We define

For G = G

n we have that min

Note also that Examples 1 and 2 show, in particular, that both conditions of Property 3 are necessary.

Example 3. Let G 0 be a connected simple graph with m > 1 vertices. Let c 1 , c 2 , . . . , c m be some natural numbers. We define G

n by

We estimate the Cheeger constant (isoperimetric number) i(G

n ). Let

We have that the degree of each vertex of V G (3) n at least c 0 n

and

n , |A| ≤ Cn/2.

• Case 1. |A| ≤ c 0 n/2. Using (45), we find that


M I Isaev

Asymptotic enumeration of Eulerian circuits for graphs with strong mixing properties

We prove an asymptotic formula for the number of Eulerian circuits 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/2+ε ), where n is the number of vertices.

Introduction

Let G be a simple connected graph all of whose vertices have even degrees. An Eulerian circuit in G is a closed walk (see, for example, [START_REF] Biggs | Graph Theory[END_REF]) which uses every edge of G exactly once. Two Eulerian circuits are called equivalent if one is a cyclic permutation of the other. It is clear that the size of such an equivalence class equals the number of edges of graph G. Let EC(G) denote the number of equivalence classes of Eulerian circuits in G.

The problem of counting the number of Eulerian circuits in an undirected simple graph (graph without loops and multiple edges) is complete for the class #P , i.e. the existence of a polynomial algorithm for this problem implies the existence of a polynomial algorithm for any problem in the class #P and, in particular, the equivalence of the classes P and NP . (see [START_REF] Brightwell | Note on Counting Eulerian Circuits[END_REF]). In other words, the problem of counting the number of Eulerian circuits is difficult in terms of the complexity theory. Moreover, it should be noted that in contrast to many other hard problems of counting on graphs (see, for example, [START_REF] Arora | Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems[END_REF], [START_REF] Mihail | On the number of Eulerian orientations of a graph[END_REF]), even approximate and probabilistic polynomial algorithms for counting the number of Eulerian circuits have not been obtained for the general case and are known only for some special classes of graphs with low density, see [START_REF] Chebulu | Exact counting of Euler tours for generalized series-parallel graphs[END_REF] and [START_REF] Tetali | Random sampling of Euler tours[END_REF].

As concerns the class of complete graphs K n , the exact expression of the number of Eulerian circuits for odd n is unknown (it is clear that EC(K n ) = 0 for even n) and only the asymptotic formula was obtained (see [START_REF] Mckay | Asymptotic enumeration of eulerian circuits in the complete graph[END_REF]): as n → ∞ with n odd

EC(K n ) = 2 (n-1) 2 2 π -n-1 2 n n-2 2 n -1 2 -1 ! n 1 + O(n -1/2+ε ) = = 2 n+1 2 π 1 2 e -n 2 2 + 11 12 n (n-2)(n+1) 2 1 + O(n -1/2+ε ) (1.1)
for any fixed ε > 0.

In [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian circuits[END_REF] the analytic approach of [START_REF] Mckay | Asymptotic enumeration of eulerian circuits in the complete graph[END_REF] was generalized. This approach is based on expression of the result in terms of a multidimensional integral and its estimation as dimension tends to infinity. In particular, the asymptotic behaviour of the number of Eulerian circuits was determined for graphs with large algebraic connectivity. This class of graphs we mean as the class of graphs having strong mixing properties.

There are several classic graph parameters which express mixing properties of graphs: the algebraic connectivity, the Cheeger constant (isoperimetric number), the spectral gap between the 1 and the second largest eigenvalue of the transition probability of the random walk on a graph. It should be noted that, using any of these parametres, one can get equivalent definitions of the class of graphs having strong mixing properties (for more detailed information, see [START_REF] Isaev | On the class of graphs with strong mixing properties[END_REF]).

In addition, it is shown in [START_REF] Isaev | On the class of graphs with strong mixing properties[END_REF] that a random graph in the Gilbert graph model G(n, p) (each possible edge occurs in a graph with n vertices independently with probability p) for n → ∞ and fixed p > 0 has strong mixing properties with probability close to 1 (with the exception of some exponentially small of n value).

In the present work we continue studies of [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian circuits[END_REF], [START_REF] Isaev | On the class of graphs with strong mixing properties[END_REF], [START_REF] Mckay | Asymptotic enumeration of eulerian circuits in the complete graph[END_REF]. We prove an asymptotic formula for the number of Eulerian circuits of graphs having strong mixing properties. This result is presented in detail in Section 2 of the present work.

Actually, the estimation of the number of Eulerian circuits was reduced in [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian circuits[END_REF] to estimating of an n-dimensional integral which is close to Gaussiantype. We partly repeat this reduction in Sections 3, 8 of the present paper. In addition, we develop an approach for estimating of integrals of such a type in Sections 4, 6, 7. We prove the main result in Section 5.

An orientation of edges of a graph such that at each vertex the number of incoming and outgoing edges are the same is called it Eulerian orientation. In [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian orientations of graphs[END_REF] the asymptotic behaviour of the number of Eulerian orientations was determined for graphs having strong mixing properties. Apparently, proceeding from the results of [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian orientations of graphs[END_REF] and the estimates of the present work, it is possible to prove the asymptotic formula for the number of Eulerian orientations given in [START_REF] Isaev | On the class of graphs with strong mixing properties[END_REF]. In a subsequent paper we plan to develop this approach.

Main result

Let G be an undirected simple graph with vertex set V G = {v 1 , v 2 , . . . , v n } and edge set EG. We define n × n matrix Q by

Q jk =    -1, {v j , v k } ∈ EG, d j , j = k, 0, otherwise, (2.1)
where n = |V G| and d j denotes the degree of

v j ∈ V G. The matrix Q = Q(G)
is called the Laplacian matrix of the graph G. The eigenvalues λ 1 ≤ λ 2 ≤ . . . ≤ λ n of the matrix Q are always non-negative real numbers and the number of zero eigenvalues of Q coincides with the number of connected components of G, in particular, λ 1 = 0. The eigenvalue λ 2 = λ 2 (G) is called the algebraic connectivity of the graph G. In addition, the following inequalities hold:

2 min j d j -n + 2 ≤ λ 2 ≤ n n -1 min j d j . (2.2)
For more information on the spectral properties of graphs see, for example, [START_REF] Fiedler | Algebraic connectivity of graphs[END_REF] and [START_REF] Mohar | The Laplacian spectrum of graphs, Graph Theory, Combinatorics, and Applications[END_REF]. An acyclic connected subgraph of the graph Gd which includes all of its vertices is called a spanning tree of G. According to Kirchhoff's Matrix-Tree-Theorem, see [START_REF] Kirchhoff | Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird[END_REF], we have that

t(G) = 1 n λ 2 λ 3 • • • λ n = det M 11 , (2.3)
where t(G) denotes the number of spanning trees of the graph G and M 11 results from deleting the first row and the first column of Q.

We call the graph G as γ-mixing graph, γ > 0, if the algebraic connectivity λ 2 = λ 2 (G) ≥ γ|V G|.

(2.4)

The main result of the present work is the following theorem.

Theorem 2.1. Let G be an undirected simple graph with n vertices v 1 , v 2 , . . . , v n having even degrees. Let G be a γ-mixing graph for some γ > 0. Then

EC(G) = (1 + δ(G)) e Kec 2 |EG|-n-1 2 π -n-1 2 t(G) n j=1 d j 2 -1 ! , K ec = - 1 4 {v j ,v k }∈EG 1 d j + 1 - 1 d k + 1 2 , (2.5)
where EG denotes the edge set of G, d j is the degree of vertex v j , t(G) is the number of spanning trees of G and for any ε > 0

|δ(G)| ≤ Cn -1/2+ε , (2.6)
where constant C > 0 depends only on γ and ε.

Proof of Theorem 2.1 is given in Section 5. This proof is based on results presented in Sections 3, 4.

Remark 2.1. For the case of the complete graph we have that:

λ 2 (K n ) = n, EK n = n(n -1) 2 , t(K n ) = n n-2 , K ec = 0. (2.7)
We obtain that the result of Theorem 2.1 for the case of the complete graph is equivalent to (1.1).

Reduction to the integral

A directed tree with root v is a connected directed graph T such that v ∈ V T has out-degree zero, and each other vertex has out-degree one. Thus, T is a tree which has each edge oriented towards v.

Let G be a connected undirected simple graph with n vertices v 1 , v 2 , . . . , v n having even degrees. Note that for every spanning tree T of the graph G and any vertex v r ∈ V G there is only one orientation of the edges of T such that we obtain a directed tree with root v r . We denote by T r the set of directed trees with root v r obtained in such a way.

We recall that (see Section 4 and formulas (4.6), (4.7) of [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian circuits[END_REF]):

EC(G) = n j=1 d j 2 -1 ! 2 |EG|-n+1 π -n S, (3.1)
where for any r ∈ N, r ≤ n,

S = Un(π/2) {v j ,v k }∈EG cos ∆ jk T ∈Tr (v j ,v k )∈ET (1 + i tan ∆ jk ) d ξ, (3.2)
where ∆ jk = ξ j -ξ k and

U n (ρ) = {(ξ 1 , ξ 2 , . . . , ξ n ) ∈ R n : |ξ j | ≤ ρ for all j = 1 . . . n}. (3.3)
We approach the integral by first estimating it in the region which is the asymptotically significant one. In what follows, we fix some small constant ε > 0. Define

V 0 = { ξ ∈ U n (π/2) : |ξ j -ξ k | π ≤ n -1/2+ε for any 1 ≤ j, k ≤ n} |ξ j -ξ k | π = min l∈Z |ξ j -ξ k + πl|. (3.4)
and let S 0 denote the contribution to S of ξ ∈ V 0 :

S 0 = 1 n n r=1 Un(π/2) {v j ,v k }∈EG cos ∆ jk T ∈Tr (v j ,v k )∈ET (1 + i tan ∆ jk ) d ξ. (3.5)
In this section we use standart notation f = O(g) as n → ∞ which indicates that there exist c, n 0 > 0 such that for n ≥ n 0 the inequality |f | ≤ c|g| holds.. Under assumptions of Theorem 2.1, we have that as n → ∞

S = 1 + O exp(-cn 2ε ) S 0 (3.6)
for some c > 0 depending only on γ. For the proof of (3.6), see Theorem 6.3 of [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian circuits[END_REF].

Let

W = Q-1 = (Q + J) -1 , (3.7)
where Q is the Laplacian matrix and J denotes the matrix with every entry 1. Let α = (α 1 , . . . , α n ) ∈ R n be defined by

α j = W jj . (3.8) Let R( ξ) = tr(Λ( ξ)W Λ( ξ)W ), (3.9)
where tr(•) is the trace fucntion, Λ( ξ) denotes the diagonal matrix whose diagonal elements are equal to corresponding components of the vector Q ξ.

The sum over T r in the integrand of (3.2) can be expressed as a determinant, according to the following theorem of [START_REF] Tutte | The dissection of equilateral triangles into equilateral triangles[END_REF], which is a generalization of aforementioned Kirchhoff's Matrix-Tree-Theorem:

Theorem 3.1. Let w jk (1 ≤ j, k ≤ n, j = k) be arbitrary. Define the n × n matrix A by A jk = -w jk , if j = k, r =j w jr , if k = j , (3.10)
the sum being over 1 ≤ r ≤ n with r = j. For any r with 1 ≤ r ≤ n, let M r denote the principal minor of A formed by removing row r and column r.

Then det M r = T (v j ,v k )∈ET w jk , (3.11)
where the sum is over all directed trees T with V T = {v 1 , v 2 , . . . , v n } and root v r .

Using formulas (3.2) and (3.6), Theorem 3.1 and the Taylor series expansion of cos ∆ jk and tan ∆ jk in the region V 0 , one can obtain the following proposition: Proposition 3.1. Let the assumptions of Theorem 2.1 hold. Then as n → ∞

S 0 = 1 + O n -1/2+6ǫ 2 -1/2 π 1/2 n -1 det Q Int, (3.12) Int = Un(n -1/2+ε ) exp i ξ T Q α - 1 2 ξ T Q ξ - 1 12 {v j ,v k }∈EG ∆ 4 jk + 1 2 R( ξ) d ξ, (3.13
) where Q, α and R( ξ) are the same as in (3.7), (3.8) and (3.9), respectively.

We prove in detail Proposition 3.1 in Section 8. Actually, this proof was implicitly given in [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian circuits[END_REF] (see Lemma 5.3 of [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian circuits[END_REF]).

Thus, we get that to prove Theorem 2.1 it remains only to estimate the integral Int of (3.12).

Asymptotic estimates of integrals

We fix constants a, b, ε > 0. In this section we use notation f = O(g) meaning that |f | ≤ c|g| for some c > 0 depending only on a, b and ε.

Let p ≥ 1 be a real number and x ∈ R n . Let

x p = n j=1 |x j | p 1/p . ( 4.1)
For p = ∞ we have the maximum norm

x ∞ = max j |x j |. (4.2)
The matrix norm corresponding to the p-norm for vectors is

A p = sup x =0 A x p x p . (4.3)
One can show that for symmetric matrix A and p ≥ 1

A p ≥ A 2 . (4.4)
For invertible matrices define the condition number

µ p (A) = A p • A -1 p ≥ AA -1 p = 1. (4.5)
Let I be identity n × n matrix and A = I + X be such a matrix that:

A is positive definite symmetric matrix,

|X jk | ≤ a/n, X jj = 0, A -1 2 ≤ b. (4.6)
Note that

A -1 -1 2 ≤ A 2 ≤ A ∞ = A 1 = max j n k=1 |A jk | = O(1). (4.7)
We recall that (see Lemma 3.2 of [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian orientations of graphs[END_REF] ), under assumptions (4.6),

µ ∞ (A) = µ 1 (A) = O(µ 2 (A)). (4.8)
Using (4.4), (4.6), (4.7) and (4.8), we obtain the following lemma:

Lemma 4.1. Let A satisfy (4.6). Then A -1 ∞ = A -1 1 = O(1), (4.9
)

|X ′ jk | = O(n -1 ), (4.10)
where

X ′ = A -1 -I = A -1 (I -A) = -A -1 X. (4.11)
We use the following notation:

< g > F,Ω = Ω g( θ)e F ( θ) d θ, (4.12)
where g, F are some functions on R n . For r > 0 let

< g > F,r =< g > F,Un(rn ε ) , (4.13)
where

U n (ρ) = {(θ 1 , θ 2 , . . . , θ n ) ∈ R n : |θ j | ≤ ρ for all j = 1 . . . n}. (4.14)
We use functions of the following type:

F ( θ) = -θ T A θ + H( θ), (4.15)
where A satisfy (4.6). Let consider the following assumptions on function H, which we will need further:

H( θ) ≤ c 1 θ T A θ n , (4.16
)

∂H( θ) ∂ θ ∞ ≤ c 2 θ 3 ∞ + θ ∞ n (4.17)
For the case when H ≡ 0 we use notations: (4.6) and assumptions (4.16), ( 4.17) hold for some c 1 , c 2 > 0. Then

< g > Ω =< g > F,Ω , < g > r =< g > F,r , < g >=< g > +∞ . (4.18) Lemma 4.2. Let Ω ⊂ R n be such that U n (r 1 n ε ) ⊂ Ω ⊂ U n (r 2 n ε ) for some r 2 > r 1 > 0. Let A satisfy
< 1 > Ω = (1 + O exp(-c 3 n 2ε ) ) < 1 >, (4.19) < 1 > F,Ω = O (< 1 >) , (4.20) < θ 2 k > F,Ω = 1 2 < 1 > F,Ω +O(n -1+4ε ) < 1 >, (4.21) < θ 4 k > F,Ω = 3 4 < 1 > F,Ω +O(n -1+7ε ) < 1 > (4.22)
and, for k = l:

< θ k θ l > F,Ω = O(n -1+5ε ) < 1 >, (4.23) < θ k θ 3 l > F,Ω = O(n -1+7ε ) < 1 >, (4.24) < θ 2 k θ 2 l > F,Ω = 1 4 < 1 > F,Ω +O(n -1+7ε ) < 1 >, (4.25)
where F is defined by ( 4.15) and

c 3 = c 3 (r 1 , r 2 , c 1 , c 2 , a, b, ε) > 0.
In addition, for any vector

p = (p 1 , p 2 , . . . p n ) ∈ R n , p ∞ = O(n -1/2 ), < θ k e i θ T p-ip k θ k > F,Ω = = i 2 j =k,j≤n p j (A -1 ) jk <e i θ T p-ip k θ k > (F -1 2 p 2 k θ 2 k ),Ω + + O(n -1+5ε ) < 1 >, (4.26)
where (A -1 ) jk denotes (j, k)-th element of the matrix A -1 .

Proof of Lemma 4.2 is given in Section 6.

Proof of Theorem 2.1

The Laplacian matrix Q of the graph G ( defined in (2.1)) has the eigenvector [1, 1, . . . , 1] T , corresponding to the eigenvalue λ 1 = 0. Let Q = Q + J, where J denotes the matrix with every entry 1. Note that Q and Q have the same set of eigenvectors and eigenvalues, except for the eigenvalue corresponding to the eigenvector [1, 1, . . . , 1] T , which equals 0 for Q and n for Q. Using (2.3), we find that

t(G) = 1 n λ 2 λ 3 • • • λ n = det Q n 2 .
(5.1)

Using (4.4), we get that

λ n = ||Q|| 2 ≤ || Q|| 2 ≤ || Q|| 1 = max j n k=1 | Qjk | = n. (5.2)
Then, we find that

|| Q-1 || 2 = 1 λ 2 ≤ 1 γn . (5.3) Using (2.
2), we get that

n -1 ≥ d j ≥ λ 2 n -1 n ≥ γ(n -1), (5.4)
where d j is the degree of v j . Consider the integral of Proposition 3.1:

Int = Un(n -1/2+ε ) exp i ξ T β - 1 2 ξ T Q ξ - 1 12 {v j ,v k }∈EG ∆ 4 jk + R( ξ) 2 d ξ, R( ξ) = tr(Λ( ξ) Q-1 Λ( ξ) Q-1 ), β = Q α, (5.5)
where Λ( ξ) denotes the diagonal matrix whose diagonal elements are equal to corresponding components of the vector Q ξ and α is the vector composed of the diagonal elements of Q-1 .

Let define ξ( θ) = (ξ 1 ( θ), ξ 2 ( θ), . . . ξ n ( θ)) by

θ k = (d k + 1)/2 ξ k . (5.6)
Then we can rewrite (5.5) in notations of Section 4:

Int =< e i p T θ > F,Ω n j=1 1 (d j + 1)/2 , (5.7)
where p = (p 1 , p 2 , . . . p n ),

p k = β k (d j + 1)/2 , ( 5.8)
F ( θ) = -θ T A θ + H( θ),
(5.9)

θ T A θ = 1 2 ξ( θ) T Q ξ( θ), A jk = 1 (d j + 1)(d k + 1)
Qjk , (5.10)

H(θ) = - 1 12 {v j ,v k }∈EG ∆ 4 jk + R( ξ( θ)) 2 , (5.11
)

Ω = { θ ∈ R n : ξ( θ) ∈ U n (n -1/2+ε )}.
(5.12)

We aim to reduce, using Lemma 4.2, expression Int of (5.7) to

< 1 >= R n e -θ T A θ d θ = π n/2 √ det A = (2π) n/2 det Q n j=1 (d j + 1)/2. (5.13)
Our argument is as follows: first we have to verify that all assumptions of Lemma 4.2 hold, then we will gradually get rid of the oscillating term e i p T θ , quadratic term R( ξ( θ))

2
and the residual term -

1 12 {v j ,v k }∈EG ∆ 4 jk .
Further, we always use notation f = O(g) meaning that |f | ≤ c|g| for some constant c > 0 depending only on γ and ε.

Assumptions of Lemma 4.2

Combining (5.3), (5.4), (5.6), (5.10) and (5.12), we get that A satisfy (4.6) and U n (r

1 n ε ) ⊂ Ω ⊂ U n (r 2 n ε ) (5.14)
for some a, b, r 1 , r 2 > 0 depending only on γ. Let e (k) = (e

(k) 1 , . . . , e (k)
n ) ∈ R n be defined by e (k) j = δ jk , where δ jk is the Kronecker delta. Due to the linearity of Λ( ξ) and tr(•), we find that

R( ξ( θ)) = ξ( θ) T R ξ( θ) = θ T S θ, (5.15)
where

R jk = tr(Λ( e (j) ) Q-1 Λ( e (k) ) Q-1 ), S jk = R jk (d j + 1)/2 (d k + 1)/2 . (5.16)
We use the following inequalities for n × n matrices X, Y :

|tr(XY )| ≤ X HS Y HS , XY HS ≤ X HS Y T 2 ,
(5.17) where • HS denotes the Hilbert-Schmidt norm,

X HS = n j=1 n k=1 |X jk | 2 .
(5.18)

Combining (5.2), (5.3), (5.15)-( 5.17), we find that

ξ T 1 R ξ 2 ≤ Λ( ξ 1 ) Q-1 HS Λ( ξ 2 ) Q-1 HS ≤ ≤ Λ( ξ 1 ) HS Λ( ξ 2 ) HS Q-1 2 2 = Q ξ 1 2 Q ξ 2 2 Q-1 2 2 ≤ ≤ Q 2 2 Q-1 2 2 ξ 1 2 ξ 2 2 = O(1) ξ 1 2 ξ 2 2 .
(5.19) Using (5.2), (5.10), (5.11) and (5.19), we obtain that

H( θ) ≤ R( ξ( θ)) = ξ( θ) T R ξ( θ) = O(1) ξ( θ) 2 2 = = O(1) ξ( θ) T Q ξ( θ) n = O(n -1 ) θ T A θ.
(5.20)

Let ( Q-1 Λ( ξ) Q-1 ) kk denote the (k, k)-th element of the matrix Q-1 Λ( ξ) Q-1 . For any 1 ≤ k ≤ n, we have that ∂R( ξ) ∂ξ k = 2tr ∂Λ( ξ) ∂ξ k Q-1 Λ( ξ) Q-1 = 2tr Λ( e (k) ) Q-1 Λ( ξ) Q-1 = = 2d k ( Q-1 Λ( ξ) Q-1 ) kk + 2tr Λ Q-1 Λ( ξ) Q-1 , (5.21)
where Λ is the diagonal matrix with the diagonal elements Λjj = Λ( e (k) ) jj in the case of j = k and Λkk = 0. In particular, we have that

Λ 2 ≤ 1. (5.22) Since Λ( ξ) is diagonal matrix, we get that |d k ( Q-1 Λ( ξ) Q-1 ) kk | = |d k Λ( ξ) kk | ( Q-1 ) k 2 2 ≤ d k Λ( ξ) 2 ( Q-1 ) k 2 2 , (5.23)
where ( Q-1 ) k is the k-th column of the matrix Q-1 . Note that

( Q-1 ) k 2 ≤ Q-1 2 Q( Q-1 ) k 2 = Q-1 2 .
(5.24)

We also note that

Λ( ξ) 2 = Q ξ ∞ ≤ 2n ξ ∞ .
(5.25)

Combining (5.3), (5.4), (5.22)-(5.25), we get that

|tr Λ Q-1 Λ( ξ) Q-1 | ≤ n Λ Q-1 Λ( ξ) Q-1 2 ≤ ≤ n Λ 2 Λ( ξ) 2 Q-1 2 2 = O(1) ξ ∞ , d k ( Q-1 Λ( ξ) Q-1 ) kk = O(1) ξ ∞ .
(5.26) Using (5.4), (5.6), (5.15), (5.21) and (5.26) for all 1 ≤ k ≤ n, we obtain that

2 R ξ ∞ = ∂R( ξ) ∂ ξ ∞ = O(1) ξ ∞ , 2 S θ ∞ = ∂R( ξ( θ)) ∂ θ ∞ = O(n -1 ) θ ∞ .
(5.27)

For any 1 ≤ k ≤ n, we have that

∂ ∂ξ k {v j ,v l }∈EG ∆ 4 jl ≤ 4 n j=1 |∆ jk | 3 = O(n) ξ 3 ∞
(5.28)

Combining (5.6) and (5.28), we find that

∂ ∂ θ {v j ,v l }∈EG ∆ 4 jl ∞ = O(n -1 ) θ 3 ∞ .
(5.29) Using (4.10), the fact that

( Q-1 ) jk = (A -1 ) jk (d j + 1)/2 (d k + 1)/2 , (5.30)
and (5.4), we get that

p ∞ = sup 1≤k≤n β k (d j + 1)/2 = O(n -1/2 ) Qα ∞ = O(n -1/2 ), (5.31)
where vector p is the same as in (5.8).

Putting together (5.10), (5.14), (5.20), (5.27), (5.29) and (5.31), we get that all assumptions of Lemma 4.2 with data (5.8)-(5.12) hold for some constants a, b, r 1 , r 2 , c 1 , c 2 > 0 depending only on γ.

Oscillating term

Let define p (k) = (p

(k) 1 , p (k) 2 , . . . , p (k) n ) ∈ R n as follows: p (k) j = 0,
for j ≤ k, p j , otherwise.

(5.32)

Let

F (k) ( θ) = F ( θ) - 1 2 k j=1 p 2 j θ 2 j .
(5.33)

Note that

F (0) ( θ) = F ( θ). (5.34)
Using (5.31) and the fact that

∂ ∂θ k n j=1 p 2 j θ 2 j = 2p 2 k θ k = O(n -1 ) θ ∞ , (5.35)
we find that all assumptions of Lemma 4.2 hold for the case when we take function F (k) ( θ) instead of the function F ( θ), vector p (k) instead of vector p and for some constants a, b, r 1 , r 2 , c 1 , c 2 > 0 depending only on γ.

Note that θ ∈ Ω =⇒ θ ∞ = O(n ε ).
(5.36)

Taking into account (5.31) and using the Taylor series expansion, we get that

e ip k θ k = e -1 2 p 2 k θ 2 k + ip k θ k + O(n -3/2+3ε ), θ ∈ Ω.
(5.37) Using (5.31) and (4.20), (4.26) for F (k-1) and p (k-1) , we find that

ip k < θ k e i θ T p (k) > F (k-1) ,Ω = = - p k 2 n j=k+1 p j (A -1 ) jk < e i θ T p (k) > F (k) ,Ω +O(n -3/2+5ε ) < 1 >, (5.38)
Combining (4.20), (5.37) and (5.38), we obtain that

< e i θ T p (k-1) > F (k-1) ,Ω = = 1 - p k 2 n j=k+1 p j (A -1 ) jk <e i θ T p (k) > F (k) ,Ω + + O(n -3/2+5ε ) < 1 > .
(5.39) Using (4.10), (5.8), (5.10) and (5.31), we note also that

p j p k (A -1 ) jk = β j β k ( Q-1 ) jk = O(n -2 ), j = k, p k j =k,j≤n p j (A -1 ) jk = O(n -1
).

(5.40)

Using (5.34), (5.40) and (5.39) for k = 1, 2 . . . n, we get that

< e i θ T p > F,Ω = C 1 < 1 > F (n) ,Ω +O(n -1/2+5ε ) < 1 >, (5.41)
where

C 1 = exp - n-1 k=1 n j=k+1 β k ( Q-1 ) jk β j = = n-1 k=1 1 - p k 2 n j=k+1
( Â-1 ) jk p j + O(n -1 ) = O(1).

(5.42)

Taking into account (5.31) and using the Taylor series expansion, we get that e -

1 2 p 2 k θ 2 k = 1 - 1 2 p 2 k θ 2 k + O(n -2+4ε ), θ ∈ Ω.
(5.43)

Combining (5.43) and (4.20), (4.21) for F (k) , we get that

< 1 > F (k) ,Ω = 1 - 1 4 p 2 k < 1 > F (k-1)
,Ω +O(n -2+4ε ) < 1 > .

(5.44) Using (5.31), (5.34) and (5.44) for k = 1, 2 . . . , n, we find that

< 1 > F (n) ,Ω = C 2 < 1 > F,Ω +O(n -1+4ε ) < 1 >, (5.45)
where

C 2 = exp - n k=1 β 2 k 2(d k + 1) = n k=1 1 - 1 4 p 2 k + O(n -1 ) = O(1).
(5.46)

Quadratic term

Let define θ k = (θ k 1 , θ k 1 , . . . , θ k n ) ∈ R n as follows:

θ k j = 0, for j ≤ k, θ j , otherwise.

(5.47)

Let F k ( θ) = -θ T A θ + H k ( θ), H k ( θ) = - 1 12 {v j ,v k }∈EG ∆ 4 jk + 1 2 R( ξ( θ k )).
(5.48)

In absolutely similar way as given in Subsection 5.1, we find that all assumptions of Lemma 4.2 hold for the case when we take F k ( θ) instead of F ( θ) for some constants a, b, r 1 , r 2 , c 1 , c 2 > 0 depending only on γ.

Note that

F 0 ( θ) = F ( θ), (5.49) R( ξ( θ k )) = ξ( θ k ) T R ξ( θ k ) = θ kT S θ k , (5.50)
where matrices R, S are the same that in (5.15), (5.16). Combining (5.48), the Mean Value Theorem and (5.27), we get that

|F k-1 ( θ) -F k ( θ)| = 1 2 |R( ξ( θ k-1 )) -R( ξ( θ k ))| = = 1 2 ∂R( ξ( θ * )) ∂θ k θ k = O(n -1 ) θ 2 ∞ , (5.51)
where θ * lies on the segment between θ k-1 and θ k . Using (5.36), (5.51) and the Taylor series expansion, we get that

e F k-1 ( θ)-F k ( θ) = 1 + F k-1 ( θ) -F k ( θ) + O(n -2+4ε ) = = 1 + 1 2 S kk θ 2 k + n j=k+1 S jk θ j θ k + O(n -2+4ε ), θ ∈ Ω.
(5.52) Using (5.4), (5.16), (5.19), we find that

S kk = e (k)T R e (k) (d k + 1)/2 = O(n -1 ) e (k) 2 2 = O(n -1
).

(5.53) Since (5.27) imply that S ∞ = O(n -1 ), using (4.23), we get that

n j=k+1 S jk < θ j θ k > F k-1 ,Ω ≤ | sup k<j≤n < θ j θ k > F k-1 ,Ω | n j=k+1 |S jk | = = O(n -1+5ε ) S ∞ = O(n -2+5ε ).
(5.54)

Combining (4.20), (4.21), (5.52) and (5.54), we obtain that

< 1 > F k-1 ,Ω = 1 + 1 4 S kk < 1 > F k ,Ω +O(n -2+5ε ) < 1 > .
(5.55) Using (5.49), (5.53) and (5.55) for k = 1, 2 . . . , n, we find that

< 1 > F,Ω = C 3 < 1 > F n ,Ω +O(n -1+5ε ) < 1 >, (5.56)
where

C 3 = exp n k=1 R kk 2(d k + 1) = n k=1 1 + 1 4 S kk + O(n -1 ) = O(1).
(5.57)

Residual term

For a subset Θ of EG we define

F Θ ( θ) = -θ T A θ + H Θ ( θ), H Θ ( θ) = - 1 12 {v j ,v k }∈Θ ∆ 4 jk .
(5.58)

In absolutely similar way as given in Subsection 5.1, we find that all assumptions of Lemma 4.2 hold for the case when we take F Θ ( θ) instead of F ( θ) for some constants a, b, r 1 , r 2 , c 1 , c 2 > 0 depending only on γ.

Note that

F EG ( θ) = F n ( θ), (5.59)
∆ 4 jk = 4θ 4 j (d j + 1) 2 -4 4θ 3 j θ k (d j + 1) 3/2 (d k + 1) 1/2 + 6 4θ 2 j θ 2 k (d j + 1)(d k + 1) - -4 4θ 3 k θ j (d k + 1) 3/2 (d j + 1) 1/2 + 4θ 4 k (d k + 1) 2 ,
(5.60) Combining (4.22), (4.24), (4.25), (5.4) and (5.60), we get that

< ∆ 4 jk > F Θ ,Ω = 3 4 4 (d j + 1) 2 + 6 4 4 (d j + 1)(d k + 1) + + 3 4 4 (d k + 1) 2 < 1 > F Θ ,Ω +O(n -3+7ε ) < 1 > .
(5.61) Using (4.20) and (5.61), we get that

< e -1 12 ∆ 4 jk > F Θ ,Ω = P jk < 1 > F Θ ,Ω +O(n -3+7ε ) < 1 >, (5.62)
where

P jk = 1 - 1 4(d j + 1) 2 - 1 2(d j + 1)(d k + 1) - 1 4(d k + 1) 2 .
(5.63)

Note that 1 -1 n 2 ≤ P jk ≤ 1.

(5.64) Using (4.20), (5.62), we can gradually remove all the edges from the residual term H EG and obtain that

< 1 > F EG ,Ω = {v j ,v k }∈EG P jk < 1 > Ω +O(n -1+7ε ) < 1 > . (5.65)
Combining (4.19) and (5.65), we get that

< 1 > F EG ,Ω = C 4 < 1 > +O(n -1+7ε ) < 1 >, (5.66)
where

C 4 = exp   - 1 4 {v j ,v k }∈EG 1 d j + 1 + 1 d k + 1 2   .
(5.67) Combining (5.41), (5.45), (5.56), (5.59) and (5.66), we find that

< e i p T θ > F,Ω = C 1 C 2 C 3 C 4 < 1 > +O(n -1/2+7ε ) < 1 > . (5.68)
Taking into account (4.10), (5.10), (5.42), (5.46), we get that:

C 1 C 2 = exp - 1 2 β T Q-1 β , β T Q-1 β = α T Q T Q-1 (Q + J) α -α T Q Q-1 J α = = {v j ,v k }∈EG 1 d j + 1 - 1 d k + 1 2 + O(n -1 ).
(5.69) Using again (4.10), (5.10), we find that

R kk = tr(Λ( e (k) ) Q-1 Λ( e (k) ) Q-1 ) = = n j,m=1 Λ jj ( e (k) )( Q-1 ) jm Λ mm ( e (k) )( Q-1 ) mj = 1 + O(n -1 ),
(5.70)

C 3 = exp n k=1 R kk 2(d k + 1) = exp n k=1 1 2(d k + 1) + O(n -1 ) = = exp   1 2 {v j ,v k }∈EG 1 (d j + 1) 2 + 1 (d k + 1) 2   + O(n -1 ).
(5.71) Putting together (3.1), (3.6), (3.12), (5.1), (5.7), (5.13) and (5.66)-( 5.71), we obtain (2.5) and (2.6) for n ≥ n 0 (γ, ε) > 0 (with the exponent 7ε instead of ε). Estimate (2.6) for n ≤ n 0 can be fulfilled by choice of sufficiently large constant C. According to (4.6), A = I +X, X jj = 0, and so for some g 1 ( θ) = g 1 (θ 2 , . . . , θ n )

θ T A θ = φ 2 1 ( θ) + g 1 ( θ). (6.2)
Using (4.6), (6.2) and estimating insignificant parts of Gaussian integral of the following type:

(max{|x|, k 1 }) s e -(x-k 2 ) 2 dx, (6.3)
we find that for r > 0, s ≥ 0

< θ s ∞ > = R n θ s ∞ e -θ T A θ d θ = = +∞ -∞ • • • +∞ -∞ e -g 1 (θ 2 ,...,θn)   +∞ -∞ θ s ∞ e -φ 1 ( θ) 2 dθ 1   dθ 2 . . . dθ n = 1 + O exp(-c 4 n 2ε ) |φ 1 ( θ)|≤rn ε θ s ∞ e -θ T A θ d θ, (6.4)
where c 4 = c 4 (r, ε, s) > 0. Combining similar to (6.4) expressions for φ 1 , φ 2 , . . . φ n , we get that

|| φ( θ)||∞≤rn ε θ s ∞ e -θ T A θ d θ = 1 + O exp(-c 5 n 2ε ) < θ s ∞ >, (6.5)
where c 5 = c 5 (r, ε, s) > 0. Combining (4.9), (6.1) and (6.5) with s = 0, we obtain (4.19). Using (4.16), we find that

| < 1 > F,Ω | ≤ Ω |e F ( θ) |d θ ≤ R n e -θ T A θ+ c 1 n θ T A θ d θ = O(< 1 >). (6.6)
In order to prove (4.21) -(4.25) we use the following two lemmas. The proofs of them are given in Section 7. (4.6) and assumptions (4.16) and ( 4.17) hold for some constants c 1 , c 2 > 0. Let P = P (x) = O(|x| s ) for some fixed s ≥ 0. Then for any T ( θ) such that |T ( θ)| ≤ P ( θ ∞ ) :

Lemma 6.1. Let Ω ⊂ R n be such that U n (r 1 n ε ) ⊂ Ω ⊂ U n (r 2 n ε ) for some r 2 > r 1 > 0. Let A satisfy
< T ( θ) > R n \Ω = O exp(-c 6 n 2ε ) < 1 >, (6.7)
and for any

T ( θ) = T (θ 1 , . . . , θ k-1 , θ k+1 , . . . , θ n ) such that T ( θ) ≤ P ( θ ∞ ): < φ 2 k ( θ) T ( θ) > F,Ω = 1 2 < T ( θ) > F,Ω +O(n -1+4ε ) < | T ( θ)| > F,Ω + +O exp(-c 6 n 2ε ) < 1 >, (6.8) 20 < φ 4 k ( θ) T ( θ) > F,Ω = 3 4 < T ( θ) > F,Ω +O(n -1+4ε ) < | T ( θ)| > F,Ω + +O exp(-c 6 n 2ε ) < 1 >, (6.9) < φ k ( θ) T ( θ) > F,Ω = O(n -1+4ε ) < | T ( θ)| > F,Ω + +O exp(-c 6 n 2ε ) < 1 >, (6.10) < φ 3 k ( θ) T ( θ) > F,Ω = O(n -1+6ε ) < | T ( θ)| > F,Ω + +O exp(-c 6 n 2ε ) < 1 >, (6.11)
where function F is defined by (4.15), vector φ( θ) is defined by (6.1) and constant c 6 = c 6 (r 1 , r 2 , c 1 , c 2 , a, b, ε, P ) > 0.

Lemma 6.2. Let assumptions of Lemma 6.1 hold and s 1 , s 2 , . . . , s n ∈ N∪{0},

M( x) = x s 1 1 • • • x sn n , s = s 1 + . . . + s n > 0.
(6.12)

Let s k = 0 and |{j : s j = 0}| ≤ 3. (6.13)

Then < φ k ( θ)M( φ( θ)) > F,Ω = O(sn -1+(s+4)ε ) < 1 > . (6.14)
Using (4.10), we find that

θ k = φ k + q T k φ, q ∞ = O(n -1
). (6.15)

Combining (6.6), (6.15), Lemma 6.1 and Lemma 6.2, we obtain that:

<δ k ( θ) 2 > F,Ω =< ( q T k φ) 2 > F,Ω = = O(n -2 ) j < φ j ( θ) 2 > F,Ω + j 1 =j 2 | < φ j 1 ( θ)φ j 2 ( θ) > F,Ω | = = O(n -1 ) + O(n -1+5ε ) < 1 >= O(n -1+5ε ) < 1 >, (6.16)
< δ k ( θ) 4 > F,Ω =< ( q T k φ) 4 > F,Ω = O(n -4 ) j < φ j ( θ) 4 > F,Ω + + O(n -4 ) j 1 =j 2 < φ j 1 ( θ) 2 φ j 2 ( θ) 2 > F,Ω + + O(n -4 ) j 1 =j 2 | < φ j 1 ( θ)φ j 2 ( θ) 3 > F,Ω |+ +O(n -4 ) j 1 =j 2 =j 3 | < φ j 1 ( θ)φ j 2 ( θ)φ j 3 ( θ) 2 > F,Ω |+ +O(n -4 ) j 1 =j 2 =j 3 =j 4 | < φ j 1 ( θ)φ j 2 ( θ)φ j 3 ( θ)φ j 4 ( θ) > F,Ω | = = O(n -3 )+O(n -2+4ε ) + O(n -3+7ε ) + O(n -2+7ε )+ + O(n -1+7ε ) < 1 >= O(n -1+7ε ) < 1 >, (6.17)
where

δ k ( θ) = θ k -φ k ( θ). (6.18)
According to (4.6), we have that

δ k ( θ) = δ k (θ 1 , . . . , θ k-1 , θ k+1 , . . . , θ n ) (6.19)
Using (6.6), (6.15), (6.16), (6.17), (6.19) and Lemma 6.1, we obtain that:

< φ k ( θ)δ k ( θ) > F,Ω = = O(n -1+4ε ) < |δ k ( θ)| > F,Ω +O exp(-c 6 n 2ε ) < 1 >= = O(n -1+5ǫ ) < 1 >, (6.20)
< θ 2 k > F,Ω =< (φ k ( θ)+δ k ( θ)) 2 > F,Ω = =< φ k ( θ) 2 > F,Ω +O(n -1+5ǫ ) < 1 >= = 1 2 < 1 > F,Ω +O(n -1+5ǫ ) < 1 > . (6.21) < φ k ( θ)δ k ( θ) 3 > F,Ω = = O(n -1+4ε ) < |δ k ( θ)| 3 > F,Ω +O exp(-c 6 n 2ε ) < 1 >= = O(n -1+7ǫ ) < 1 >, (6.22)
< φ k ( θ) 2 δ k ( θ) 2 > F,Ω = 1 2 + O(n -1+4ε ) < δ k ( θ) 2 > F,Ω + +O exp(-c 6 n 2ε ) < 1 >= = O(n -1+5ǫ ) < 1 >, (6.23)
< φ k ( θ) 3 δ k ( θ) > F,Ω = = O(n -1+6ε ) < |δ k ( θ)| > F,Ω +O exp(-c 6 n 2ε ) < 1 >= = O(n -1+7ǫ ) < 1 >, (6.24)
< θ 4 k > F,Ω =< (φ k ( θ)+δ k ( θ)) 4 > F,Ω = =< φ k ( θ) 4 > F,Ω +O(n -1+7ǫ ) < 1 >= = 3 4 < 1 > F,Ω +O(n -1+7ǫ ) < 1 > . (6.25)
In a similar way as in (6.16), (6.17), using (6.20) -( 6.24), we find that

< δ k ( θ)θ l > F,Ω = O(n -1 ) j < φ j ( θ)θ l > F,Ω = = O(n -1+2ε ) + O(n -1+5ε ) < 1 >= O(n -1+5ε ) < 1 >, (6.26)
< δ k ( θ) 2 θ 2 l > F,Ω = O(n -2 ) j < φ j ( θ) 2 θ 2 l > F,Ω + + O(n -2 ) j 1 =j 2 | < φ j 1 ( θ)φ j 2 ( θ)θ 2 l > F,Ω | = = O(n -1+2ε ) + O(n -1+7ε ) < 1 >= O(n -1+7ε ) < 1 >, (6.27)
< δ k ( θ)θ 3 l > F,Ω = = O(n -1 ) j =l < φ j ( θ)θ 3 l > F,Ω +O(n -1 ) < φ l ( θ)θ 3 l > F,Ω = = O(n -1+7ε ) + O(n -1+4ε ) < 1 >= O(n -1+7ε ) < 1 > . (6.28)
Using (6.6), (6.19), (6.26)-(6.28) and Lemma 6.1, we obtain that:

< φ k ( θ)δ k ( θ)θ 2 l > F,Ω = O(n -1+4ε ) < |δ k ( θ)θ 2 l | > F,Ω + +O exp(-c 6 n 2ε ) < 1 >= = O(n -1+7ǫ ) < 1 >, (6.29)
< θ k θ l > F,Ω =< (φ k ( θ) + δ k ( θ))θ l > F,Ω = O(n -1+5ǫ ) < 1 >, (6.30)
< θ k θ 3 l > F,Ω =< (φ k ( θ) + δ k ( θ))θ 3 l > F,Ω = O(n -1+7ǫ ) < 1 >, (6.31)
< θ 2 k θ 2 l > F,Ω =< (φ k ( θ) + δ k ( θ)) 2 θ 2 l > F,Ω =< φ k ( θ) 2 θ 2 l > F,Ω +O(n -1+7ǫ ) < 1 >= = 1 2 < φ l ( θ) + δ l ( θ)) 2 > F,Ω +O(n -1+7ǫ ) < 1 >= = 1 4 < 1 > F,Ω +O(n -1+7ǫ ) < 1 > . (6.32) Since p ∞ = O(n -1/2
), using the fact that

e 1 2 p 2 k θ 2 k = 1 + O(n -1+2ε ), θ ∈ Ω, (6.33)
and (6.6), we get that

< θ k e i θ T p-ip k θ k > F,Ω =< θ k e i θ T p-ip k θ k > F ′ ,Ω +O(n -1+3ε ) < 1 >, (6.34)
where

F ′ = F -1 2 p 2 k θ 2 k .
It is clear that F ′ satisfy all assumptions of Lemma 6.1. For any

p ′ = (p ′ 1 , p ′ 2 , . . . , p ′ n ) ∈ R n such that p ′ ∞ = O(n -1/2
), we have that

e ip ′ l θ l = 1 + ip ′ l θ l + O(n -1+2ε ), e -ip ′ l θ l = 1 + O(n -1/2+ε ), θ ∈ Ω. (6.35)
Using (6.6), (6.8) and (6.10) with F ′ instead of F , (6.35), we get that

< φ l ( θ)e i θ T p ′ -ip ′ l θ l > F ′ ,Ω = O(n -1+4ε ) < 1 >, < φ l ( θ)δ l ( θ)e i θ T p ′ -ip ′ l θ l > F ′ ,Ω = O(n -1+5ε ) < 1 >, < φ l ( θ)θ l e i θ T p ′ -ip ′ l θ l > F ′ ,Ω =< φ 2 l ( θ)e i θ T p ′ -ip ′ l θ l > F ′ ,Ω + < φ l ( θ)δ l ( θ)e i θ T p ′ -ip ′ l θ l > F ′ ,Ω = = 1 2 < e i θ T p ′ -ip ′ l θ l > F ′ ,Ω +O(n -1+5ε ) < 1 >= = 1 2 < e i θ T p ′ > F ′ ,Ω +O(n -1/2+5ε ) < 1 > . (6.36)
Combining (6.35) and (6.36), we find that

< φ l ( θ)e i θ T p ′ > F ′ ,Ω =< φ l ( θ)e i θ T p ′ -ip ′ l θ l > F ′ ,Ω + + ip ′ l < φ l ( θ)θ l e i θ T p ′ -ip ′ l θ l > F ′ ,Ω +O(n -1+3ε ) < 1 >= = i 2 p ′ l < e i θ T p ′ > F ′ ,Ω +O(n -1+5ε ) < 1 > .
(6.37) Using (6.2), we get that

Un(r 2 n ε ) φ p 1 ( θ) T (θ 2 , . . . , θ n )e -θ T A θ+H( θ) d θ + O exp(-c 6 n 2ε ) < 1 >= = r 2 n ε -r 2 n ε • • • r 2 n ε -r 2 n ε T e -g 1 (θ 2 ,...,θn)+H( θ (1) )   r 2 n ε -r 2 n ε φ p 1 e -φ 2 1 ( θ)+H( θ)-H( θ (1) ) dθ 1   dθ 2 . . . dθ n , p = 0, 1 , 2, 3, 4. (7.5)
Combining (4.9) and (7.4), we find that for θ (1) ∈ U n (r 2 n ε )

r 2 n ε -r 2 n ε φ p 1 e -φ 2 1 ( θ)+H( θ)-H( θ (1) ) dθ 1 = = +∞ -∞ φ p 1 e -φ 2 1 ( θ) dθ 1 + O exp(-c 7 n 2ε ) +∞ -∞ e -φ 2 1 ( θ) dθ 1 + + |φ 1 ( θ)|≤r 3 n ε φ p 1 e -φ 2 1 ( θ) e H( θ)-H( θ (1) ) -1 dθ 1 , p = 0, 1, 2, 3, 4, (7.6)
where c 7 = c 7 (r 2 , c 1 , c 2 , a, b, ε) > 0, r 3 = r 3 (r 2 , c 1 , c 2 , a, b, ε) > 0. For p = 2, 4, we have that:

+∞ -∞ φ 2 1 e -φ 2 1 ( θ) dθ 1 = 1 2 +∞ -∞ e -φ 2 1 ( θ) dθ 1 , +∞ -∞ φ 4 1 e -φ 2 1 ( θ) dθ 1 = 3 4 +∞ -∞ e -φ 2 1 ( θ) dθ 1 , (7.7
)

|φ 1 ( θ)|<r 3 n ε φ p 1 e -φ 2 1 ( θ) e H( θ)-H( θ (1) ) -1 dθ 1 = = O(n -1+4ǫ ) +∞ -∞ φ p 1 e -φ 2 1 ( θ) dθ 1 = = O(n -1+4ǫ ) +∞ -∞ e -φ 2 1 ( θ) dθ 1 ,
for θ (1) ∈ U n (r 2 n ε ), p = 0, 2, 4.

(7.8) Combining (7.2)-(7.8), we obtain (6.8) and (6.9). For p = 1, 3, we have that:

+∞ -∞
φ p 1 e -φ 2 1 ( θ) dθ 1 = 0 (7.9)

|φ 1 ( θ)|≤r 3 n ε φ p 1 e -φ 2 1 ( θ) e H( θ)-H( θ (1) ) -1 dθ 1 = = 0≤φ 1 ( θ)≤r 3 n ε |φ 1 | p e -φ 2 1 ( θ) e H( θ)-H( θ (1) ) -1 dθ 1 - - r 3 n ε ≤φ 1 ( θ)≤0 |φ 1 | p e -φ 2 1 ( θ) e H( θ)-H( θ (1) ) -1 dθ 1 = = O(n -1+4ǫ ) φ 1 ≥0 |φ 1 | p e -φ 2 1 ( θ) dθ 1 = = O(n -1+4ǫ ) +∞ -∞ e -φ 2 1 ( θ) dθ 1 ,
for θ (1) ∈ U n (r 2 n ε ), p = 1, 3.

(7.10) Combining (7.2)-(7.6), (7.8), (7.9), (7.10), we obtain (6.8) and (6.9).

Proof of Lemma 6.2. Let T ( θ) satisfy .11) Combining (6.10) and (7.11), we get that

|T ( θ)| = O( θ s ∞ ), ∂T ( θ) ∂θ k = O(sn -1-ε ) sup θ∈Ω |T ( θ)|, θ ∈ Ω. ( 7
< φ k ( θ)T ( θ) > F,Ω = =< φ k ( θ)T ( θ (k) ) > F,Ω + < φ k ( θ)(T ( θ) -T ( θ (k) ) > F,Ω = =< φ k ( θ)T ( θ (k) ) > F,Ω +O(sn -1-ǫ ) < sup θ∈Ω |φ k θ k T ( θ)| > F,Ω = = O(sn -1+4ǫ ) < sup θ∈Ω |T ( θ)| > F,Ω +O exp(-c 6 n 2ε ) < 1 > . (7.12)
Using (4.6), we find that for θ ∈ Ω

∂M( φ( θ)) ∂θ k = O(sn (s-1)ε ) j:s j =0 ∂ φ j ( θ) ∂θ k = O(sn -1-ε ) sup θ∈Ω |M( φ( θ))|. (7.13)
Combining (6.6) and(7.12), we obtain (6.14)

8 Proof of Proposition 3.1

In this section we use notation f = O(g) meaning that |f | ≤ c|g| for some constant c > 0 depending only on γ and ε.

The following lemma will be applied to estimate the determinant of a matrix close to the identity matrix I. Lemma 8.1. Let denote any matrix norm. Let X be such an n×n matrix that X < 1. Then for fixed m ≥ 2

det(I + X) = exp m-1 r=1 (-1) r+1 r tr(X r ) + E m (X) , (8.1)
where tr(•) is the trace function and

|E m (X)| ≤ n m X m 1 -X . (8.2)
The proof of Lemma 8.1 is based on estimation the trace of the matrix ln(I + X), using the representation as a convergent series. Lemma 8.1 was also formulated and proved in [START_REF] Mckay | Asymptotic enumeration of eulerian circuits in the complete graph[END_REF].

We have that

S 0 = 1 n n r=1 V 0 {v j ,v k }∈EG cos ∆ jk T ∈Tr (v j ,v k )∈ET (1 + i tan ∆ jk ) d ξ, (8.3)
where ∆ jk = ξ j -ξ k and

V 0 = { ξ ∈ U n (π/2) : |ξ j -ξ k | π ≤ n -1/2+ε for any1 ≤ j, k ≤ n}, |ξ j -ξ k | π = min l∈Z |ξ j -ξ k + πl|. (8.4)
Since the integrand is invariant under uniform translation of all the ξ j 's mod π, we can fix n k=1 ξ k = 0 and multiply it by the ratio of its range π to the length n -1/2 of the vector 1 n [1, 1, . . . , 1] T . Thus, for any 1 ≤ r ≤ n, we get that

S 0 = πn 1/2 L∩V 0 ∩Un(n -1/2+ε ) T ( ξ) dL, T ( ξ) = 1 n n r=1 (v j ,v k )∈EG cos ∆ jk T ∈Tr (v j ,v k )∈ET (1 + i tan ∆ jk ), (8.5)
where L denotes the orthogonal complement to the vector [1, 1, . . . , 1] T . Let define n × n matrix B by

B jk =      -tan ∆ jk , for {v j , v k } ∈ EG, l:(v j ,v l )∈EG tan ∆ jl , for k = j, 0 otherwise . (8.6)
Using Theorem 3.1 with the matrix Q + iB, we get that

n r=1 T ∈Tr (v j ,v k )∈ET (1 + i tan ∆ jk ) = n r=1 M r , (8.7)
where M r denotes the principal minor of A formed by removing row r and column r. Since the vector [1, 1, . . . , 1] T is the common eigenvector of the matrices Q and B, corresponding to the eigenvalue 0, we find that

n r=1 M r = det( Q + iB) n , (8.8)
where Q = Q + J and J denotes the matrix with every entry 1. Note that

|∆ jk | ≤ n -1/2+ε , ξ ∈ V 0 ∩ U n (n -1/2+ε ), (8.9
)

||B|| 1 = max j n k=1 |B jk | = O(n 1/2+ε ), ξ ∈ U n (n -1/2+ε ). ( 8.10)
Let Φ = B Q-1 . Using (4.9), (5.4), (5.30) and (8.10), we get that

||Φ|| 1 ≤ ||B|| 1 || Q-1 || 1 = O(n -1/2+ε ), ξ ∈ U n (n -1/2+ε ). (8.11)
Using Lemma 8.1 with the matrix iΦ, we find that

det(I + iΦ) = exp itrΦ + trΦ 2 2 + O(n -1/2+3ε ) , ξ ∈ U n (n -1/2+ε ). (8.12) Let B = B skew + B diag , (8.13)
where B skew is the skew-symmetric matrix and B diag is the diagonal matrix. Since Q is the symmetric matrix tr(B skew Q-1 ) = 0. (8.14)

Using (8.9), we find that

||B diag -Λ|| 2 = O(n -1/2+3ε ), ξ ∈ U n (n -1/2+ε ), (8.15)
where Λ denotes the diagonal matrix whose diagonal elements are equal to the components of the vector Q θ. Combining (5.3) and (8.15), we get that

tr (B diag -Λ) Q-1 ≤ n||B diag -Λ|| 2 || Q-1 || 2 = O(n -1/2+3ε ), ξ ∈ U n (n -1/2+ε
(B diag -Λ) Q-1 B diag Q-1 ≤ ≤ n Q-1 2 2 ||(B diag -Λ)|| 2 ||B diag || 2 = O(n -1+4ε ), ξ ∈ V 0 , (8.24)
and

tr (B diag -Λ) Q-1 (B diag -Λ) Q-1 ≤ ≤ n Q-1 2 2 ||(B diag -Λ)|| 2 2 = O(n -2+6ε ), ξ ∈ V 0 . ( 8
cos ∆ jk = = exp   - 1 2 (v j ,v k )∈EG ∆ 2 jk - 1 12

6

  Proof of Lemma 4.2 In this section we use notation f = O(g) meaning that |f | ≤ c|g| for some c > 0 depending only on r 1 , r 2 , c 1 , c 2 , a, b and ε. Let φ( θ) = (φ 1 ( θ), φ 2 ( θ), . . . , φ n ( θ)) = A θ. (6.1)

(v j ,v k )∈EG ∆ 4 F

 4 jk + O(n -1+6ε ) (v j ,v k )∈EG ∆ 2 jk = ξ T Q ξ. (8.30) Putting together (8.5) for r = 1, 2 . . . , n, (8.7), (8.8), (8.28), (8.29), (8.30), we obtain thatS 0 = πn -3/2 det Q Int ′ + O n -1/2+6ǫ Int ′′ ,(8.31)whereInt ′ = L∩V 0 ∩Un(n -1/2+ε ) exp(i ξ T Q α + F ( ξ))dL, Int ′′ = L∩V 0 ∩Un(n -1/2+ε )e F ( ξ) dL,

( 8 .c 7 >

 87 32)where R( ξ) = tr(Λ( ξ) Q-1 Λ( ξ) Q-1 ).Let Pr( ξ) be the orthogonal projection ξ onto the space L, where L denotes the orthogonal complement to the vector [1, 1, . . . , 1] T . Note thatPr( ξ) = ξ -ξ[1, 1, . . . , 1] T , 2+ε ) ⊂ ξ : Pr( ξ) ∈ V 0 ∩ U n (n -1/2+ε ) (8.35)We also note thatQ ξ = QPr( ξ). (8.36)Therefore the integrand of (8.32) does not change under the substitution of vector ξ by vector Pr( ξ) andInt ′ = Pr( ξ)∈L∩V 0 ∩Un(n -1/2+ε ) e i ξ T Q α+F ( ξ) d ξ )∈V 0 ∩Un(n -1/2+ε ) e i ξ T Q α+F ( ξ) d ξ,(8.37)Int ′′ = Pr( ξ)∈L∩V 0 ∩Un(n -1/2+ε ) e F ( ξ) d ξ ( ξ)∈V 0 ∩Un(n -1/2+ε ) e F ( ξ) d ξ,(8.38)Using notations (5.6) -(5.11), and formulas (4.20), (8.35), (5.68), we get that Int ′ = 1 + O exp(-c 7 n 2ε ) 0 depends only on γ and ε. Combining (8.31) and (8.39), we obtain (3.12).

  ). = tr(B skew Q-1 ) 2 + tr(B diag Q-1 ) 2 + 2 tr B skew Q-1 B diag Q-1 . (8.19)Since B skew is the skew-symmetric matrix and Q-1B diag Q-1 is the symmetric matrix, we find that ||XY || HS ≤ ||X|| HS ||Y T || 2 . || HS ≤ || Q-1 || 2 ||B skew || HS = O(n -1/2+ε ), ξ ∈ V 0 .

	Using (8.14) and (8.16), we obtain that
		trΦ = tr(B diag	Q-1 ) = tr(Λ Q-1 ) + O(n -1/2+3ε ) = = ξ T Q α + O(n -1/2+3ε ), ξ ∈ V 0 ,	(8.17)
	where α is the vector composed of the diagonal elements of the matrix Q-1 .
	Using the property of the trace function
			tr(XY ) = tr(Y X),	(8.18)
	we have that
	trΦ 2 tr B skew	Q-1 B diag	Q-1 = 0.	(8.20)
	According to (5.17), we have that
			trX 2 ≤ ||X|| 2 HS ,	(8.21)
	Therefore we get that
		tr(B skew	Q-1 ) 2 ≤ ||B skew	Q-1 || 2 HS .	(8.22)
	Combining (5.3) and (8.9), we obtain that
	||B skew	Q-1 (8.23)
	Using (5.3), (8.9) and (8.15), we get that
	tr
					(8.16)

  .25) Combining(8.18),(8.24) and(8.25), we obtain thattr(B diag Q-1 ) 2 = tr(Λ Q-1 ) 2 + O(n -1+4ε ), ξ ∈ V 0 . (8.26) Combining (8.19), (8.20), (8.22), (8.23) and (8.26), we obtain that trΦ 2 = tr(Λ Q-1 ) 2 + O(n -1+4ε ), ξ ∈ V 0 . (8.27) Using (8.17) and (8.27) in (8.12), we get thatdet(I + iΦ) = exp i θ T Q α + tr(Λ Q-1 ) 2 2 + O(n -1/2+4ε ) , ξ ∈ V 0 . (8.28)By Taylor's theorem we have that for ξ ∈ V 0 (v j ,v k )∈EG

Acknowledgements

This work was carried out under the supervision of S.P. Tarasov and supported in part by RFBR grant no 11-01-00398a.

Using (4.9), (6.1) and (6.37), we get that

Combining (6.34) and (6.38) for p ′ = p -p k e (k) , we obtain (4.26).

7 Proofs of Lemma 6.1 and Lemma 6.2

In this section we continue use notation

Proof of Lemma 6.1. Using (4.9), (6.1) and (6.5), we find that

For simplicity, let k = 1. Using (7.2), we get that

Combining (4.17) and the Mean Value Theorem, we find that for θ ∈ U n (r 2 n ε ) H( θ) -H( θ (1) ) = O(n -1+4ε ). (7.4)


M I Isaev

K V Isaeva

Asymptotic enumeration of Eulerian orientations for graphs with strong mixing properties

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+ε ), where n is the number of vertices.

Introduction

An Eulerian orientation of the graph G is an orientation of its edges such that for every vertex the number of incoming edges and outgoing edges are equal. We denote EO(G) the number of Eulerian orientations of graph G. It is easy clear that EO(G) = 0, if the degree of at least one vertex of G is odd. An Eulerian orientation of the complete graph K n is called regular tournament.

The problem of counting the number of Eulerian orientations of an undirected simple graph (i.e. graph without loops and multiple edges) is complete for the class #P . Thus this problem is difficult in terms of complexity theory. We recall also that this problem can be reduced to counting perfect matching for some class of bipartite graphs for which it can be done approximately with high probability in polynomial time, see [START_REF] Mihail | On the number of Eulerian orientations of a graph[END_REF].

In addition, for the case of loopless 2d-regular graph G with n vertices the following estimates hold, see [START_REF] Vergnas | Le polynôme de Martin d'un graphe eulérien[END_REF], [START_REF] Schrijver | Bounds on the number of Eulerian orientations[END_REF]:

2 d (2d -1)!! d! n-1 ≤ EO(G) ≤ (2d)! d! • d! n/2
.

(1.1)

An improvement of the upper bound for the regular graph case and some additional studies in this direction were fulfilled in [START_REF] Vergnas | An upper bound for the number of Eulerian orientations of a regular graph[END_REF].

Even for a complete graph K n the exact expression of the number of Eulerian orientations is unknown and only the asymptotic formula was obtained (see [START_REF] Mckay | The asymptotic numbers of regular tournaments, eulirian digraphs and eulirian oriented graphs[END_REF]): for odd n → ∞

EO(K n ) = 2 n+1 πn (n-1)/2 n 1/2 e -1/2 1 + O(n -1/2+ε ) (1.2)
for any fixed ε > 0.

In [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian orientations of graphs[END_REF] the approach of [START_REF] Mckay | The asymptotic numbers of regular tournaments, eulirian digraphs and eulirian oriented graphs[END_REF] was generalized. In particular, the asymptotic behaviour of the number of Eulerian orienations was determined for graphs with large algebraic connectivity. This class of graphs we mean as the class of graphs having strong mixing properties and it can be also defined as the class of graphs having large Cheeger constant (isoperimetric number) or sufficiently large spectral gap from 1 for the second largest eigenvalue of the transition probability matrix of the random walk on the graph and large degree of each vertex. The equivalence of these definitions was proved, for example, in [START_REF] Isaev | On the class of graphs with strong mixing properties[END_REF].

In the present work we continue studies of [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian orientations of graphs[END_REF], [START_REF] Isaev | On the class of graphs with strong mixing properties[END_REF], [START_REF] Mckay | The asymptotic numbers of regular tournaments, eulirian digraphs and eulirian oriented graphs[END_REF]. We prove the asymptotic formula for the number of Eulerian orientations of graphs having strong mixing properties. This result is presented in detail in Section 2 of the present work and was given for the first time, but without proof, in [START_REF] Isaev | On the class of graphs with strong mixing properties[END_REF].

Actually, the estimation of the number of Eulerian orientations was reduced in [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian orientations of graphs[END_REF] to estimating of an n-dimensional integral which is close to Gaussian-type. In Sections 3, 5, 6 we develop an approach for estimating of integrals of such a type.

We note also that in [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian circuits[END_REF] the asymptotic behaviour of the number of Eulerian circuits was determined for graphs having strong mixing properties. Apparently, proceeding from the results of [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian circuits[END_REF] and the estimates of the present work, it is possible to prove the asymptotic formula for the number of Eulerian circuits given in [START_REF] Isaev | On the class of graphs with strong mixing properties[END_REF]. In a subsequent paper we plan to develop this approach.

Main result

Let G be an undirected simple graph with vertex set V G and edge set EG. We define n × n matrix Q by

Q jk =    -1, {v j , v k } ∈ EG, d j , j = k, 0, otherwise, (2.1)
where n = |V G| and d j denotes the degree of

v j ∈ V G. The matrix Q = Q(G)
is called the Laplacian matrix of the graph G. The eigenvalues λ 1 ≤ λ 2 ≤ . . . ≤ λ n of the matrix Q are always non-negative real numbers and λ 1 = 0. The eigenvalue λ 2 = λ 2 (G) is called the algebraic connectivity of the graph G. In addition the following inequalities hold:

2 min j d j -n + 2 ≤ λ 2 ≤ n n -1 min j d j . (2.2)
For more information on the spectral properties of graphs see, for example, [START_REF] Fiedler | Algebraic connectivity of graphs[END_REF] and [START_REF] Mohar | The Laplacian spectrum of graphs, Graph Theory, Combinatorics, and Applications[END_REF].

According to the Kirchhoff Matrix-Tree-Theorem, see [START_REF] Kirchhoff | Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird[END_REF], we have that

t(G) = 1 n λ 2 λ 3 • • • λ n = det M 11 , (2.3)
where t(G) denotes the number of spanning trees of the graph G and M 11 results from deleting the first row and the first column of Q.

We call the graph G as γ-mixing graph, γ > 0, if the algebraic connectivity λ 2 = λ 2 (G) ≥ γ|V G|.

(2.4)

In addition, we recall that (see, [START_REF] Isaev | On the class of graphs with strong mixing properties[END_REF]):

• The class of γ-mixing graphs can be also defined as the class of graphs having sufficiently large Cheeger constant (isoperimetric number) or spectral gap from 1 for the second largest eigenvalue of the transition probability matrix of the random walk on the graph and sufficiently large degree of each vertex.

• Almost all graphs (asymptotically, in some probabilistic sense) are γmixing.

The main result of the present work is the following theorem.

Theorem 2.1. Let G be an undirected simple graph with n vertices v 1 , v 2 , . . . , v n having even degrees. Let G satisfy (2.4) for some γ > 0. Then

EO(G) = (1 + δ(G))   2 |EG|+ n-1 2 π -n-1 2 1 t(G) {vj ,v k }∈EG P jk   , P jk = 1 - 1 4(d j + 1) 2 - 1 2(d j + 1)(d k + 1) - 1 4(d k + 1) 2 , (2.5)
where d j denotes the degree of vertex v j , t(G) denotes the number of spanning trees of the graph G and for any ε > 0

|δ(G)| ≤ Cn -1+ε , (2.6)
where constant C > 0 depends only on γ and ε.

Proof of Theorem 2.1 is given in Section 4. This proof is based on results presented in Section 3.

Remark 2.1. For the complete graph λ 2 (K n ) = n, EK n = n(n-1) 2 , t(K n ) = n n-2 , {vj ,v k }∈EKn P jk = 1 - 1 4n 2 - 1 2n 2 - 1 4n 2 n(n-1) 2 = = e ln(1-1 n 2 ) n(n-1) 2 = e -1/2 + O(n -1 ).
(2.7)

The result of Theorem 2.1 for this case improve the error estimate in (1.2).

Asymptotic estimates of an integral

We fix constants a, b, ε > 0. In this section we use notation f = O(g) meaning that |f | ≤ c|g| for some c > 0 depending only on a, b and ε.

Let p ≥ 1 be a real number and x ∈ R n . Let

x p =   n j=1 |x j | p   1/p . (3.1)
For p = ∞ we have the maximum norm

x ∞ = max j |x j |. (3.2)
The matrix norm corresponding to the p-norm for vectors is

A p = sup x =0 A x p x p . (3.3)
One can show that for symmetric matrix A and p ≥ 1

A p ≥ A 2 . (3.4)
For invertible matrices one can define the condition number

µ p (A) = A p • A -1 p ≥ AA -1 p = 1. (3.5)
Let I be identity n × n matrix and A = I + X be such a matrix that:

A is positive definite symmetric matrix,

|X jk | ≤ a/n, X jj = 0, A -1 2 ≤ b. (3.6)
Note that

A -1 -1 2 ≤ A 2 ≤ A ∞ = A 1 = max j n k=1 |A jk | = O(1). (3.7)
We recall that (see Lemma 3.2 of [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian orientations of graphs[END_REF] ), under assumptions (3.6),

µ ∞ (A) = µ 1 (A) = O(µ 2 (A)). ( 3

6). Then

A -1 ∞ = A -1 1 = O(1), (3.9
)

|X ′ jk | = O(n -1 ), (3.10)
where

X ′ = A -1 -I = A -1 (I -A) = -A -1 X. (3.11)
We use the following notation:

< g > F,Ω = Ω g( θ)e F ( θ) d θ, (3.12)
For r > 0 let

< g > F,r =< g > F,Un(rn ε ) , (3.13)
where

U n (ρ) = {(θ 1 , θ 2 , . . . , θ n ) ∈ R n : |θ j | ≤ ρ for all j = 1 . . . n}. (3.14) Let F ( θ) = -θ T A θ + R( θ), (3.15)
where A satisfy (3.6). We consider the following assumptions on function R:

R( θ) ≤ c 1 θ T A θ n , (3.16
) (3.6) and assumptions (3.16), (3.17) hold for some c 1 , c 2 > 0. Then

∂R( θ) ∂ θ ∞ ≤ c 2 θ 3 ∞ n (3.17) For R ≡ 0 we denote < g > Ω =< g > F,Ω , < g > r =< g > F,r , < g >=< g > +∞ . Proposition 3.2. Let Ω ⊂ R n be such that U n (r 1 n ε ) ⊂ Ω ⊂ U n (r 2 n ε ) for some r 2 > r 1 > 0. Let A satisfy
< 1 > Ω = (1 + O exp(-c 3 n 2ε ) ) < 1 >, (3.18) < 1 > F,Ω = O (< 1 >) , (3.19)
< θ 4 k > F,Ω = 3 4 < 1 > F,Ω +O(n -1+7ε ) < 1 > (3.20)
and, for k = l:

< θ k θ 3 l > F,Ω = O(n -1+7ε ) < 1 >, (3.21) < θ 2 k θ 2 l > F,Ω = 1 4 < 1 > F,Ω +O(n -1+7ε ) < 1 >, (3.22)
where F is defined by (3.15) and

c 3 = c 3 (r 1 , r 2 , c 1 , c 2 , a, b, ε) > 0.
Proof of Proposition 3.2 is given in Section 5.

Proof of Theorem 2.1

The Laplacian matrix Q of the graph G has the eigenvector [1, 1, . . . , 1] T , corresponding to the eigenvalue λ 1 = 0. Let Q = Q + J, where J denotes the matrix with every entry 1. Note that Q and Q have the same set of eigenvectors and eigenvalues, except for the eigenvalue corresponding to the eigenvector [1, 1, . . . , 1] T , which equals 0 for Q and n for Q. Using (2.3), we find that

t(G) = 1 n λ 2 λ 3 • • • λ n = det Q n 2 . (4.1)
Using (3.4), we get that

λ n = ||Q|| 2 ≤ || Q|| 2 ≤ || Q|| 1 = max j n k=1 | Qjk | = n. (4.2)
Then, we find that

|| Q-1 || 2 = 1 λ 2 ≤ 1 γn . (4.3) Using (2.
2), we get that

n -1 ≥ d j ≥ λ 2 n -1 n ≥ γ(n -1). (4.4)
We recall that under assumtions of Theorem 2.1 (see, Proposition 6.1 of [START_REF] Isaev | Asymptotic behaviour of the number of Eulerian orientations of graphs[END_REF])

EO(G) = 1 + O n -1+6ε 2 |EG|-1/2 π -n+1/2 n Int, (4.5)
where

Int = Un(n -1/2+ε ) exp   - 1 2 ξ T Q ξ - 1 12 {vj ,v k }∈EG ∆ 4 jk   d ξ, ∆ jk = ξ j -ξ k . (4.6) Let θ k = (d k + 1)/2 ξ k . (4.7) Then ∆ 4 jk = 4θ 4 j (d j + 1) 2 -4 4θ 3 j θ k (d j + 1) 3/2 (d k + 1) 1/2 + 6 4θ 2 j θ 2 k (d j + 1)(d k + 1) - -4 4θ 3 k θ j (d k + 1) 3/2 (d j + 1) 1/2 + 4θ 4 k (d k + 1) 2 . (4.8) - 1 2 ξ T Q ξ = -θ T A θ, (4.9)
where

A jk = 1 (d j + 1)(d k + 1)
Qjk .

(4.10)

For a subset Θ of EG let

R Θ ( θ) = - 1 12 {vj ,v k }∈Θ⊂EG ∆ 4 jk . (4.11)
Using (4.3), (4.4), (4.8) it is not difficult to find that the assumptions of Proposition 3.2 for

Ω = { θ ∈ R n : ξ ∈ U n (n -1/2+ε )} (4.12)
and

F ( θ) = F Θ ( θ) = -θ T A θ + R Θ ( θ) (4
(d k + 1) 2 < 1 > FΘ,Ω + +O(n -3+7ε ) < 1 > . (4.14) Using (3.19), we get that < e -1 12 ∆ 4 jk > FΘ,Ω = P jk < 1 > FΘ,Ω +O(n -3+7ε ) < 1 >, (4.15)
where

P jk = 1 - 1 4(d j + 1) 2 - 1 2(d j + 1)(d k + 1) - 1 4(d k + 1) 2 . ( 4
< 1 > FEG,Ω = {vj ,v k }∈EG P jk < 1 > Ω +O(n -1+7ε ) < 1 > . (4.18)
Combining (3.18) and (4.18), we get that

< 1 > FEG,Ω =   {vj ,v k }∈EG P jk + O(n -1+7ε )   < 1 > . (4.19) Then Int = Un(n -1/2+ε ) exp   - 1 2 ξ T Q ξ - 1 12 {vj ,v k }∈EG ∆ 4 jk   d ξ = = Un(n -1/2+ε ) exp -θ T A θ + R EG ( θ) d ξ = =   (vj ,v k )∈EG P jk + O(n -1+7ε )   R n exp -θ T A θ d ξ = 1 + O(n -1+7ε ) (2π) n/2 det Q {vj ,v k }∈EG P jk .
(4.20)

Combining (4.1), (4.5), (4.20), we obtain (2.5).

5 Proof of Proposition 3.

2 Let φ( θ) = (φ 1 ( θ), φ 2 ( θ), . . . , φ n ( θ)) = A θ. (5.1)
According to (3.6), A = I + X, X jj = 0, and so for some

g 1 ( θ) = g 1 (θ 2 , . . . , θ n ) θ T A θ = φ 2 1 ( θ) + g 1 ( θ). (5.2)
Using (3.6), (5.2) and estimating insignificant parts of Gaussian integral of the following type:

(max{|x|, k 1 }) s e -(x-k2) 2 dx, (5.3)
we find that for r > 0, s ≥ 0

< θ s ∞ > = R n θ s ∞ e -θ T A θ d θ = = +∞ -∞ • • • +∞ -∞ e -g1(θ2,...,θn)   +∞ -∞ θ s ∞ e -φ1( θ) 2 dθ 1   dθ 2 . . . dθ n = 1 + O exp(-c 4 n 2ε ) |φ1( θ)|≤rn ε θ s ∞ e -θ T A θ d θ, (5.4)
where c 4 = c 4 (r, ε, s) > 0. Combining similar expressions for φ 1 , φ 2 , . . . φ n , we get that

|| φ( θ)||∞≤rn ε θ s ∞ e -θ T A θ d θ = 1 + O exp(-c 5 n 2ε ) < θ s ∞ >, (5.5)
where c 5 = c 5 (r, ε, s) > 0. Combining (3.9), (5.1) and (5.5) with s = 0, we obtain (3.18). Using (3.16), we find that

| < 1 > F,Ω | ≤ Ω |e F ( θ) |d θ ≤ R n e -θ T A θ+ c 1 n θ T A θ d θ = O(< 1 >). (5.6)
In order to prove (3.20) -(3.22) we use the following two lemmas. The proofs of them are given in Section 6. (3.6) and assumptions (3.16) and (3.17) hold. Let P = P (x) = O(|x| s ) for some fixed s ≥ 0. Then for any

Lemma 5.1. Let Ω ⊂ R n be such that U n (r 1 n ε ) ⊂ Ω ⊂ U n (r 2 n ε ) for some r 2 > r 1 > 0. Let A satisfy
T ( θ), |T ( θ)| ≤ P ( θ ∞ ) : < T ( θ) > R n \Ω = O exp(-c 6 n 2ε ) < 1 >, (5.7)
and for any

T ( θ) = T (θ 1 , . . . , θ k-1 , θ k+1 , . . . , θ n ), T ( θ) ≤ P ( θ ∞ ): < φ 2 k ( θ) T ( θ) > F,Ω = 1 2 < T ( θ) > F,Ω +O(n -1+4ε ) < | T ( θ)| > F,Ω + +O exp(-c 6 n 2ε ) < 1 >, (5.8)
< φ 4 k ( θ) T ( θ) > F,Ω = 3 4 < T ( θ) > F,Ω +O(n -1+4ε ) < | T ( θ)| > F,Ω + +O exp(-c 6 n 2ε ) < 1 >, (5.9)
< φ k ( θ) T ( θ) > F,Ω = O(n -1+4ε ) < | T ( θ)| > F,Ω + +O exp(-c 6 n 2ε ) < 1 >, (5.10)
< φ 3 k ( θ) T ( θ) > F,Ω = O(n -1+6ε ) < | T ( θ)| > F,Ω + +O exp(-c 6 n 2ε ) < 1 >, (5.11)
where function F is defined by (3.15), vector φ( θ) is defined by (5.1) and constant c 6 = c 6 (r 1 , r 2 , c 1 , c 2 , a, b, ε, P ) > 0.

Lemma 5.2. Let assumptions of Lemma 5.1 hold. Let s 1 , s 2 , . . . , s n ∈ N ∪ {0},

M ( x) = x s1 1 • • • x sn n , s = s 1 + . . . + s n > 0.
(5.12)

Let s k = 0 and |{j : s j = 0}| ≤ 3.

(5.13)

Then < φ k ( θ)M ( φ( θ)) > F,Ω = O(sn -1+(s+4)ε ) < 1 > .
(5.14) Using (3.10), we find that

θ k = φ k + α T φ, α ∞ = O(n -1
).

(5.15)

Combining (5.6), Lemma 5.1 and Lemma 5.2, we obtain that:

< δ k ( θ) 2 > F,Ω = O(n -2 )   j < φ j ( θ) 2 > F,Ω + j1 =j2 | < φ j1 ( θ)φ j2 ( θ) > F,Ω |   = = O(n -1 ) + O(n -1+5ε ) < 1 >= O(n -1+5ε ) < 1 >, (5.16) < δ k ( θ) 4 > F,Ω = O(n -4 ) j < φ j ( θ) 4 > F,Ω + + O(n -4 ) j1 =j2 < φ j1 ( θ) 2 φ j2 ( θ) 2 > F,Ω + + O(n -4 ) j1 =j2 | < φ j1 ( θ)φ j2 ( θ) 3 > F,Ω |+ + O(n -4 ) j1 =j2 =j3 | < φ j1 ( θ)φ j2 ( θ)φ j3 ( θ) 2 > F,Ω |+ + O(n -4 ) j1 =j2 =j3 =j4 | < φ j1 ( θ)φ j2 ( θ)φ j3 ( θ)φ j4 ( θ) > F,Ω | = = (O(n -3 )+O(n -2+4ε ) + O(n -3+7ε ) + O(n -2+7ε ) + O(n -1+7ε )) < 1 >= = O(n -1+7ε ) < 1 >,
(5.17) where δ k ( θ) = θ k -φ k ( θ).

(5.18)

According to (3.6), we have that

δ k ( θ) = δ k (θ 1 , . . . , θ k-1 , θ k+1 , . . . , θ n ) (5.19)
Using (5.6), (5.16), (5.17), (5.19) and Lemma 5.1, we obtain that:

< φ k ( θ)δ k ( θ) 3 > F,Ω = O(n -1+4ε ) < |δ k ( θ)| 3 > F,Ω +O exp(-c 6 n 2ε ) < 1 >= = O(n -1+7ǫ ) < 1 >, (5.20)
< φ k ( θ) 2 δ k ( θ) 2 > F,Ω = 1 2 + O(n -1+4ε ) < δ k ( θ) 2 > F,Ω + +O exp(-c 6 n 2ε ) < 1 >= = O(n -1+5ǫ ) < 1 >, (5.21) < φ k ( θ) 3 δ k ( θ) > F,Ω = O(n -1+6ε ) < |δ k ( θ)| > F,Ω +O exp(-c 6 n 2ε ) < 1 >= = O(n -1+7ǫ ) < 1 >, (5.22)
For simplicity, let k = 1. Using (6.2), we get that

< φ p 1 ( θ) T ( θ) > F,Ω = Ω φ p 1 ( θ) T (θ 2 , . . . , θ n )e -θ T A θ+R( θ) d θ = = Un(r2n ε ) φ p 1 ( θ) T (θ 2 , . . . , θ n )e -θ T A θ+R( θ) d θ + O exp(-c 6 n 2ε ) < 1 >, p = 1, 2 , 3, 4.
(6.3)

Using (3.17), find that for θ ∈ U n (r 2 n ε ) R( θ) -R( θ (1) ) = O(n -1+4ε ). ( 6.4)
Using (5.2), we get that

Un(r2n ε ) φ p 1 ( θ) T (θ 2 , . . . , θ n )e -θ T A θ+R( θ) d θ + O exp(-c 6 n 2ε ) < 1 >= = r2n ε -r2n ε • • • r2n ε -r2n ε T e -g1(θ2,...,θn)+R( θ (1) )   r2n ε -r2n ε φ p 1 e -φ 2 1 ( θ)+R( θ)-R( θ (1) ) dθ 1   dθ 2 . . . dθ n , p = 0, 1, 2, 3, 4. (6.5)
Combining (3.9) and (6.4), we find that for θ (1) ∈ U n (r 2 n ε )

r2n ε -r2n ε φ p 1 e -φ 2 1 ( θ)+R( θ)-R( θ (1) ) dθ 1 = = +∞ -∞ φ p 1 e -φ 2 1 ( θ) dθ 1 + O exp(-c 7 n 2ε ) +∞ -∞ e -φ 2 1 ( θ) dθ 1 + + |φ1( θ)|≤r3n ε φ p 1 e -φ 2 1 ( θ) e R( θ)-R( θ (1) ) -1 dθ 1 , p = 0, 1, 2, 3, 4, (6.6)
where

c 7 = c 7 (r 2 , c 1 , c 2 , a, b, ε) > 0, r 3 = r 3 (r 2 , c 1 , c 2 , a, b, ε) > 0.
For p = 2, 4, we have that: for θ (1) ∈ U n (r 2 n ε ), p = 0, 2, 4. (6.8) Combining (6.2)-(6.8), we obtain (5.8) and (5.9).

+∞ -∞ φ 2 1 e -φ 2 1 ( θ) dθ 1 = 1 2 +∞ -∞ e -φ 2 1 ( θ) dθ 1 , +∞ -∞ φ 4 1 e -φ 2 1 ( θ) dθ 1 = 3 4 +∞ -∞ e -φ 2 1 ( θ) dθ 1 , (6.7
For p = 1, 3, we have that: for θ (1) ∈ U n (r 2 n ε ), p = 1, 3. (6.10) Combining (6.2)-(6.6), (6.8), (6.9), (6.10), we obtain (5.8) and (5.9). Combining (5.6) and(6.12), we obtain (5.14)

. 8 )

 8 Using (3.4), (3.6), (3.7) and (3.8), it is not difficult to prove the following proposition.Proposition 3.1. Let A satisfy(3.

) |φ1( θ)|<r3n ε φ p 1 e -φ 2 1 ( 1 e -φ 2 1 (

 1111 θ) e R( θ)-R( θ (1) ) -1 dθ 1 = O(n -1+4ǫ ) θ) dθ 1 = = O(n -1+4ǫ ) +∞ -∞ e -φ 2 1 ( θ) dθ 1

ε φ p 1 e -φ 2 1 (

 11 θ) e R( θ)-R( θ (1) ) -1 dθ 1 = = 0≤φ1( θ)≤r3n ε |φ 1 | p e -φ 2 1 ( θ) e R( θ)-R( θ (1) ) -1 dθ 1 --r3n ε ≤φ1( θ)≤0 |φ 1 | p e -φ 2 1 ( θ) e R( θ)-R( θ (1) ) -1 dθ 1 = = O(n -1+4ǫ ) φ1≥0 |φ 1 | p e -φ 2 1 ( θ) dθ 1 = O(n -1+4ǫ ) +∞ -∞ e -φ 2 1 ( θ) dθ 1 ,

Proof of Lemma 5 . 2 .

 52 Let T ( θ) satisfy |T ( θ)| = O( θ s ∞ ), ∂T ( θ) ∂θ k = O(sn -1-ε ) sup θ∈Ω |T ( θ)|, θ ∈ Ω. (6.11)Combining (5.10) and (6.11), we get that< φ k ( θ)T ( θ) > F,Ω =< φ k ( θ)T ( θ (k) ) > F,Ω + < φ k ( θ)(T ( θ) -T ( θ (k) ) > F,Ω = =< φ k ( θ)T ( θ (k) ) > F,Ω +O(sn -1-ǫ ) < sup θ∈Ω |φ k θ k T ( θ)| > F,Ω = = O(sn -1+4ǫ ) < sup θ∈Ω |T ( θ)| > F,Ω +O exp(-c 6 n 2ε ) < 1 > .(6.12) Using (3.6), we find that for θ ∈ Ω∂M ( φ( θ)) ∂θ k = O(sn (s-1)ε ) j:sj =0 ∂ φ j ( θ) ∂θ k = O(sn -1-ε ) supθ∈Ω |M ( φ( θ))|. (6.13)

Acknowledgements

This work was carried out under the supervision of S.P. Tarasov and supported in part by RFBR grant no 11-01-00398a.

Warning

It is preprint of the paper Asymptotic enumeration of Eulerian orientations for graphs with strong mixing properties accepted for publication in the journal Journal of Applied and Industrial Mathematics in 2013, (C) by Pleiades Publishing, Ltd., see also http://www.maik.ru.

(5.23) In a similar way as in (5.16), (5.17), we find that

(5.25) Using (5.6), (5.19), (5.24), (5.25) and Lemma 5.1, we obtain that:

(5.28)

6 Proofs of Lemma 5.1 and Lemma 5.2

Let θ (k) = (θ 1 , . . . , θ k-1 , 0, θ k+1 , . . . , θ n ). (6.1)

Proof of Lemma 5.1. Using (3.9), (5.1) and (5.5), we find that