An analogue of the Harer-Zagier formula for unicellular maps on general surfaces

A unicellular map is the embedding of a connected graph in a surface in such a way that the complement of the graph is simply connected. In a famous article, Harer and Zagier established a formula for the generating function of unicellular maps counted according to the number of vertices and edges. The keystone of their approach is a counting formula for unicellular maps on orientable surfaces with n edges, and with vertices colored using every color in [q] (adjacent vertices are authorized to have the same color). We give an analogue of this formula for general (locally orientable) surfaces.Our approach is bijective and is inspired by Lass?s proof of the Harer-Zagier formula. We first revisit Lass?s proof and twist it into a bijection between unicellular maps on orientable surfaces with vertices colored using every color in [q], and maps with vertex set [q] on orientable surfaces with a marked spanning tree. The bijection immediately implies Harer-Zagier?s formula and a formula by Jackson concerning bipartite unicellular maps. It also shed a new light on constructions by Goulden and Nica, Schaeffer and Vassilieva, and Morales and Vassilieva. We then extend the bijection to general surfaces and obtain a correspondence between unicellular maps on general surfaces with vertices colored using every color in [q], and maps on orientable surfaces with vertex set [q]with a marked planar submap. This correspondence gives an analogue of the Harer-Zagier formula for general surfaces. We also show that this formula implies a recursion formula due to Ledoux for the numbers of unicellular maps with given numbers of vertices and edges.     

Optimal cubature formulas for tensor products of certain classes of functions

We study the problem of constructing an optimal formula of approximate integration along a d-dimensional parallelepiped. Our construction utilizes mean values along intersections of the integration domain with n hyperplanes of dimension (d−1), each of which is perpendicular to some coordinate axis. We find an optimal cubature formula of this type for two classes of functions. The first class controls the moduli of continuity with respect to all variables, whereas the second class is the intersection of certain periodic multivariate Sobolev classes. We prove that all node hyperplanes of the optimal formula in each case are perpendicular to a certain coordinate axis and are equally spaced and the weights are equal. For specific moduli of continuity and for sufficiently large n, the formula remains optimal for the first class among cubature formulas with arbitrary positions of hyperplanes.     

Density condensation of Boolean formulas

The following problem is considered: given a Boolean formula f, generate another formula g such that: (i) If f is unsatisfiable then g is also unsatisfiable. (ii) If f is satisfiable then g is also satisfiable and furthermore g is “easier” than f. For the measure of this easiness, we use the density of a formula f which is defined as (the number of satisfying assignments)/2ⁿ, where n is the number of Boolean variables of f. In this paper, we mainly consider the case that the input formula f is given as a 3-CNF formula and the output formula g may be any formula using Boolean AND, OR and negation. Two different approaches to this problem are presented: one is to obtain g by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms.     

A new proof of the refined alternating sign matrix theorem

In the early 1980s, Mills, Robbins and Rumsey conjectured, and in 1996 Zeilberger proved a simple product formula for the number of n×n alternating sign matrices with a 1 at the top of the ith column. We give an alternative proof of this formula using our operator formula for the number of monotone triangles with prescribed bottom row. In addition, we provide the enumeration of certain 0-1-(−1) matrices generalizing alternating sign matrices.     

On some p-adic properties of Siegel-Eisenstein series

We introduce a formula for the p-adic Siegel-Eisenstein series which demonstrates a connection with the genus theta series and the twisted Eisenstein series with level p. We then prove a generalization of Serre's formula in the elliptic modular case.     

The scattering matrix with respect to an Hermitian matrix of a graph

Recently, Gnutzmann and Smilansky [5] presented a formula for the bond scattering matrix of a graph with respect to an Hermitian matrix. We present another proof for this formula by a technique use in the zeta function of a graph. Furthermore, we generalize Gnutzmann and Smilansky's formula to a regular covering of a graph. Finally, we define an L-function of a graph, and present a determinant expression. As a corollary, we express the generalization of Gnutzmann and Smilansky's formula to a regular covering of a graph by using its L-functions.     

A composition formula for squares of Hermite polynomials and its generalizations

We prove a general formula which, with appropriately chosen parameters, gives a composition formula for squares of Gould–Hopper polynomials g²_n(x,h), and hence also for Hermite polynomials. Our main tool is the classical Mehler formula, but with imaginary arguments. To cite this article: P. Graczyk, A. Nowak, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations

Spectra of first-order formulas are studied. The spectrum of a first-order formula is the set of all positive α such that either this formula is true for the random graph G(n, n ^?α) with an asymptotic probability being neither 0 nor 1 or the limit does not exist. It is well known that there exists a first-order formula with an infinite spectrum. The minimum number of quantifier alternations in such a formula is found.     

Moments of the number of upcrossings of an absolutely continuous process at points of density of a sample path derivative associated set

For a separable process on the unit interval with a.s. absolutely continuous sample paths a kth factorial moment formula is found for the number of sample path upcrossings of zero which occur at points of density (in a weak sense) of the set where the sample path derivative exceeds a fixed value. In the case where the sample path derivative is continuous on the closed unit interval the moment formula reduces to a simple variation of the Cramér-Leadbetter formula for the corresponding kth factorial moment of the number of unconstrained upcrossings.     

The Euler characteristic of a polyhedral product

Given a finite simplicial complex L and a collection of pairs of spaces indexed by the vertices of L, one can define the ??polyhedral product?? of the collection with respect to L. We record a simple formula for its Euler characteristic. In special cases the formula simplifies further to one involving the h-polynomial of L.     

The discriminant of an algebraic torus

For a torus T defined over a global field K, we revisit an analytic class number formula obtained by Shyr in the 1970s as a generalization of Dirichlet?s class number formula. We prove a local-global presentation of the quasi-discriminant of T, which enters into this formula, in terms of cocharacters of T. This presentation can serve as a more natural definition of this invariant.     

The Sixth Power Moment of Dirichlet L-Functions

We prove a formula, with power savings, for the sixth moment of Dirichlet L- functions averaged over all primitive characters χ (mod q) with q ≤?Q, and over the critical line. Our formula agrees precisely with predictions motivated by random matrix theory. In particular, the constant 42 appears as a factor in the leading order term, exactly as is predicted for the sixth moment of the Riemann zeta-function.     

Simplified stress correction factor to study the dynamic behavior of a cracked beam

In this work a simplified formula for the stress correction factor in terms of the crack depth to the beam height ratio, f(a/h), is presented. The modified formula is compared to a well-known similar factor in the literature, and shows a good agreement for a/h lower than 0.5. The modified formula is used to examine the lateral vibration of an Euler–Bernoulli beam with a single-edge open crack. This is done through introducing the flexibility scalar. This scalar can be generated from the Irwins’s relationship using the modified factor f(a/h). The crack in this case is represented as rotational spring. With the modified model, beam configurations with classical and non-classical support conditions could be studied.     

Dimensions of some affine Deligne-Lusztig varieties

This paper concerns the dimensions of certain affine Deligne-Lusztig varieties, both in the affine Grassmannian and in the affine flag manifold. Rapoport conjectured a formula for the dimensions of the varieties Xμ(b) in the affine Grassmannian. We prove his conjecture for b in the split torus; we find that these varieties are equidimensional; and we reduce the general conjecture to the case of superbasic b. In the affine flag manifold, we prove a formula that reduces the dimension question for Xx(b) with b in the split torus to computations of dimensions of intersections of Iwahori orbits with orbits of the unipotent radical. Calculations using this formula allow us to verify a conjecture of Reuman in many new cases, and to make progress toward a generalization of his conjecture.     

The Green polynomials via vertex operators

An iterative formula for the Green polynomial is given using the vertex operator realization of the Hall-Littlewood function. Based on this, (1) a general combinatorial formula of the Green polynomial is given; (2) several compact formulas are given for Green's polynomials associated with upper partitions of length ≤3 and the diagonal lengths ≤3; (3) a Murnaghan-Nakayama type formula for the Green polynomial is obtained; and (4) an iterative formula is derived for the bitrace of the finite general linear group G and the Iwahori-Hecke algebra of type A on the permutation module of G by its Borel subgroup.     

On the eigenvalue problem for Toeplitz band matrices

A formula is given for the characteristic polynomial of an nth order Toeplitz band matrix, with bandwidth k < n, in terms of the zeros of a kth degree polynomial with coefficients independent of n. The complexity of the formula depends on the bandwidth k, and not on the order n. Also given is a formula for eigenvectors, in terms of the same zeros and k coefficients which can be obtained by solving a k × k homogeneous system.     

Singularities of the wave trace for the Friedlander model

There has recently been renewed interest in the trace formula–in particular, that of the initial case of GL(2)–due to counting applications in the function field case. For these applications, one needs a very precise form of the trace formula, with all terms computed explicitly. Our aim in this work is to compute the trace formula for GL(2) over a number field in as full detail as was done for the function field case and to give an accessible exposition, being motivated by these applications to counting, but also by pure curiosity as to the optimal form of this plastic formula. We also explain a correction argument in our context here of GL(2). The idea is to introduce a global summand which does not change the formula globally but changes the local weighted orbital integrals at the hyperbolic terms, so that their limit at the identity becomes a unipotent contribution to the trace formula. This gives a harmonious and pleasing form to the formula. Finally, we put the trace formula in an invariant form; thus all its terms are distributions whose value at a test function f ^y (x) = f(y ^?1 xy) is independent of y in GL(2,A).     

Some Results on the Coefficients of Integrated Expansions of Ultraspherical Polynomials and their Integrals

The formula of expressing the coefficients of an expansion of ultraspherical polynomials that has been integrated an arbitrary number of times in terms of the coefficients of the original expansion is stated in a more compact form and proved in a simpler way than the formula of Phillips and Karageorghis (1990). A new formula is proved for the q times integration of ultraspherical polynomials, of which the Chebyshev polynomials of the first and second kinds and Legendre polynomials are important special cases. An application of these formulae for solving ordinary differential equations with varying coefficients is discussed.     

The several transformation formula in several complex variables and its applications

In this paper, by the method of global analysis, the authors give a new global integral transformation formula and obtain the Plemelj formula with Hadamard principal value of higher-order partial derivatives for the integral of Bochner-Martinelli type on a closed piecewise smooth orientable manifold C ⁿ . Moreover, the authors obtain the composition formula, Poincaré-Bertrand extended formula of the corresponding singular integral. As the application of some results, the authors also study a higher-order Cauchy boundary problem and a regularization problem of higher-order linear complex differential singular integral equation with variable coefficients.     

A new Leray formula for smooth functions on bounded domains in C n

By means of a new technique of integral representations in C ⁿ given by the authors, we establish a new abstract formula with a vector function W for smooth functions on bounded domains in C ⁿ , which is different from the well-known Leray formula. This new formula eliminates the term that contains the parameter A from the classical Leray formula, and especially on some domains the uniform estimates for the $\bar \partial - equation$ are very simple. From the new Leray formula, we can obtain correspondingly many new formulas for smooth functions on many domains in C ⁿ , which are different from the classical ones, when we properly select the vector function W.