text:
# Aspects of Confinement: a Brief Review

## 1 Definitions of Confinement

Confinement is the poster boy of nonperturbative physics for good reason: it is associated with a linear potential with a string tension,

$$\sigma \mathrm{\Lambda }^2\mathrm{e}^{{\scriptscriptstyle {\scriptscriptstyle \frac{dg}{\beta (g)}}}}$$

which is nonperturbative in the coupling.

Although this statement has intuitive appeal, one must be careful in defining confinement. For example, it is often loosely defined as the absence of free quarks in nature. But it is conceivable, and even possible, that there exists a coloured scalar particle which can form bound states with quarks. The resultant particles would then carry flavour and fractional electric chargeG , which is likely not the intent of the definition.

Similarly, requiring that all observable particles be colour singlets encompasses gauge theories in both the confinement and the Higgs phases. The latter also manifests colour singlet states because colour charge is completely screened.

One may hope to improve the situation by focussing on the expected physical properties of confinement. For example, the appearance of a long range linear potential between quarks is a reasonable requirement. Of course, the problem here is that string breaking will occur once the potential energy approaches the quark pair creation threshold. The conventional way out of this difficulty is to consider the work to separate two quarks as the quark masses approach infinity. Thus one is led to the strange position of defining quark confinement in a limit which removes quarks from the theory.

### 1.1 Centre Vortices

It is traditional to implement the last definition in lattice gauge theory with the aid of the Wilson loop:

$$WL=DU_{\mathrm{}}\mathrm{tr}[\underset{iC}{}U_i]\mathrm{e}^{S_{YM}}$$
(1)
where $`C`$ is a large planar loop and the pure gauge action is given by

$$S_{YM}=\frac{6}{g^2}\underset{P}{}\left(1\frac{1}{N_c}\mathrm{}\mathrm{tr}[U_P]\right).$$
(2)
Here the gluonic degrees of freedom are represented by link variables $`U_{\mathrm{}}=\mathrm{exp}(igT^aA_\mu ^a(x))`$ where $`\mathrm{}`$ represents a link on a spacetime lattice which starts at the point $`x`$ and points in the $`\widehat{\mu }`$ direction and the lattice spacing has been set to unity. The sum in the action is over plaquettes, $`P`$, which are the smallest closed loops permitted on the lattice. $`U_P`$ is a product of link variables around a plaquette and is thus a lattice implementation of the two-forms of gauge theories. It is measurements of the Wilson loop which have provided the most compelling demonstrations of the confinement phenomenon.

The lattice definition of QCD and confinement makes it especially easy to see the significance of the centre group of SU(3). The centre is defined as the set of all elements of the gauge group which commute with all other elements. Evidently these are given by the set $`\{z=\mathrm{exp}(2\pi n/N_c)\}`$ where $`n=0,\mathrm{},N_c1`$. This set forms the group $`Z_{N_c}`$. It is clear that multiplying all temporal link variables on a particular time slice by an element of the group , $`U_t(t_0,𝐱)zU_t(t_0,𝐱)`$ does not change the value of a plaquette, implying that QCD is invariant under global $`Z_{N_c}`$ transformations.

We now consider a Wilson loop which extends in the temporal direction for the entire length of the lattice (and, because of the imposition of boundary conditions, encircles the lattice), called a Polyakov line. If one makes the transformation discussed above it is clear that the Polyakov line picks up a phase: $`PL(𝐱)zPL(𝐱)`$. Since the theory is invariant under such a transformation one must have either $`PL(𝐱)=0`$ if the vacuum of QCD shares the symmetry of the action or $`PL(𝐱)0`$ if the theory is in the $`Z_{N_c}`$ broken phase.

The connection with confinement arises once it is realized that the Polyakov line measures the free energy of a static quark at the position $`𝐱`$: $`PL(𝐱)=\mathrm{exp}(ET)`$ where $`T`$ is the temporal extent of the lattice. But the free energy of an isolated confined quark is infinite, thus QCD must be in the unbroken $`Z_{N_c}`$ symmetry phase if it is confining.

It is useful to note that $`Z_{N_c}`$ transformations are an example of “singular gauge transformations” (which are not gauge transformations!), namely they may be generated by performing a gauge transformation which is periodic modulo a $`Z_{N_c}`$ phase factor:

$$U_t(t,𝐱)g(t,𝐱)U_t(t,𝐱)g^{}(t+1,𝐱)$$
(3)
with $`g(T+1,𝐱)=z^{}g(1,𝐱)`$. For example the symmetry transformation $`U_t(t_0,𝐱)zU_t(t_0,𝐱)`$ may be achieved by setting $`g(t,𝐱)=1`$ for $`tt_0`$ and $`g(t,𝐱)=z^{}`$ for $`t>t_0`$. Singular gauge transformations are of central interest to the study of confinement because the structures associated with them are often postulated to cause confinement. We shall return to this in section III below.

### 1.2 Kugo-Ojima Criteria

The final definition of confinement to be considered here was first investigated by Kugo and Ojima shortly after the invention of QCDKO . Their starting assumption was that only BRST singlets may be allowed as physical states if confinement is to hold. A sufficient condition for this is that the ghost propagator in Landau gauge is enhanced in the infrared:

$$D_G(k)=\frac{1}{k^2}\frac{1}{1+u(k^2)}\frac{G(k^2)}{k^2}$$
(4)
with $`u(0)=1`$. This may be related to the gluon propagator via Dyson-Schwinger equations and implies that there is an infrared suppression of the transverse gluon correlator:

$$D_{\mu \nu }(k)=\frac{Z(k^2)}{k^2}\left(\delta _{\mu \nu }\frac{k_\mu k_\nu }{k^2}\right)$$
(5)
with $`Z(k^2)/k^20`$ as $`k0`$TK .

It is interesting to note that these criteria are consistent with results derived by Zwanziger in noncovariant gaugesZ .

## 2 Properties of Confinement

At present the only reliable method for determining properties of confinement is with lattice computations. Indeed, the detection of confinement (with the Wilson loop) was one of the first lattice computations and it continues as the standard bearer of lattice gauge theory.

Recent investigations have revealed much beyond the static quark interaction. Perhaps the most famous examples are plots of action or field density which clearly show the formation of tubes of gluonic flux forming between the colour source and sinkBali . Of course, such tubes fit in very well with the naive notion of linear quark confinement. More interesting is recent investigations of the dynamics of flux tubes, as represented by the higher surfaces in Fig. 1(left). These may be interpreted as adiabatic energy surfaces describing hybrid mesons.

Another type of flux tube investigation places small kinks in Wilson loops to study the spin-dependence of the long range confining forceWLspin . The results are consistent with the supposition that confinement is of a Lorentz scalar nature (it is important to note, however, that mapping the lattice results to this type of interaction is an effective, low energy approximation only).

Casimir Scaling

Figure 1(right) shows in a compelling way the property of Casimir scaling of confinement. The figure was obtained by measuring the Wilson loop for sources in various representations of SU(3). The interaction between colour triplets is the lowest surface in the figure and forms the template for the others. In the figure one sees higher surfaces with sources in the 8, 6, 15A, 10, 27, 24, and 15S representations. The curves are obtained by multiplying a fit to the lowest (fundamental representation) surface by the quadratic Casimir, $`𝒞_R^2=R|T^aT^a|R`$ divided by $`𝒞_F^2`$. The quadratic Casimir is given by $`(p^2+q^2+pq)/3+p+q`$ where $`(p,q)`$ is the Dynkin index of the representation. The agreement is remarkable and is a strong indication that the colour structure of confinement may be written as

$$\overline{\psi }T^a\psi \mathrm{}\overline{\psi }T^a\psi $$

where the ellipsis represents Lorentz and spatial dependence.

String Behaviour

In pre-QCD days strings were invoked as a fundamental theory of QCD. With the advent of QCD, strings have survived as an effective description of flux tubes. In particular one expects that

(i) transverse flux tube profiles should be logarithmically divergent with the tube length (due to string ‘roughening’);

(ii) the ground state potential should exhibit a universal ‘Luescher term’, $`\pi /(12R)`$;

(iii) the string excitation spectrum should be that of bosonic string modes, $`\pi /R`$.

Juge, Kuti, and Morningstar have carried out a detailed analysis of the relationship of the hybrid surfaces of Fig. 1(left) to string excitationsJKMstring . They have found that surface excitations only have $`\pi /R`$ splittings for very large source separation (roughly 4 fermi or greater); see Figure 2(left). Furthermore, there is a cross over region at about 1 fermi where the surfaces move from a perturbative behaviour (characterized by the ‘gluelump’ spectrum) to a string-like behaviour.

Point (ii) has been examined with a new algorithm by Luescher and WeiszLW ; their main results are shown in Figure 2(right). One sees that the expected behaviour of the confinement potential is achieved at a source separation of roughly 1/2 fm or less. String-like behaviour at such short distances may be called precocious and is very difficult to understand in light of the conclusion of Juge, Kuti, and Morningstar. It appears that the existence of a $`1/r`$ interaction with the expected Luescher coefficient is not necessarily indicative of string dynamics.

Baryonic Flux Tubes

Finally, investigations of the static baryon interaction have begun. The chief point of interest is whether the expected flux tubes form into a ‘Y’ shape or a ‘$`\mathrm{\Delta }`$’ shape (ie., is the effective baryonic quark interaction two-body or three-body?). This may be addressed by carefully examining the baryonic energy under a variety of quark configurations. Figure 3 shows the flux tube which arises in one such configuration (which seems to be an interpolation of Y and $`\mathrm{\Delta }`$). Current results are mixed, with some groups claiming support for the two-body hypothesis Alexandrou  and some for the three-body hypothesisSuganuma . Finally, a strong operator dependence in the flux tube profiles has been observedOW , which clearly needs to be settled before definitive conclusions can be reached.

## 3 Ideas of Confinement

The final portion of this report deals with analytic attempts to describe confinement. Unfortunately, there is a great deal of prejudice concerning this issue, with many people believing that any such attempts cannot succeed. This is not a useful point of view to take and is, in fact, at odds with generations of successes in field theory, many-body physics, and condensed matter physics:

nonperturbative does not mean intractable!

A trivial example is provided by elementary calculus. As is well known the function $`f(x)=\mathrm{e}^{\frac{1}{x}}`$ has a zero radius of convergence and hence no sensible ‘perturbation theory’. However, if a sufficiently clever theorist were able to derive the ‘Dyson-Schwinger’ differential equation $`f^{}(x)=\frac{1}{x^2}f(x)`$, almost anyone could then derive any desired property of $`f`$.

More substantial examples are provided by the Gell-Mann – Brueckner resolution to the infrared divergence problem in the degenerate electron gas, the Galitskii method for dealing with strong short range repulsive interactions in nuclear physics, and Laughlin’s explanation of the fractional quantum Hall effect.

The point is this: QCD is described by a Lagrangian and therefore all of the properties of QCD are carried by its diagrams. To make progress nonperturbatively one must find an infinite set of diagrams to ‘sum’ which capture the majority of the physics one is interested in. It would be a completely new occurrence in physics if this approach should not work for confinement, requiring the introduction of a concept such as ‘intrinsic incomputability’ (with commensurate implications for attempts at deriving the ‘theory of everything’).

In the following a very brief summary of Dyson-Schwinger and Green’s function approaches to confinement are presented. I shall also recall some salient features of the vortex picture of confinement. Space constraints forbid discussing many other popular ideas of confinement such as the dual superconductor picture, merons, and monopoles.

### 3.1 The Dyson-Schwinger Formalism

There has been much progress in the Dyson-Schwinger approach to confinement in recent years. The idea is to truncate the infinite series of Dyson-Schwinger equations (which are equivalent to the field theory) in such a way that the leading infrared behaviour of the ghost and gluon propagators may be reliably extracted. This endeavour is assisted by appealing to known properties of nonperturbative vertices, either through Slavnov-Taylor identities, the application of BRST symmetries, or properties of special gauges (in particular, the ghost-gluon vertex is not renormalized in Landau gauge). It has been found that including the ghost propagator in the coupled set of D-S equations is important. One may then solve for the infrared behaviour of the ghost and gluon propagators under various approximations or solve the coupled integral equations numericallyDS .

A convincing demonstration of confinement results. Analytic work finds that the infrared propagators behave as

$$Z(k)\left(\frac{k^2}{\sigma }\right)^{2\kappa },k0$$
(6)
and

$$G(k)\left(\frac{\sigma }{k^2}\right)^\kappa ,k0.$$
(7)
with $`\kappa 0.6`$. This value is very stable under modification of the truncations or Ansätze. Equations 6 and 7 demonstrate that the Kugo-Ojima confinement criteria are met. Furthermore, numerical solutions are in remarkable agreement with lattice resultsAF , indicating the utility of the truncations made.

### 3.2 Green’s Function Approach in Coulomb Gauge

It has been 25 years since Gribov first noted that the imposition of Coulomb gauge in non-Abelian theories is beset with ambiguitiesgribov . The ambiguity arises because more than one solution to the gauge constraint, $`\mathbf{}𝐀=0`$ may exist. Gribov showed that the condition for this to occur was that nontrivial solutions to the equation $`\mathbf{}𝐃=0`$ had to exist. Here $`𝐃`$ is the covariant derivative in adjoint representation. Gribov proposed to resolve the ambiguity by restricting the gauge configurations to those with a positive definite value of $`det(\mathbf{}𝐃)`$, called the Gribov region. He also noted that such a constraint imposes a boundary in field space, and this boundary can affect the gluon dispersion relation, causing confinement.

Much progress has occurred since Gribov framed his conjectures. It is now known that the Gribov region does not resolve the Gribov ambiguity, rather a smaller region called the fundamental modular region (FMR) is required. Furthermore, the FMR is contained in the Gribov region, the FMR incloses the origin, it is convex, and its boundary sometimes coincides with the boundary of the Gribov regionPvB . Topological field configurations are realized through the imposition of nontrivial boundary conditions at the boundary of the FMR. Finally, Zwanziger has argued that physical matrix elements draw their support solely from the intersection of the Gribov and fundamental modular boundariesZ4 .

It is suggestive that the operator $`\mathbf{}𝐃`$ appears in the instantaneous portion of the interaction in the QCD Hamiltonian in Coulomb gaugeCL :

$$V_{Coul}=\frac{1}{2}d^3xd^3y𝒥^1\rho ^a(𝐱)𝐱a|\frac{g}{\mathbf{}𝐃}\mathbf{}^2\frac{g}{\mathbf{}𝐃}|𝐲b𝒥\rho ^b(𝐲)$$
(8)
where $`𝒥=det(\mathbf{}𝐃)`$ is the Faddeev-Popov determinant and the colour density is given by $`\rho ^a=f^{abc}𝐀^b(𝐱)𝐄^c(𝐱)`$. If vacuum field configurations are dominated by those near the boundary of the Gribov region there will be a strong infrared enhancement of the instantaneous interaction, which may cause confinement. This old observation has recently received support from several lattice computationsCZ ; GO .

It is known that the non-Abelian Coulomb interaction is renormalization group invariant and that it generates the complete running coupling of QCDZ2 . Furthermore, quarks decouple from transverse gluons in the static limit and therefore this interaction must generate confinement. Indeed, Zwanziger has recently shown that the non-Abelian Coulomb interaction provides an upper bound to the Wilson loop interactionZ3  and has conjectured that this bound is saturated (numerical evidence in favour of this conjecture is provided in Ref. CZ ).

It is clear that the instantaneous interaction is an important element of QCD. Recently an analytical attempt to understand this operator has been made in the Greens function approachss7 . The central idea was to compute the kernel appearing in Eq. 8 by summing all diagrams which contribute at leading order in the infraredss . The resulting Dyson equation was solved with the gluon propagator equation (which was obtained with the aid of a Gaussian Ansatz for the pure gauge vacuum). Numerical solution of the coupled nonlinear integral equations yielded a nontrivial gluonic quasiparticle dispersion relation and a linearly confining instantaneous interaction in remarkable agreement with lattice Wilson loop resultsss7 . These results are in agreement with the Kugo-Ojima confinement criteria, namely the inverse Faddeev-Popov operator (which is the Coulomb gauge analogue of the ghost propagator) is infrared enhanced. The infrared behaviour of the transverse gluon propagator is more problematic, but it is now understood to arise from strong modifications of the vacuum Ansatz near the Gribov boundarys .

### 3.3 Vortices

Singular gauge transformations generate local objects of great interest. For example, zero-dimensional gauge dislocations are associated with instantons, one-dimensional with monopoles, and two-dimensional with vortices. A vortex is a sheet (in 4-d) of infinite field strength which is associated with a $`Z_{N_c}`$ singular gauge transformation (see Ref. KL0  for more details). It has been postulated that vortices drive confinementvortices  because they are localized field configurations which percolate the lattice. The argument is quite general and relies on the fact that localized field distributions contribute independently to the expectation value of the Wilson loop operator, and hence yield an area law interaction.

There are many other attractive features of the vortex confinement picture, for example, deconfinement may be viewed as a vortex de-percolation phase transitionKL2  and the vortex density has been shown to scale in maximal centre gauge, thereby establishing their physical naturescaling . Lastly, it has recently been shown that monopoles may be understood in terms of vortex self intersections, thereby introducing topological field configurations into the discussionHR .

This compelling picture is strongly supported by lattice computations permitted by recent advances in lattice gauge fixing algorithms. In particular figure 4 shows that the Wilson loop string tension is maintained if one projects onto vortex gauge configurations (upper green line) and that linear confinement disappears if vortices are removed (lower red line).

## 4 Conclusions

Great strides have been made recently in the effort to understand confinement. New lattice algorithms allow a detailed study of the importance of different model gauge configurations and of the onset of string-like behaviour in flux tubes. Multiquark states are also beginning to be probed. At the same time, analytical methods are rapidly approaching the time when quantitatively accurate computations of nonperturbative phenomena are possible. And we are already seeing convincing demonstrations of the general features of confinement.

Of course much remains to be done. The analytical formalisms need to examine the robustness of the assumed truncations and the effects of topology and boundary conditions. At the same time, these approaches can check and compare with a new breed of fixed-gauge lattice results. There are many open issues in the lattice approach a well. For example, too many models of the QCD vacuum seem to be supported by the lattice and one needs to find some commonality among the different mechanisms and gauges. It is hoped and likely that issues such as the nature of baryonic flux tubes, the infrared behaviour of the Landau gauge gluon propagator, the onset of stringiness in flux tubes (is it at 1/2 or 4 fermi?), and the nature of the non-Abelian Coulomb interaction will all be resolved in the short term.

I am grateful to the organizers of Hadron03 for the invitation to speak on such a fascinating topic and for providing a wonderful venue for discussing hadronic physics. I wish to thank Reinhard Alkofer, Pierre van Baal, Jeff Greensite, Hugo Reinhardt, Adam Szczepaniak, and Daniel Zwanziger for many illuminating discussions on this topic. This work was supported by the DOE under contracts DE-FG02-00ER41135 and DE-AC05-84ER40150.


format: text

text:
# 1 Introduction

## 1 Introduction

The global structure of many four-dimensional inflationary universes is very rich . Self-reproduction of inflationary domains leads to a universe consisting of many large domains. In each of these domains there can be different realizations of the inflationary scenario. This property of standard inflation alleviates the problem of fine tuning in inflation. The process of self-reproduction of inflationary domains leads globally to eternal inflation, namely, there is at least one inflating region in the universe. Self-reproduction of inflationary domains can be understood as a branching diffusion process in the space of field values of the inflaton. The probability distributions found in such a way will give the probabilities of finding a certain field value at a certain point in space-time.

There is an interesting connection between the stochastic approach to inflation and quantum cosmology. The probability of finding the universe in a state characterized by certain parameters assuming the Hartle-Hawking no-boundary condition yields the same exponential behaviour as the stationary probability distribution in a comoving volume derived from stochastic inflation. This is the case for standard chaotic inflation. As it turns out this also holds for chaotic inflation on the brane.

The idea that the universe is confined to a brane embedded in a higher dimensional bulk space-time has received much attention in recent years. In the one brane Randall-Sundrum scenario the brane is embedded in a five-dimensional bulk space-time with negative cosmological constant $`\mathrm{\Lambda }_5`$ . Chaotic inflation on the brane in this setting has been investigated in . The form of the spectrum of perturbations is modified due to the modified dynamics at high energies. Therefore, it seems to be interesting to investigate stochastic inflation on the brane.

## 2 Inflation on the brane

In a braneworld scenario 4D Einstein gravity is recovered on the brane with some corrections at high energies. Furthermore there are corrections due to the gravitational interaction with the bulk space-time. Assuming a fine tuning between the brane tension and the bulk cosmological constant $`\mathrm{\Lambda }_5`$ leads to the vanishing of the 4D cosmological constant on the brane. Neglecting contributions from the dark radiation term, this leads to the following Friedmann equation on the brane

$`H^2={\displaystyle \frac{8\pi }{3M_4^2}}\rho \left(1+{\displaystyle \frac{\rho }{2\lambda }}\right),`$ (2.1)
where $`\rho `$ is the energy density on the brane, $`\lambda `$ the (positive) brane tension and $`M_4`$ the four-dimensional Planck mass. This is related to the five-dimensional Planck mass $`M_5`$ by

$`M_4=\sqrt{{\displaystyle \frac{3}{4\pi }}}\left({\displaystyle \frac{M_5^2}{\sqrt{\lambda }}}\right)M_5.`$ (2.2)
Assuming that matter on the brane is dominated by a scalar field $`\varphi `$, confined to the brane, with potential $`V(\varphi )`$, its equation of motion is given by

$`\ddot{\varphi }+3H\dot{\varphi }+V^{}(\varphi )=0.`$ (2.3)
In the slow roll approximation,

$`H^2`$ $``$ $`{\displaystyle \frac{8\pi }{3M_4^2}}V\left(1+{\displaystyle \frac{V}{2\lambda }}\right)`$ (2.4)
$`\dot{\varphi }`$ $``$ $`{\displaystyle \frac{V^{}}{3H}}.`$ (2.5)
For $`\lambda \mathrm{}`$ the usual Friedmann equation is recovered. For $`V\lambda `$ brane effects dominate.

Inflation takes place if the Hubble parameter satisfies $`|\dot{H}|<H^2`$. In a braneworld with matter given by a scalar field the condition for inflation yields to

$`\dot{\varphi }^2V+{\displaystyle \frac{\dot{\varphi }^2+2V}{8\lambda }}\left(5\dot{\varphi }^22V\right)<0.`$ (2.6)
In the following, the potential of the inflaton will be taken to be of the form,

$`V={\displaystyle \frac{1}{2}}m^2\varphi ^2.`$ (2.7)
Furthermore, for convenience, everything will be expressed in four-dimensional Planck units, hence $`M_41`$.

## 3 Eternal inflation on the brane

The evolution of a scalar field in an inflationary universe is determined by two contributions. On the one hand, there is the classical rolling down of the scalar field down its potential. On the other hand, there are quantum fluctuations of the inflaton which become classical outside the horizon. This latter contribution can have either positive or negative sign. The classical rolling down is given by, $`\mathrm{\Delta }\varphi \dot{\varphi }\mathrm{\Delta }t`$, where in the slow roll approximation $`\dot{\varphi }`$ is given by $`\dot{\varphi }\frac{V^{}}{3H}`$. The amplitude of a quantum fluctuation is given by $`\delta \varphi =\frac{H}{2\pi }`$. In a typical time interval $`H^1`$, $`e^3`$ new domains appear each containing an almost homogeneous field $`\varphi \mathrm{\Delta }\varphi +\delta \varphi `$ . There is a critical value $`\varphi _s`$ for which for all $`\varphi \varphi _s`$ quantum fluctuations dominate over the classical evolution towards smaller field values. This is the regime of self-reproduction of inflationary domains. $`\varphi _s`$ is determined by

$`{\displaystyle \frac{2\pi }{3}}{\displaystyle \frac{V^{}}{H^3}}|_{\varphi =\varphi _s}=1.`$ (3.8)
For field values $`\varphi \varphi _s`$ there will be domains in which quantum jumps lead to an increase in the field value of the inflaton. In a small percentage of domains this will lead to the maximal field value at which inflation takes place. The upper boundary $`\varphi _{5\mathrm{D}}`$ in this braneworld model is determined by the five-dimensional Planck boundary. For energies higher than $`V(\varphi _{5\mathrm{D}})=M_5^4`$ the scalar field becomes deconfined and flows off the brane into the bulk . As in the four-dimensional case inflation will stop at this boundary. Here one might argue that inflation on the brane stops since the scalar field is flowing off the brane and thus four-dimensional inflation can no longer be sustained on the brane. Thus the upper boundary is given by

$`\varphi _{5\mathrm{D}}=\sqrt{2}\left({\displaystyle \frac{4\pi }{3}}\right)^{\frac{1}{3}}{\displaystyle \frac{\lambda ^{\frac{1}{3}}}{m}}.`$ (3.9)
In the low energy regime, $`V\lambda `$ the Friedmann equation on the brane reduces to the standard one,

$`H^2{\displaystyle \frac{8\pi }{3}}V.`$ (3.10)
It will be assumed that the whole period of inflation takes place in the low energy regime. The end of inflation $`\varphi _e`$ is determined by the first two terms in (2.6), $`\dot{\varphi }^2=V`$, which yields, $`\varphi _e=1/\sqrt{6\pi }`$. Furthermore, $`\varphi _e<\varphi _{5\mathrm{D}}`$ implies $`\lambda >(12\pi )^{3/2}(3/4\pi )m^3`$. The lower boundary for self-reproduction $`\varphi _s`$ is given by

$$\varphi _s=\left(\frac{3}{16\pi }\right)^{\frac{1}{4}}m^{\frac{1}{2}}.$$

The requirement $`V/2\lambda <1`$ at $`\varphi _{5\mathrm{D}}`$ implies $`\lambda >2\pi ^2/9`$. Eternal inflation takes place if $`\varphi _s<\varphi _{5\mathrm{D}}`$ which yields the condition, $`\lambda >(1/8)(3/4\pi )^{7/4}m^{3/2}`$. In the standard inflationary scenario observations require that $`m10^{13}\mathrm{GeV}=10^6M_4`$. Thus for realistic values of $`m`$ eternal inflation takes place on the brane in the low energy regime, as long as $`\lambda >2\pi ^2/9`$. However, note that inflation as well as self-reproduction takes place at field values larger than the four-dimensional Planck scale.

In the high energy limit, $`V\lambda `$, the quadratic term in the Friedmann equation dominates,

$`H^2{\displaystyle \frac{8\pi }{3}}{\displaystyle \frac{V^2}{2\lambda }}.`$ (3.11)
Inflation is assumed only to take place in the high energy regime. The end of inflation is determined by the last two terms in the condition (2.6), $`5\dot{\varphi }^2=2V`$, implying, $`\varphi _e=(5/3\pi )^{1/4}\lambda ^{1/4}m^{1/2}`$. The lower boundary for eternal inflation $`\varphi _s`$ is given by

$$\varphi _s=\left(\frac{12}{\pi }\right)^{\frac{1}{10}}\lambda ^{\frac{3}{10}}m^{\frac{4}{5}}.$$

Out of the two inequalities $`\varphi _e<\varphi _{5\mathrm{D}}`$ and $`\varphi _s<\varphi _{5\mathrm{D}}`$ it is found that the first one provides the stronger bound on the brane tension $`\lambda `$, namely, $`\lambda >8\times 10^6m^6`$. An upper bound on $`\lambda `$ is found by requiring that $`V(\varphi _e)/2\lambda >1`$, implying $`\lambda <3\times 10^3m^2`$. As shown in  in the limit of strong brane corrections the COBE normalization of the curvature perturbations put a bound on $`m`$, which can be written in units of $`M_4`$ as, $`m6\times 10^5\lambda ^{1/6}`$. This implies $`\varphi _e10^2\lambda ^{1/6}`$, $`\varphi _s3\times 10^3\lambda ^{1/6}`$, and $`\varphi _{5\mathrm{D}}4\times 10^4\lambda ^{1/6}`$. Thus $`\varphi _e<\varphi _s<\varphi _{5\mathrm{D}}`$ and eternal inflation takes place for values of $`m`$ derived from observations. As already pointed out in , the 5D Planck boundary $`\varphi _{5\mathrm{D}}`$ is below the 4D Planck scale, $`M_4`$. Thus eternal inflation takes place at field values below $`M_4`$.

For a certain range of parameters eternal inflation takes place inside the low energy and inside the high energy regime on the brane. In this case domains reproduce themselves. Since it was assumed that the inflationary period is either in the low or in the high energy regime the dynamics of each of them will be determined by the characteristics of the regime that they are originating from. However, it could also be considered that a domain starts in the low energy regime and then due to the process of stochastic inflation, field values in successive domains reach such high values that strong brane corrections become important. Thus in this case the Friedmann equation on the brane changes from equation (3.10) to equation (3.11). In order for this to happen, one has to require that eternal inflation takes place in the low energy regime. Furthermore, the 5D Planck boundary has to be in the high energy regime. This implies that the brane tension has to satisfy, $`\lambda <2\pi ^2/9`$. In this case, out of a low energy domain domains with the low energy characterics emerge as well as those with the high energy dynamics emerge. This picture is similar to the model proposed in  where the space-time dimension can change locally in chaotic eternal inflation. In this case, on the brane there are regions in which the dynamics are determined by the high energy Friedmann equation (3.11) and there are domains in which the Friedmann equation is the low energy one (3.10).

## 4 Stochastic description

The stochastic nature of the effect of the competition between the classical rolling down and the quantum perturbations is captured by a Fokker-Planck equation . The (classical) field $`\varphi `$ is performing a Brownian motion described by a Langevin equation,

$`{\displaystyle \frac{d}{dt}}\varphi ={\displaystyle \frac{V^{}(\varphi )}{3H(\varphi )}}+{\displaystyle \frac{H^{\frac{3}{2}}(\varphi )}{2\pi }}\xi (t),`$ (4.12)
where $`\xi (t)`$ describes the white noise due to the quantum fluctuations, which causes the Brownian motion of the classical field $`\varphi `$.

The probability distribution $`P_c(\varphi ,t)`$ determines the probability to find a given value of the field $`\varphi `$ at a given time at a given point. This is the probability distribution over a comoving coordinate volume, i.e. over a physical volume at some initial moment of inflation. $`P_c(\varphi ,t)`$ is determined by the equation ,

$`{\displaystyle \frac{P_c}{t}}={\displaystyle \frac{}{\varphi }}\left[{\displaystyle \frac{H^{3(1\beta )}(\varphi )}{8\pi ^2}}{\displaystyle \frac{}{\varphi }}\left(H^{3\beta }(\varphi )P_c\right)+{\displaystyle \frac{V^{}}{3H(\varphi )}}P_c\right].`$ (4.13)
The parameter $`\beta `$ encodes an ambiguity in the derivation of this equation for systems for which the diffusion coefficient depends on $`\varphi `$. $`\beta =1`$ corresponds to the Itô version of stochastic analysis and $`\beta =\frac{1}{2}`$ to the Stratonovich version . An exact stationary solution, for which $`\frac{P_c}{t}=0`$, can be found for the Hubble parameter given by equation (2.4), namely,

$`P_c(\varphi )=\left({\displaystyle \frac{8\pi }{3}}\right)^{\frac{3\beta }{2}}V^{\frac{3\beta }{2}}\left[1+{\displaystyle \frac{V}{2\lambda }}\right]^{\frac{3\beta }{2}}\left[1+{\displaystyle \frac{2\lambda }{V}}\right]^{\frac{3}{8\lambda }}\mathrm{exp}\left[{\displaystyle \frac{3}{8V}}{\displaystyle \frac{1+\frac{V}{\lambda }}{1+\frac{V}{2\lambda }}}\right].`$ (4.14)
In the low energy regime, $`V\lambda `$, this reduces to the well known expression

$`P_cV^{\frac{3\beta }{2}}(\varphi )\mathrm{exp}\left({\displaystyle \frac{3}{8V(\varphi )}}\right).`$ (4.15)
Considering the high energy regime, $`V\lambda `$, the stationary distribution $`P_c(\varphi )`$ approaches,

$`P_c(\varphi )\left({\displaystyle \frac{4\pi }{3}}\right)^{\frac{3\beta }{2}}\left({\displaystyle \frac{V^2}{\lambda }}\right)^{\frac{3\beta }{2}}\mathrm{exp}\left[{\displaystyle \frac{\lambda ^2}{2V^3}}\right].`$ (4.16)
It is interesting to compare the expression for the stationary probability distribution (4.14) with the probability for creation of a braneworld from nothing. This is described by the de Sitter brane instanton . The probability for creation of a universe in the Hartle-Hawking no-boundary proposal  is given by, $`𝒫\mathrm{exp}(S_E)`$, with $`S_E`$ the Euclidean action. In the case of the creation of a braneworld containing just one de Sitter brane in an AdS bulk, the Euclidean action, in the notation used here, is given by ,

$`S_E={\displaystyle \frac{\pi }{H^2}}\left(1+{\displaystyle \frac{V}{\lambda }}\right).`$ (4.17)
Using the expression for the Hubble parameter on the brane (2.4) the nucleation probability of a de Sitter braneworld is given by

$`𝒫\mathrm{exp}\left({\displaystyle \frac{3}{8V}}{\displaystyle \frac{1+\frac{V}{\lambda }}{1+\frac{V}{2\lambda }}}\right).`$ (4.18)
Thus comparing the exponentials in the stationary probability distribution $`P_c`$ (4.14) and in the probability distribution $`𝒫`$ (4.18) it is found that they are exactly the same. Therefore the same coincidence between these two probability distributions appears as is the case in standard four-dimensional inflation .

$`P_c(\varphi ,t)`$ is the probability distribution in a comoving volume, neglecting the expansion of the universe. The probability distribution $`P_p(\varphi ,t)`$ in a proper volume takes into account that during a small time interval $`dt`$ the total number of points associated with the field $`\varphi `$ is additionally increased by a factor $`3H(\varphi )dt`$. Thus this leads to the following equation

$`{\displaystyle \frac{P_p}{t}}={\displaystyle \frac{}{\varphi }}\left[{\displaystyle \frac{H^{3(1\beta )}(\varphi )}{8\pi ^2}}{\displaystyle \frac{}{\varphi }}\left(H^{3\beta }(\varphi )P_p\right)+{\displaystyle \frac{V^{}}{3H(\varphi )}}P_p\right]+3H(\varphi )P_p(\varphi ,t).`$ (4.19)
In order to solve this equation it is convenient to make the ansatz

$`P_p(\varphi ,t)={\displaystyle \underset{s=1}{\overset{\mathrm{}}{}}}e^{\lambda _st}\pi _s(\varphi )e^{\lambda _1t}\pi _1(\varphi )\mathrm{for}t\mathrm{}`$ (4.20)
For large times $`t\mathrm{}`$ only the largest eigenvalue is kept. In the high energy regime brane effects are dominant and the deviations from standard 4D inflation are the largest. Therefore, in the following, the probability distribution $`P_p`$ will be discussed for an inflationary period entirely in the high energy regime. Thus the Hubble parameter is given by (3.11). Together with this and (4.20) equation (4.19) yields to,

$`\pi _1^{\prime \prime }+\left[{\displaystyle \frac{9}{\varphi }}+24{\displaystyle \frac{\lambda ^2}{m^6}}{\displaystyle \frac{1}{\varphi ^7}}\right]\pi _1^{}+\left[{\displaystyle \frac{15}{\varphi ^2}}+72\pi {\displaystyle \frac{\lambda }{m^4}}{\displaystyle \frac{1}{\varphi ^4}}8\pi ^2\left({\displaystyle \frac{\pi }{3}}\right)^{\frac{3}{2}}\lambda _1{\displaystyle \frac{\lambda ^{\frac{3}{2}}}{m^6}}{\displaystyle \frac{1}{\varphi ^6}}24{\displaystyle \frac{\lambda ^2}{m^6}}{\displaystyle \frac{1}{\varphi ^8}}\right]\pi _1=0.`$ (4.21)
where $`\beta =\frac{1}{2}`$. The boundary conditions on $`P_p`$ are equivalent to those in the standard four-dimensional case . There is no diffusion below the end of inflation, which implies
$`\frac{}{\varphi }\left(H^{\frac{3}{2}}(\varphi )P_p\right)_{\varphi _e}=0`$, and inflation stops at the (5D) Planck boundary, thus $`P_p(\varphi _{5\mathrm{D}})=0`$. This imposes the following conditions on $`\pi _1(\varphi )`$,

$`\pi _1^{}(\varphi _e)={\displaystyle \frac{3}{\varphi _e}}\pi _1(\varphi _e)\pi _1(\varphi _{5\mathrm{D}})=0.`$ (4.22)
Numerical solutions have been plotted in figure 1.

In figure 1, the probability distribution shows a maximum in all cases. For larger values of $`m`$ at constant brane tension $`\lambda `$ it is shifted towards smaller field values $`\varphi `$. For larger values of $`\lambda `$ at constant $`m`$ it is shifted towards higher field values $`\varphi `$, concentrated very close to the 5D Planck boundary. The eigenvalue $`\lambda _1`$ can be related to the fractal dimension of the universe, $`d_{fr}`$, defined as $`d_{fr}=\lambda _1/H_{max}`$ , where $`H_{max}`$ is the maximal Hubble parameter at the five-dimensional Planck boundary. The fractal dimension is motivated by the observation that at the Planck boundary the total volume of inflationary domains does not grow as $`e^3`$ during a time interval $`H_{max}^1`$ but only as $`\mathrm{exp}(\lambda _1/H_{max})`$. Some domains will reach energies beyond the Planck scale and thus drop out of the total volume. On the brane in the high energy regime the maximal Hubble parameter at the 5D Planck boundary is given by $`H_{max}=\left(\frac{4\pi }{3}\right)^{\frac{7}{6}}\lambda ^{\frac{1}{6}}`$. Thus the numerical examples in figure 1 have fractal dimensions much below 3.

For scalar field values $`\varphi >\varphi _s`$ self-reproduction takes place. This phenomenon is related to the quantum jumps that cause the field values to increase. However, as pointed out in  these quantum jumps could also coherently add up to lead to a larger than usual jump down the potential. This might lead to nonperturbative amplification of inhomogeneities. Domains in which quantum jumps lead to an increase of the field value are pushed up to the five dimensional Planck boundary. At this point the Hubble parameter reaches its maximum, $`H_{max}`$. Thus these domains give the greatest contribution to the volume of the universe. The domains will stay as long as possible at the Planck boundary and then ”rush down” the potential with an amplitude larger than $`H/2\pi `$ . Following  the extra time, $`\stackrel{~}{\mathrm{\Delta }}t`$ spent at the Planck boundary can be estimated by, $`\stackrel{~}{\mathrm{\Delta }}t(\varphi )=\stackrel{~}{\delta }\varphi /\dot{\varphi }`$, where $`\stackrel{~}{\delta }\varphi `$ is the amplified amplitude of the jump down the potential, $`\stackrel{~}{\delta }\varphi =n(\varphi )H(\varphi )/(2\pi ),`$ where $`n(\varphi )`$ is an amplification factor. In the regime where brane effects are dominant, $`V\lambda `$, this leads to

$`\stackrel{~}{\mathrm{\Delta }}t(\varphi )=2n(\varphi ){\displaystyle \frac{V^2}{\lambda V^{}}}.`$ (4.23)
The volume is increased by a factor $`\mathrm{exp}(d_{fr}H_{max}\stackrel{~}{\mathrm{\Delta }}t)`$. Hence the volume-weighted probability (4.20) is given by

$`P\mathrm{exp}\left[d_{fr}H_{max}\stackrel{~}{\mathrm{\Delta }}t(\varphi ){\displaystyle \frac{1}{2}}n^2(\varphi )\right],`$ (4.24)
where it is assumed that an amplification of the standard jump is suppressed by a factor $`\mathrm{exp}[\frac{1}{2}n^2(\varphi )]`$. Maximizing this with respect to $`n(\varphi )`$ gives

$`n(\varphi )=2d_{fr}H_{max}{\displaystyle \frac{V^2}{\lambda V^{}}}.`$ (4.25)
Expressing this in terms of the ratio of the amplitudes of scalar to tensor perturbations, $`A_S/A_T`$ , yields to

$`n(\varphi )=\left({\displaystyle \frac{3}{2\pi }}\right)^{\frac{1}{2}}d_{fr}H_{max}\left({\displaystyle \frac{V}{\lambda }}\right)^{\frac{1}{2}}{\displaystyle \frac{A_S}{A_T}}.`$ (4.26)
In the standard four-dimensional case dependence on the inflaton field $`\varphi `$ in the amplifying factor $`n(\varphi )`$ can be entirely expressed in terms of the ratio of the amplitudes of the scalar to tensor perturbations. As it turns out, in the high energy regime of chaotic inflation on the brane this is no longer the case. There is an additional amplifying factor $`V/\lambda `$. Since $`A_S/A_T`$ is an observable quantity this means that the amplitude of the jumps down the potential are amplified with respect to the case of standard four-dimensional inflation. Domains which jump down with these amplified amplitudes end up as regions with smaller energy density compared to the background. In a braneworld these wells or infloids  are deeper than in standard four-dimensional inflation.

## 5 Conclusions

The stochastic approach to standard 4D inflation and its variations opened the way to a rich global structure of an inflating universe. Here the stochastic approach to inflation has been applied to a braneworld model, namely, to chaotic inflation on the brane. It has been shown that eternal inflation takes place for a certain range of parameters, and in particular, for those satisfying observational bounds.

The competition between the evolution towards smaller field values due to classical dynamics and the evolution towards either even smaller or higher field values can be described as a Brownian motion. There exists a well defined procedure to obtain a Fokker-Planck equation determining the probability distribution to find a certain value of the scalar field at a given point in space-time. Furthermore, there are two types of probability distributions. Firstly, the probability distribution $`P_c`$ in a given comoving volume. Secondly, the probability distribution $`P_p`$ in a given physical volume, which takes into account the expansion of the universe. In standard 4D chaotic inflation, apart from some pre-factors, the dominant behaviour is determined by an exponential function, which is exactly the square of the Hartle-Hawking no-boundary wavefunction of the universe. In the braneworld scenario discussed here, a similar result was found. Comparing the expression for $`P_c`$ found in the stochastic approach to chaotic inflation on the brane with the de Sitter brane instanton for a one brane system as calculated in , apart from some prefactors, the same exponential function was found in the two cases.

The probability distribution in a given physical volume, $`P_p`$, was calculated numerically in the high energy regime where brane effects dominate. The results are similar to the ones in standard 4D inflation with the distribution concentrated near the 5D Plack boundary.

Finally, the process of a scalar field close to the 5D Planck boundary rolling down with amplitudes larger than the usual $`H/2\pi `$, due to quantum fluctuations, was briefly discussed. It was found that the amplification factor is enhanced by a factor $`V/\lambda `$ in the high energy regime on the brane. Thus the infloids or wells in the energy distribution are deeper than in standard four dimensional inflation.

## 6 Acknowledgments

It is a pleasure to thank J. Garriga and M.A. Vázquez-Mozo for enlightening discussions. I would like to thank the University of Geneva for hospitality where part of this work was done. This work has been supported in part by Spanish Science Ministry Grant FPA 2002-02037.


text:
# Packing 4-cycles in Eulerian and bipartite Eulerian tournaments with an application to distances in interchange graphs

## 1 Introduction

All graphs and digraphs considered here are finite, and contain no parallel edges or anti-parallel arcs. For standard graph-theoretic terminology the reader is referred to . An Eulerian orientation of an undirected graph $`G`$ is an orientation of the edges of $`G`$ such that each vertex has the same indegree and outdegree in the resulting oriented graph. It is well known that a graph $`G`$ has an Eulerian orientation if and only if every vertex is of even degree. A tournament is an orientation of a complete graph and a bipartite tournament is an orientation of a complete bipartite graph. Properties of Eulerian tournaments (also called regular tournaments) and bipartite Eulerian tournaments have been extensively studied in the literature (see, e.g., ).

A conjecture of Brualdi and Shen  asserts that every bipartite Eulerian tournament has a decomposition into $`C_4`$, the directed cycle on four vertices. In other words, any Eulerian orientation of $`K_{m,n}`$ contains $`mn/4`$ arc-disjoint $`C_4`$’s (clearly $`m`$ and $`n`$ must be even in order to have an Eulerian orientation). This conjecture is still far from being solved, and, in fact, there is no evidence that it should be true. Even an asymptotic version of this conjecture is not known. A recent result from  states that any Eulerian orientation of a bipartite graph with vertex class sizes $`m`$ and $`n`$ and more than $`2mn/3`$ arcs has a $`C_4`$. This immediately implies that any Eulerian orientation of $`K_{m,n}`$ contains at least $`mn/12`$ arc-disjoint $`C_4`$’s. Although very far from the Brualdi-Shen conjecture, this is currently the best known published lower bound for this problem. In this paper we considerably improve the lower bound.

###### Theorem 1.1

Every Eulerian orientation of $`K_{m,n}`$ contains at least $`\frac{1}{4+\sqrt{8}}mn(1o(1))`$ arc-disjoint copies of $`C_4`$.

The $`o(1)`$ term denotes a function tending to zero as $`\mathrm{min}\{m,n\}`$ tends to infinity. Notice that, trivially, any $`C_4`$-packing of an orientation of $`K_{m,n}`$ contains at most $`mn/4`$ elements. Theorem 1.3 shows that more than $`58`$ per cent of the arcs can be packed with $`C_4`$’s.

The motivation behind the Brualdi-Shen conjecture stems from the theory of interchange graphs. These graphs are defined as follows: Let $`R=(r_1,\mathrm{},r_n)`$ and $`S=(s_1,\mathrm{},s_m)`$ be non-negative integral vectors with $`r_i=s_j`$. Let $`𝒜(R,S)`$ denote the set of all $`m\times n`$ $`\{0,1\}`$-matrices with row sum vector $`R`$ and column sum vector $`S`$, and assume that $`𝒜(R,S)\mathrm{}`$. This set has been studied extensively (see  for a survey). An interchange is a transformation which replaces a $`2\times 2`$ identity submatrix of a matrix $`A`$ with the $`2\times 2`$ permutation matrix $`P_{i,j}=|ij|`$. Clearly an interchange (and hence any sequence of interchanges) does not alter the row and column sum vectors of a matrix and transforms a matrix in $`𝒜(R,S)`$ into another matrix in $`𝒜(R,S)`$. Ryser  proved that for any two matrices in $`𝒜(R,S)`$ there is a sequence of interchanges which transforms one to the other. The interchange graph $`G(R,S)`$ of $`𝒜(R,S)`$, defined by Brualdi in 1980, is the graph with all matrices in $`𝒜(R,S)`$ as its vertices, where two matrices are adjacent provided that one can be obtained from the other by a single interchange. Brualdi conjectured that the diameter of $`G(R,S)`$, denoted $`d(R,S)`$, cannot exceed $`mn/4`$. This conjecture is still far from being resolved. The best known bounds for $`d(R,S)`$ use the following reduction of Walkup. Given two matrices $`A,B𝒜(R,S)`$ consider the $`m\times n`$ matrix $`AB`$. This matrix contains the elements $`\{1,0,1\}`$ and the sum of each row and column is zero. Thus, there is a one-to-one correspondence between such matrices and Eulerian orientations of a bipartite graph with vertex class sizes $`m`$ and $`n`$. Walkup  proved that the distance between $`A`$ and $`B`$ in $`G(R,S)`$, denoted $`i(A,B)`$ satisfies

$$i(A,B)=\frac{d(A,B)}{2}q(A,B)$$
(1)
where $`d(A,B)`$ is the number of nonzero entries in $`AB`$ and $`q(A,B)`$ is the maximum number of arc-disjoint cycles in a cycle decomposition of the bipartite Eulerian digraph corresponding to $`AB`$. The currently best known upper bound for $`d(R,S)`$ obtained using Walkup’s reduction is given in  yielding $`d(R,S)\frac{5}{12}mn`$. We call two matrices $`A,B𝒜(R,S)`$ antipodal if $`B`$ is the complement of $`A`$, or, in other words, if $`A+B`$ is the all-one matrix. Notice that a necessary conditions for $`A`$ and $`B`$ to be antipodal is that all coordinates of $`R`$ are $`m/2`$ and all coordinates of $`S`$ are $`n/2`$. Trivially, the distance between two antipodal vertices in $`G(R,S)`$ is at least $`mn/4`$, and hence such vertices show that Brualdi’s conjecture, if true, is best possible. In particular antipodal vertices are conjectured to be farthest apart in $`G(R,S)`$. If $`A`$ and $`B`$ are antipodal matrices then $`AB`$ corresponds to an Eulerian orientation of $`K_{m,n}`$. Observe that using (1) and Theorem 1.1 we obtain the following.

###### Corollary 1.2

Let $`A`$ and $`B`$ be two antipodal vertices of $`G(R,S)`$. Then,

$$0.25mni(A,B)\frac{1+\sqrt{2}}{4+\sqrt{8}}mn(1+o(1))0.354mn(1+o(1)).$$

Theorem 1.1, combined with a probabilistic argument, enables us to prove an analogous theorem for regular tournaments.

###### Theorem 1.3

Every regular tournament with $`n`$ vertices contains at least $`\frac{1}{8+\sqrt{32}}n^2(1o(1))`$ arc-disjoint copies of $`C_4`$.

Notice that, trivially, any $`C_4`$-packing of an $`n`$-vertex tournament contains less than $`n^2/8`$ elements. Theorem 1.3 shows that more than $`58`$ per cent of the arcs can be packed with $`C_4`$’s.

In the following section we prove Theorem 1.1. The final section contains the proof of Theorem 1.3.

## 2 Proof of Theorem 1.1

Kotzig  computed the minimum possible number of $`C_4`$’s in regular tournaments. We require an analogous lower bound for bipartite Eulerian tournaments. The following lemma provides this bound.

###### Lemma 2.1

Every bipartite Eulerian tournament with vertex class sizes $`m`$ and $`n`$ contains at least $`m^2n^2/32`$ copies of $`C_4`$.

Proof: The result is trivial for $`m=n=2`$. We therefore assume $`m+n6`$. There are four possible ways to orient an undirected $`4`$-cycle. One of them is $`C_4`$ and we denote the other three by $`H_1`$, $`H_2`$ and $`H_3`$ where $`H_i`$ is the unique orientation having a maximal path of length $`i`$. Note that $`H_1`$ has two sources and two sinks while $`H_2`$ and $`H_3`$ each have one source and one sink. Let $`G=(AB,V)`$ be a bipartite Eulerian tournament with vertex classes $`A`$ and $`B`$ where $`|A|=m`$ and $`|B|=n`$. Let $`h_i`$ denote the number of distinct copies of $`H_i`$ in $`G`$ and let $`x`$ denote the number of copies of $`C_4`$ in $`G`$. Clearly,

$$x+h_1+h_2+h_3=\left(\genfrac{}{}{0pt}{}{n}{2}\right)\left(\genfrac{}{}{0pt}{}{m}{2}\right).$$

Let $`t`$ denote the total number of sources in all these $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)\left(\genfrac{}{}{0pt}{}{m}{2}\right)`$ graphs. As each vertex of $`A`$ is a source in precisely $`(m1)\left(\genfrac{}{}{0pt}{}{n/2}{2}\right)`$ such graphs, and as each vertex of $`B`$ is a source in precisely $`(n1)\left(\genfrac{}{}{0pt}{}{m/2}{2}\right)`$ such graphs, we have

$$t=n(n1)\left(\genfrac{}{}{0pt}{}{\frac{m}{2}}{2}\right)+m(m1)\left(\genfrac{}{}{0pt}{}{\frac{n}{2}}{2}\right).$$

Every copy of $`H_1`$ contains two sources, and every copy of $`H_2`$ and of $`H_3`$ contains one source. Thus, $`2h_1+h_2+h_3=t`$. It follows that

$$xh_1=\frac{mn}{4}(\frac{m}{2}+\frac{n}{2}1).$$

For each pair of distinct vertices $`u,v`$ belonging to the same vertex class, let $`k_{u,v}`$ denote the number of common out neighbors. Notice that $`k_{u,v}`$ is also the number of common incoming neighbors. Furthermore, if $`u,vA`$ then $`n/2k_{u,v}`$ is the number of out neighbors of $`u`$ which are incoming neighbors of $`v`$ and also the number of incoming neighbors of $`u`$ which are out neighbors of $`v`$. The number of $`C_4`$ copies containing both $`u`$ and $`v`$ is $`(n/2k_{u,v})^2`$. The number of $`H_1`$ copies containing both $`u`$ and $`v`$ is $`2\left(\genfrac{}{}{0pt}{}{k_{u,v}}{2}\right)`$. An analogous argument holds for $`u,vB`$. As each $`H_1`$ and each $`C_4`$ account for two pairs, we have

$$2x+2h_1=\left(\underset{u,vA}{}(\frac{n}{2}k_{u,v})^2+2\left(\genfrac{}{}{0pt}{}{k_{u,v}}{2}\right)\right)+\left(\underset{u,vB}{}(\frac{m}{2}k_{u,v})^2+2\left(\genfrac{}{}{0pt}{}{k_{u,v}}{2}\right)\right).$$

Minimizing the right hand side of the last equality we obtain

$$2x+2h_1\left(\genfrac{}{}{0pt}{}{m}{2}\right)\frac{n^22n1}{8}+\left(\genfrac{}{}{0pt}{}{n}{2}\right)\frac{m^22m1}{8}.$$

Therefore,

$$4x\frac{mn}{2}(\frac{m}{2}+\frac{n}{2}1)\left(\genfrac{}{}{0pt}{}{m}{2}\right)\frac{n^22n1}{8}+\left(\genfrac{}{}{0pt}{}{n}{2}\right)\frac{m^22m1}{8}.$$

Hence,

$$x\left(\genfrac{}{}{0pt}{}{m}{2}\right)\frac{n^22n1}{32}+\left(\genfrac{}{}{0pt}{}{n}{2}\right)\frac{m^22m1}{32}+\frac{mn}{8}(\frac{m}{2}+\frac{n}{2}1)$$

$$=\frac{m^2n^2}{32}+\frac{1}{64}(mn^2+nm^2)\frac{1}{16}mn\frac{1}{64}(m^2+n^2)+\frac{1}{64}(m+n)\frac{m^2n^2}{32}.$$

We note that Lemma 2.1 is asymptotically tight. This can easily be shown by considering random Eulerian orientations of $`K_{m,n}`$. We omit the details.

Our next lemma shows that if some arc of a bipartite Eulerian tournament is on too many copies of $`C_4`$ or on too few copies of $`C_4`$ then there must be many copies of $`C_4`$ altogether. Before we state the lemma we need a few definitions. Let $`G`$ be a bipartite Eulerian tournament with vertex class sizes $`m`$ and $`n`$. Let $`e=(x,y)`$ be an arc of $`G`$. Let $`N^{}(x)`$ denote the in-neighborhood of $`x`$ and let $`N^+(y)`$ denote the out-neighborhood of $`y`$. Let $`d(e)`$ be the number of arcs from $`N^+(y)`$ to $`N^{}(x)`$. Notice that $`e`$ is on precisely $`d(e)`$ copies of $`C_4`$ and notice also that there are $`mn/4d(e)`$ arcs from $`N^{}(x)`$ to $`N^+(y)`$. Let $`\alpha (e)=\mathrm{min}\{d(e)/mn,1/4d(e)/mn\}`$. Let $`\alpha (G)=\mathrm{min}_{eG}\alpha (e)`$.

###### Lemma 2.2

Let $`G`$ be a bipartite Eulerian tournament with vertex class sizes $`m`$ and $`n`$. $`G`$ has at least $`m^2n^2(1/16\alpha (G)+4\alpha (G)^2)`$ copies of $`C_4`$.

Proof: Let $`A`$ and $`B`$ denote the vertex classes of $`G`$ with $`|A|=m`$ and $`|B|=n`$. Let $`e=(x,y)`$ be an arc for which $`\alpha (e)=\alpha (G)`$. For simplicity let $`\alpha =\alpha (e)=\alpha (G)`$. Thus, either $`\alpha =d(e)/mn`$ or $`\alpha =1/4d(e)/mn`$. Without loss of generality assume that $`\alpha =1/4d(e)/mn`$ (the proof of the other case is analogous). Also without loss of generality assume that $`xA`$ and $`yB`$ (the proof of the other case is analogous). By our assumptions, $`|N^{}(x)|=|N^+(x)|=n/2`$ and $`|N^{}(y)|=|N^+(y)|=m/2`$. Also, $`e`$ appears on precisely $`d(e)=mn(1/4\alpha )`$ copies of $`C_4`$.

Let $`T`$ be the set of arcs from $`N^{}(x)`$ to $`N^+(y)`$. Notice that $`|T|=\alpha mn`$. Let $`S`$ be the set of arcs from $`N^+(x)`$ to $`N^{}(y)`$, let $`W`$ be the set of arcs from $`N^{}(y)`$ to $`N^{}(x)`$ and let $`Z`$ be the set of arcs from $`N^+(y)`$ to $`N^+(x)`$. Since $`G`$ is Eulerian we must have $`\alpha mn=|T|=|S|=|W|=|Z|`$.

Consider an induced subgraph of $`G`$ with four vertices, precisely one vertex from each of $`N^+(x),N^{}(x),N^+(y),N^{}(y)`$, and with no arc from $`STWZ`$. Such a subgraph must be a $`C_4`$. Denote the number of such subgraphs by $`x`$. Denote the number of $`C_4`$’s of $`G`$ having at least one arc in $`STWZ`$ by $`y`$. Denote the number of $`C_4`$’s of $`G`$ with all their arcs in $`STWZ`$ by $`z`$. Clearly, $`zy`$ and there are at least $`x+y`$ copies of $`C_4`$ in $`G`$.

Let $`F`$ be the set of induced subgraphs of $`G`$ with four vertices, precisely one vertex from each of $`N^+(x),N^{}(x),N^+(y),N^{}(y)`$. Notice that $`|F|=m^2n^2/16`$. Let $`F^{}F`$ be the set of elements of $`F`$ containing at least one arc from $`STWZ`$. Notice that all elements in $`FF^{}`$ are $`C_4`$’s. The sum of the arcs of $`STWZ`$ over all elements of $`F^{}`$ is precisely $`(4\alpha mn)(mn/4)=\alpha m^2n^2`$. However, some elements of $`F^{}`$ contain more than one arc from $`STWZ`$, and are therefore counted more than once. In fact, each $`eT`$ and each $`e^{}S`$ appear together in precisely one element of $`F^{}`$. Similarly, each $`eW`$ and each $`e^{}Z`$ appear together in precisely one element of $`F^{}`$. Thus, there are $`\alpha ^2m^2n^2`$ elements of $`F^{}`$ containing a pair of arcs from $`ST`$ and there are $`\alpha ^2m^2n^2`$ elements of $`F^{}`$ containing a pair of arcs from $`WZ`$. Such elements are counted at least twice. In fact, precisely $`z`$ of them are counted four times. It follows that $`|F^{}|\alpha m^2n^22\alpha ^2m^2n^2z`$. Therefore,

$$x=|F||F^{}|\frac{1}{16}m^2n^2\alpha m^2n^2+2\alpha ^2m^2n^2+z.$$

By the definition of $`\alpha =\alpha (G)`$, each arc of $`G`$ appears on at least $`\alpha mn`$ copies of $`C_4`$. In particular the sum of the arcs from $`STWZ`$ appearing on copies of $`C_4`$ is at least $`(4\alpha mn)(\alpha mn)=4\alpha ^2m^2n^2`$. Precisely $`z`$ of the $`C_4`$’s containing arcs from $`STWZ`$ are counted $`4`$ times in this way. Notice that if some $`C_4`$ has three arcs from $`STWZ`$ then it must have four arcs in $`STWZ`$. Thus, $`yz+(4\alpha ^2m^2n^24z)/2=2\alpha ^2m^2n^2z`$. Consequently,

$$x+ym^2n^2(\frac{1}{16}\alpha +4\alpha ^2).$$

Recall that a $`k`$-uniform hypergraph is a family of $`k`$-subsets of some set $`V`$ of vertices. The $`k`$-subsets are the edges of the hypergraph. If $`x,y`$ are two vertices of a hypergraph then let $`d(x)`$ denote the number of edges containing $`x`$ and let $`d(x,y)`$ denote the number of edges containing both $`x`$ and $`y`$ (their co-degree). A proper $`r`$-coloring of the edges of a hypergraph is a partition of the set of edges to $`r`$ subsets such that any two edges in the same subset are disjoint. Kahn  has proved a very powerful result giving an upper bound for the minimum number of colors in a proper edge-coloring of a uniform hypergraph (his result is, in fact, more general).

###### Lemma 2.3 (Kahn )

For every $`k2`$ and every $`ϵ>0`$ there exists a $`\delta >0`$ such that the following statement is true:
If $`H`$ is a $`k`$-uniform hypergraph on a set $`V`$ of vertices, and if $`d(v)D`$ for all $`vV`$ and $`d(u,v)<\delta D`$ for all distinct $`u,vV`$, then there is a proper coloring of the edges of $`H`$ with at most $`(1+ϵ)D`$ colors.

Completing the proof of Theorem 1.1. Let $`ϵ>0`$. We need to prove that if $`m`$ is sufficiently large as a function of $`ϵ`$ and if $`nm`$ and $`G`$ is a bipartite Eulerian tournament with vertex class sizes $`m`$ and $`n`$, then $`G`$ has at least $`\frac{1}{4+\sqrt{8}}mn(1ϵ)`$ arc-disjoint copies of $`C_4`$.

We construct a $`4`$-uniform hypergraph $`H`$ as follows. The vertices of $`H`$ are the $`mn`$ arcs of $`G`$ and the edges of $`H`$ are the copies of $`C_4`$ in $`G`$. Let $`e=(x,y)`$ be an arc of $`G`$ such that $`d(e)`$ is maximal. Clearly, $`d(e)mn/4`$. By Lemma 2.1 we also have $`d(e)4(m^2n^2/32)/(mn)mn/8`$. In particular $`\alpha (e)=1/4d(e)/mn`$ and $`0\alpha (G)\alpha (e)1/8`$. Notice that any two arcs of $`G`$ appear together on at most $`\mathrm{max}\{m/2,n/2\}=n/2`$ copies of $`C_4`$. Thus, with $`D=d(e)`$ and with $`\delta =\delta (4,ϵ)`$ chosen as in Lemma 2.3 we have that for $`m`$ sufficiently large, the hypergraph $`H`$ satisfies the conditions of Lemma 2.3. In particular, there is a coloring of the $`C_4`$ copies of $`G`$ with at most $`(1+ϵ)d(e)`$ colors such that each color class corresponds to a set of arc-disjoint copies of $`C_4`$. By Lemma 2.1 and Lemma 2.2, the total number of edges of $`H`$ is at least

$$\mathrm{max}\{\frac{1}{32}m^2n^2,m^2n^2(\frac{1}{16}\alpha (G)+4\alpha (G)^2)\}.$$

Thus, there must be a set of arc-disjoint copies of $`C_4`$ with at least

$$\mathrm{max}\{\frac{m^2n^2/32}{(1+ϵ)d(e)},\frac{m^2n^2(1/16\alpha (G)+4\alpha (G)^2)}{(1+ϵ)d(e)}\}$$

elements. Since $`\alpha (G)\alpha 1/8`$ it suffices to prove that

$$\frac{mn}{1+ϵ}\mathrm{max}\{\frac{1/32}{1/4\alpha (e)},\frac{1/16\alpha (e)+4\alpha (e)^2}{1/4\alpha (e)}\}\frac{1}{4+\sqrt{8}}mn(1ϵ).$$

Indeed, this follows from the fact that for $`0z1/8`$ the value of $`\mathrm{max}\{(1/32)/(1/4z),(1/16z+4z^2)/(1/4z)\}`$ is minimized when $`z=1/8\sqrt{1/128}`$.

## 3 Proof of Theorem 1.3

The proofs of Lemma 2.1 and Lemma 2.2, and hence of Theorem 1.1, can easily be modified to hold for almost Eulerian bipartite tournaments. More precisely, we say that a bipartite orientation of $`K_{m,n}`$ is $`\delta `$-Eulerian if the outdegree and indegree of each vertex from the $`m`$-vertex class is at least $`(1\delta )n/2`$ and if the outdegree and indegree of each vertex from the $`n`$-vertex class is at least $`(1\delta )m/2`$. Given $`ϵ>0`$, it is straightforward to check that Lemma 2.1 holds for $`\delta `$-Eulerian bipartite tournaments if one replaces the $`m^2n^2/32`$ bound with $`m^2n^2(1ϵ)`$ provided that $`\delta =\delta (ϵ)`$ is sufficiently small and $`\mathrm{min}\{m,n\}`$ is sufficiently large as a function of $`ϵ`$. It is straightforward to check that a similar relaxation also holds for Lemma 2.2. Thus, we obtain the following relaxation for Theorem 1.1.

###### Lemma 3.1

Let $`ϵ>0`$. There exists $`\delta =\delta (ϵ)>0`$ and $`M=M(ϵ)`$ such that if $`Mmn`$, any $`\delta `$-Eulerian orientation of $`K_{m,n}`$ contains at least $`\frac{1}{4+\sqrt{8}}mn(1ϵ)`$ arc-disjoint copies of $`C_4`$.

Completing the proof of Theorem 1.1. Let $`ϵ>0`$. We need to show that there exists $`N=N(ϵ)`$ such that for all $`n>N`$, any regular tournament with $`n`$ vertices has at least $`\frac{1}{8+\sqrt{32}}n^2(1ϵ)`$ arc-disjoint directed $`4`$-cycles.

We choose $`\delta =\delta (ϵ/2)`$ to be as in Lemma 3.1. Choose $`N\mathrm{max}\{2M^2,64/ϵ^2\}`$, where $`M=M(ϵ/2)`$ is the constant from Lemma 3.1, to be the smallest integer satisfying $`4N^2\mathrm{exp}(\delta ^2N/128)<1`$. Let $`n>N`$. The asymptotic nature of our proof allows us to assume, for simplicity, that $`n`$ is a square of an integer. Therefore, let $`m=\sqrt{n}`$. Let $`T`$ be a regular tournament with $`n`$ vertices. Each $`vT`$ chooses uniformly and independently an integer from $`\{1,\mathrm{},m\}`$. Let $`V_i`$ denote the set of vertices that chose $`i`$, and for $`1i<jm`$ let $`G_{i,j}`$ be the complete bipartite tournament with vertex classes $`V_i`$ and $`V_j`$.

We will prove that with positive probability, all the $`\left(\genfrac{}{}{0pt}{}{m}{2}\right)`$ bipartite tournaments $`G_{i,j}`$ are $`\delta `$-Eulerian, and that all $`V_i`$ have size at least $`M`$ and at most $`2m`$. This suffices to complete the theorem since by Lemma 3.1 we have that the total number of arc-disjoint $`C_4`$ in $`T`$ is at least

$$\underset{1i<jm}{}\frac{1}{4+\sqrt{8}}|V_i||V_j|(1\frac{ϵ}{2})$$

$$=\frac{1}{8+\sqrt{32}}(1\frac{ϵ}{2})(n^2\underset{i=1}{\overset{m}{}}|V_i|^2)\frac{1}{8+\sqrt{32}}(1\frac{ϵ}{2})(n^24m^3)$$

$$\frac{1}{8+\sqrt{32}}(1\frac{ϵ}{2})n^2(1\frac{ϵ}{2})\frac{1}{8+\sqrt{32}}n^2(1ϵ).$$

Fix a vertex $`v`$. Let $`d_i^+(v)`$ (resp. $`d_i^{}(v)`$) denote the number of out (resp. incoming) neighbors of $`v`$ in $`V_i`$. The expectation of $`d_i^+(v)`$ (resp. $`d_i^{}(v)`$) is precisely $`m^1(n1)/2=(n1)/(2m)`$. A large deviation inequality of Chernoff (cf.  Appendix A) bounds the probability that a random variable which is the sum of independent indicator random variables deviates from its expectation by more than a specified amount. More precisely, for the variable $`d_i^+(v)`$ and the amount $`\frac{\delta }{4}\frac{n1}{2m}`$ we get

$$\mathrm{Pr}\left[\left|d_i^+(v)\frac{n1}{2m}\right|>\frac{\delta }{4}\frac{n1}{2m}\right]<2\mathrm{exp}\left(\frac{\delta ^2(n1)^2/64m^2}{2(n1)/2m}+\frac{\delta ^3(n1)^3/512m^3}{2(n1)^2/4m^2}\right)=$$

$$2\mathrm{exp}\left(\frac{\delta ^2(n1)}{64m}+\frac{\delta ^3(n1)}{128m}\right)<\frac{1}{2mn}.$$

Precisely the same bound holds for $`d_i^{}(v)`$. Since there are $`n`$ choices for vertices and $`m`$ choices for $`i`$, we get that with probability greater than $`12nm\frac{1}{2mn}=0`$, for all vertices $`v`$ and all indices $`i`$,

$$\left|d_i^+(v)\frac{n1}{2m}\right|\frac{\delta }{4}\frac{n1}{2m}\left|d_i^{}(v)\frac{n1}{2m}\right|\frac{\delta }{4}\frac{n1}{2m}.$$

We therefore fix a partition $`V_1,\mathrm{},V_m`$ for which all of these conditions are met. In particular, this means that for all $`i=1,\mathrm{},m`$,

$$2m>(1+\frac{\delta }{4})\frac{n1}{m}|V_i|(1\frac{\delta }{4})\frac{n1}{m}>M,$$

and that for all vertices $`v`$ and all $`i=1,\mathrm{},m`$

$$\mathrm{min}\{d_i^{}(v),d_i^+(v)\}(1\frac{\delta }{4})\frac{n1}{2m}(1\delta )(1+\frac{\delta }{4})\frac{n1}{2m}\frac{|V_i|}{2}(1\delta ).$$

Thus, all the $`\left(\genfrac{}{}{0pt}{}{m}{2}\right)`$ bipartite tournaments $`G_{i,j}`$ are $`\delta `$-Eulerian, and all $`V_i`$ have size at least $`M`$ and at most $`2m`$.


text:
# Combinatorics of binomial decompositions of the simplest Hodge integrals

## 1. Introduction

In this paper we study the simplest Hodge integrals on the moduli space of curves. Let $`\overline{}_{g,n}`$ be the moduli space of curves of genus $`g`$ with $`n`$ marked points. By $`\psi _i`$ denote the first Chern class of the line bundle over $`\overline{}_{g,n}`$, whose fiber at a moduli point $`(C_g,x_1,\mathrm{},x_n)\overline{}_{g,n}`$ is equal to $`T_{x_i}^{}C`$. The Hodge bundle is the rank $`g`$ vector bundle over $`\overline{}_{g,n}`$, whose fiber at a moduli point $`(C_g,x_1,\mathrm{},x_n)\overline{}_{g,n}`$ is equal to $`H^0(C,\omega _C)`$. By $`\lambda _1,\mathrm{},\lambda _g`$ denote the Chern classes of the Hodge bundle.

In this paper we consider the integrals

(1.1)
$$_{\overline{}_{g,1}}\psi _1^{3g2i}\lambda _i.$$

We give an algorithm to calculate these integrals. In fact, these integrals have already been calculated by Faber and Pandharipande, see . There is a remarkable formula for the generating function of Hodge integrals:

(1.2)
$$1+\underset{g1}{}\underset{i=0}{\overset{g}{}}t^{2g}k^i_{\overline{}_{g,1}}\psi _1^{2g2+i}\lambda _{gi}=\left(\frac{t/2}{\mathrm{sin}(t/2)}\right)^{k+1}.$$

So, let us explain our motivations. First, for the integrals $`_{\overline{}_{g,1}}\psi _1^{2g2}\lambda _g`$ our computing algorithm has a rather simple interpretation as a certain sum over trees. So, since these integrals are already calculated, we solve an interesting combinatorial problem. In particular, this gives a representation of Bernoulli numbers as some sums over trees.

Second, the combinatorial structure of Hodge integrals still seems to produce some questions, see . Our approach could clarify something in this direction. Moreover, the soul of our computing algorithm is a ‘cut-and-join’ type equation for the Hodge integrals over two-pointed ramification cycles. Since Hurwitz numbers satisfy the similiar equations, this could give some new relations between Hurwitz numbers and Hodge integrals, see .

Third, our computing algorithm is a modification of the computing algorithm for the simplest Witten intersections, see . It works very good to calculate any concrete intersection number, but it is very hard to prove any general statement using this approach. In the case considered in this paper we reduce the computing algorithm to rather friendly combinatorics. We hope this could help in our approach to the Witten conjecture.

### Organization of the paper

In Section 2 we give our algorithm for computing the integrals $`_{\overline{}_{g,1}}\psi _1^{2g2}\lambda _g`$. In Section 3 explain the combinatorial interpretation of this algorithm and combinatorial corollaries of this interpretation. In Section 4 we prove all theorems of Section 2.

In Appendix A we give some calculations checking independently our algorithm. In Appendix B we describe separately genus zero case of our combinatorial results. In Appendix C we generalize our algorithm to compute all Hodge integrals $`_{\overline{}_{g,1}}\psi _1^{3g2i}\lambda _i`$.

## 2. Calculation of Hodge integrals

In this section we explain an algorithm to calculate the Hodge integrals $`_{\overline{}_{g,1}}\psi _1^{2g2}\lambda _g`$. The proofs of all theorems of this section are given in Section 4.

### 2.1. Some notations

Consider the moduli space of curves $`\overline{}_{g,n+1}`$. Let us fix some positive integers $`a_1,\mathrm{},a_n`$. By $`V_g^{}(a_1,\mathrm{},a_n)`$ denote the subvariety of the open moduli space $`_{g,n+1}`$ consisting of curves $`(C,x_1,\mathrm{},x_{n+1})`$ such that $`(_{i=1}^na_i)x_1+a_1x_2+\mathrm{}+a_nx_{n+1}`$ is a divisor of a meromorphic function.

Let $`V_g(a_1,\mathrm{},a_n)`$ be the closure of $`V_g^{}(a_1,\mathrm{},a_n)`$ in $`\overline{}_{g,n}`$. By $`W_g(_{i=1}^n\eta _{a_i})`$ denote the integral of $`\psi _1^{g+n2}\lambda _g`$ over the subspace $`V_g(a_1,\mathrm{},a_n)`$:

(2.1)
$$W_g(\underset{i=1}{\overset{n}{}}\eta _{a_i}):=_{V_g(a_1,\mathrm{},a_n)}\psi _1^{g+n2}\lambda _g.$$

### 2.2. Binomial decomposition

###### Theorem 2.1.

For arbitrary positive integers $`a_1,\mathrm{},a_n`$ we have

(2.2) $`(1)^gg!{\displaystyle _{\overline{}_{g,1}}}\psi _1^{2g2}\lambda _g=`$ $`\left({\displaystyle \genfrac{}{}{0pt}{}{g}{0}}\right)W_g({\displaystyle \underset{i=1}{\overset{n}{}}}\eta _{a_i})\left({\displaystyle \genfrac{}{}{0pt}{}{g}{1}}\right)W_g(\eta _1{\displaystyle \underset{i=1}{\overset{n}{}}}\eta _{a_i})`$
$`+\mathrm{}+(1)^g\left({\displaystyle \genfrac{}{}{0pt}{}{g}{g}}\right)W_g(\eta _1^g{\displaystyle \underset{i=1}{\overset{n}{}}}\eta _{a_i}).`$
### 2.3. Recursion relation

There is a recursion relation for the the numbers $`W_g(_{i=1}^n\eta _{a_i})`$:

###### Theorem 2.2.

If $`g+n2>0`$, then

(2.3) $`({\displaystyle \underset{i=1}{\overset{n}{}}}a_i)(2g+n1)W_g({\displaystyle \underset{i=1}{\overset{n}{}}}\eta _{a_i})=`$ $`{\displaystyle \underset{k<l}{}}(a_k+a_l)W_g(\eta _{a_k+a_l}{\displaystyle \underset{ik,l}{}}\eta _{a_i})`$
$`+{\displaystyle \underset{k=1}{\overset{n}{}}}{\displaystyle \frac{a_k^3a_k}{12}}W_{g1}({\displaystyle \underset{i=1}{\overset{n}{}}}\eta _{a_i}).`$
### 2.4. Initial values

Consider the case $`g+n2=0`$. This means that either $`g=1`$, $`n=1`$, or $`g=0`$, $`n=2`$. In these cases we have the following:

###### Theorem 2.3.

(2.4)
$$W_1(\eta _{a_1})=\frac{a_1^21}{24};W_0(\eta _{a_1}\eta _{a_2})=1.$$

### 2.5. Calculation of Hodge integrals

Now we have an algorithm to calculate the integrals $`_{\overline{}_{g,1}}\psi _1^{2g2}\lambda _g`$. First, we express such integral via the numbers $`W_g(_{i=1}^n\eta _{a_i})`$ (Theorem 2.1). Then we step by step simplify the numbers $`W_g(_{i=1}^n\eta _{a_i})`$ using Theorem 2.2 until we obtain numbers calculated in Theorem 2.3.

Let us apply this algorithm to calculate $`_{\overline{}_{1,1}}\lambda _1`$. The first step looks, for example, like follows:

$$_{\overline{}_{1,1}}\lambda _1=W_1(\eta _2)W_1(\eta _1\eta _2).$$

Then

$$33W_1(\eta _1\eta _2)=3W_1(\eta _3)+\frac{82}{12}W_0(\eta _1\eta _2).$$

Since

$$W_0(\eta _1\eta _2)=1,W_1(\eta _3)=\frac{8}{24},\mathrm{and}W_1(\eta _2)=\frac{3}{24},$$

we have

$$_{\overline{}_{1,1}}\lambda _1=\frac{3}{24}\frac{1}{3}\frac{8}{24}\frac{1}{9}\frac{6}{12}=\frac{1}{24}.$$

The same number is give by Equation 1.2.

## 3. The number $`W_g(\eta _1^n)`$ as a sum over trees

The algorithm of calculation of numbers $`W_g(\eta _1^n)`$ implies a representation of these numbers as a sum over some trees. In this section we describe the trees we need and prove a theorem expressing $`W_g(\eta _1^n)`$ via some numbers calculated by trees.

### 3.1. Decorated trees

Let us fix $`g0`$ and $`n1`$. We describe here trees corresponding to the number $`W_g(\eta _1^n)`$.

#### 3.1.1. Construction

We consider rooted trees. Each vertex has $`2`$ sons. 111If we have two connected vetices in a rooted tree, then one of these vertices is the son of another one. By son we call the vertex, which is farther from the root. We require that there are exactly $`n`$ vertices with no sons and exactly $`g`$ vertices with one son. This follows that there are exactly $`n1`$ vertices with two sons.

By leaves we call vertices with no sons. By $`V_0`$ denote the set of leaves. Let us assign to each leaf a personal number $`\mathrm{𝗇𝗆}`$ from the set $`\{1,\mathrm{},n\}`$. In other words, we consider a one-to-one correspondence $`\mathrm{𝗇𝗆}:V_0\{1,\mathrm{},n\}`$.

One more condition for the structure of trees is that the father of each leaf has two sons (In fact, we use this condition just to decrease the number of examples. The contribution of such trees to our formulas will be zero).

By $`V_1`$ denote the set of vertices with one son. By $`V_2`$ denote the set of vertices with two sons. Consider a map $`\mathrm{𝖼𝗉}:V_1V_2\{1,\mathrm{},2g+n1\}`$ satifying the following three properties:

1. The map $`\mathrm{𝖼𝗉}`$ takes different verices to different numbers.
2. If $`a\mathrm{𝖼𝗉}(V_1)`$, then $`a>1`$ and $`a1\mathrm{𝖼𝗉}(V_1V_2)`$.
3. If vertex $`v`$ is a ‘descendant’ of vertex $`v^{}`$, then $`\mathrm{𝖼𝗉}(v)>\mathrm{𝖼𝗉}(v^{})`$.

In particular, if the root vertex has one (resp., two) sons, then its image under the mapping $`\mathrm{𝖼𝗉}`$ is equal to $`2`$ (resp., $`1`$).

By a decorated tree (or $`(n,g)`$-decorated tree) we call all this data, i. e. a rooted tree with mappings $`\mathrm{𝗇𝗆}`$ and $`\mathrm{𝖼𝗉}`$.

#### 3.1.2. Examples

Consider $`n=3`$, $`g=2`$. Up to isomorphism, there are $`3`$ possible rooted trees with the mapping $`\mathrm{𝖼𝗉}`$.

Note that in this particular case the type of rooted graph uniquely determines the mapping $`\mathrm{𝖼𝗉}`$. For each of these graphs there are three possible mappings $`\mathrm{𝗇𝗆}`$.

Consider $`n=2`$, $`g=2`$. There is a unique possible rooted tree with the mapping $`\mathrm{𝖼𝗉}`$. For this tree there is a unique possible mapping $`\mathrm{𝗇𝗆}`$.

Consider $`n=1`$, $`g=2`$. There exists no such decorated trees. Moreover, if $`n=1`$, then a decorated tree exists if and only if $`g=0`$. In this case this tree consists just of one vertex.

### 3.2. Taking a number from a decorated tree

#### 3.2.1. Function $`ml`$.

Consider a decorated tree. Let us define one more function $`\mathrm{𝗆𝗅}:V_1V_2\{1,\mathrm{},n\}`$. The mapping $`\mathrm{𝗆𝗅}`$ takes a vertex to the number of its descendants in $`V_0`$.

In the examples studied above the mapping $`\mathrm{𝗆𝗅}`$ looks like follows:

#### 3.2.2. The numbers $`N(\mathrm{\Gamma })`$ and $`S_{g,n}`$.

To any $`(n,g)`$-decorated tree $`\mathrm{\Gamma }`$ we assign the number $`N(\mathrm{\Gamma })`$:

(3.1)
$$N(\mathrm{\Gamma })=\frac{1}{n^{(n+g1)}}\underset{vV_2}{}\frac{\mathrm{𝗆𝗅}(v)}{\mathrm{𝖼𝗉}(v)}\underset{vV_1}{}\frac{\mathrm{𝗆𝗅}(v)^3\mathrm{𝗆𝗅}(v)}{12\mathrm{𝖼𝗉}(v)}$$

By $`S_{g,n}`$ denote the sum

(3.2)
$$S_{g,n}=\underset{\mathrm{\Gamma }}{}N(\mathrm{\Gamma }),$$

where the sum is taken over all $`(n,g)`$-decorated trees $`\mathrm{\Gamma }`$.

### 3.3. Theorems

###### Theorem 3.1.

For any $`n1`$, $`g0`$, we have

(3.3)
$$W_g(\eta _1^n)=S_{g,n}.$$

This theorem implies purely combinatorial identities.

###### Corollary 3.2.

For any $`g1`$, $`n1`$, we have

(3.4)
$$\begin{array}{c}\left(\genfrac{}{}{0pt}{}{g}{0}\right)S_{g,n+g}\left(\genfrac{}{}{0pt}{}{g}{1}\right)S_{g,n+g1}+\mathrm{}+(1)^g\left(\genfrac{}{}{0pt}{}{g}{g}\right)S_{g,n}=\hfill \\ \hfill \frac{(2^{2g1}1)g!}{2^{2g1}(2g)!}|B_{2g}|.\end{array}$$

###### Corollary 3.3.

For any $`n1`$, we have

(3.5)
$$S_{0,n}=1.$$

Note that the trees determining the numbers $`S_{0,n}`$ have much more simple description then in the general case. So Corollary 3.3 has more simple and more beautiful reformulation.

### 3.4. Proof of Theorem 3.1

In fact, this Theorem is more or less obvious. Let us consider the calculation of the number $`W_g\eta _1^n`$ step by step. Simultaniously we try to build the corresponding graph.

At the beginning we have only $`n`$ vertices $`v_1^0,\mathrm{},v_n^0`$. The first step given by Equation 2.2:

(3.6)
$$W_g\eta _1^n=\frac{1}{n(2g+n1)}\underset{i<j}{}2W_g(\eta _2\eta _1^{n2}).$$

Consider the summand in the right hand side of this equation corresponding to the pair $`(i,j)`$, $`i<j`$. According to this summand we add to our graph the vertex $`v_{2g+n1}^2`$ with two sons, $`v_i^0`$ and $`v_j^0`$. We put $`\mathrm{𝖼𝗉}(v_{2g+n1}^2)=2g+n1`$ and we have $`\mathrm{𝗆𝗅}(v_{2g+n1}^2)=2`$. Therefore, the factor $`2/(2g+n1)`$ is equal to $`\mathrm{𝗆𝗅}(v_{2g+n1}^2)/\mathrm{𝖼𝗉}(v_{2g+n1}^2)`$ (Let us always skip the factor $`1/n`$ throughout our calculations).

Let us make the second step for this summand. We have:

(3.7) $`W_g(\eta _2\eta _1^{n2})=`$ $`{\displaystyle \frac{1}{n(2g+n2)}}{\displaystyle \underset{i^{}<j^{}}{}}2W_g(\eta _2^2\eta _1^{n4})`$
$`+{\displaystyle \frac{1}{n(2g+n2)}}{\displaystyle \underset{i^{}}{}}3W_g(\eta _3\eta _1^{n3})`$
$`+{\displaystyle \frac{1}{n(2g+n2)}}{\displaystyle \frac{2^32}{12}}W_{g1}(\eta _2\eta _1^{n2}).`$
Here we take all sums over $`i^{},j^{}\{1,\mathrm{},n\}\{i,j\}`$.

Consider the summand of the first sum in the right hand side of this equation corresponding to the pair $`(i^{},j^{})`$, $`i^{}<j^{}`$. According to this summand we add to our graph the vertex $`v_{2g+n2}^2`$ with two sons, $`v_i^{}^0`$ and $`v_j^{}^0`$. We put $`\mathrm{𝖼𝗉}(v_{2g+n2}^2)=2g+n2`$ and we have $`\mathrm{𝗆𝗅}(v_{2g+n2}^2)=2`$. Therefore, the factor $`2/(2g+n2)`$ is equal to $`\mathrm{𝗆𝗅}(v_{2g+n2}^2)/\mathrm{𝖼𝗉}(v_{2g+n2}^2)`$.

Consider the summand of the second sum in the right hand side of this equation corresponding to $`i^{}`$. According to this summand we add to our graph the vertex $`v_{2g+n2}^2`$ with two sons, $`v_i^{}^0`$ and $`v_{2g+n1}^2`$. We put $`\mathrm{𝖼𝗉}(v_{2g+n2}^2)=2g+n2`$ and we have $`\mathrm{𝗆𝗅}(v_{2g+n2}^2)=3`$. Therefore, the factor $`3/(2g+n2)`$ is equal to $`\mathrm{𝗆𝗅}(v_{2g+n2}^2)/\mathrm{𝖼𝗉}(v_{2g+n2}^2)`$.

Consider the summand of the second sum in the right hand side of this equation corresponding to $`W_{g1}(\eta _2\eta _1^{n2})`$. According to this summand we add to our graph the vertex $`v_{2g+n2}^1`$ with one sons, $`v_{2g+n1}^2`$. We put $`\mathrm{𝖼𝗉}(v_{2g+n2}^1)=2g+n2`$ and we have $`\mathrm{𝗆𝗅}(v_{2g+n2}^1)=2`$. Therefore, the factor $`(2^32)/12(2g+n2)`$ is equal to $`\mathrm{𝗆𝗅}(v_{2g+n2}^1)/\mathrm{𝖼𝗉}(v_{2g+n2}^1)`$.

Continue with this procedure one obtain the same representation of $`W_g(\eta _1^n)`$ as we have described. The missed factor $`1/n`$ gives the contribution $`1/n^{g+n1}`$; the same factor we have in our definition of $`N(\mathrm{\Gamma })`$.

## 4. Proofs of Theorems 2.1-2.3

### 4.1. Proof of Theorem 2.3

This Theorem consists of two formulas:

(4.1)
$$W_1(\eta _{a_1})=\frac{a_1^21}{24};W_0(\eta _{a_1}\eta _{a_2})=1.$$

Let us start with the second one. We have $`W_0(\eta _{a_1}\eta _{a_2})=_{V_0(a_1,a_2)}1`$. Since $`V_0(a_1,a_2)=\overline{}_{0,3}`$, it follows the required formula.

Consider now the first formula. It could be rewritten as

(4.2)
$$_{V_1(a_1)}\lambda _1=\frac{a_1^21}{24}.$$

Note that $`\lambda _1|_{V_1(a_1)}=\psi _1|_{V_1(a_1)}`$. The integral $`_{V_1(a_1)}\psi _1`$ equals

(4.3)
$$\frac{1}{4a_1}\underset{i=1}{\overset{a_11}{}}i(a_1i)_{V_0(i,a_1i)}1$$

(this follows from , Theorem 12.2). Since $`W_0(i,a_1i)=_{V_0(i,a_1i)}1=1`$ and $`_{i=1}^{a_11}i(a_1i)=(a_1^3a_1)/6`$, it follows that

(4.4)
$$_{V_1(a_1)}\lambda _1=_{V_1(a_1)}\psi _1=\frac{a_1^21}{24}.$$

### 4.2. Ionel Lemma

In this subsection we recall the Ionel Lemma, which is the main tool in the foregoing argument. For a more detailed explanation of this technique, see .

Consider the space $`\widehat{H}`$ of admissible coverings of genus $`g`$, of degree $`n`$, with $`m`$ critical values, and with partitions $`A_1,\mathrm{},A_m`$, $`A_i=(a_1^i,\mathrm{},a_{l_i}^i)`$, over these critical values. Of course, for any $`i`$, $`_{j=1}^{l_i}a_j^i=n`$, and $`_{i=1}^m_{j=1}^{l_i}(a_j^i1)=nm_{i=1}^ml_i=2g+2n2`$. Moreover, we consider admissible coverings with all marked preimages of all critical values.

There are two mapping of the space $`\widehat{H}`$. The first one, $`\mathrm{𝗌𝗍}:\widehat{H}\overline{}_{g,_{i=1}^ml_i}`$, takes an admissible covering to its source curve with marked preimages of critical values. The second mapping, $`\mathrm{𝗅𝗅}:\widehat{H}\overline{}_{0,m}`$, takes an admissible covering to its target curve with marked critical values.

Consider an admissible covering $`f\widehat{H}`$. Let

$$\mathrm{𝗌𝗍}(f)=(C_g,x_1^1,\mathrm{},x_{l_1}^1,\mathrm{},x_1^m,\mathrm{},x_{l_m}^m),\mathrm{𝗅𝗅}(f)=(C_0,z_1,\mathrm{},z_m).$$

We choose our notations to make $`x_j^i`$ be a preimage of $`x_i`$ of multiplicity $`a_j^i`$ w. r. t. the covering $`f`$.

Let $`\psi (x_j^i)`$ be the first Chern class of the line bundle over $`\overline{}_{g,_{i=1}^ml_i}`$, whose fiber at a moduli point $`(C_g,x_1^1,\mathrm{},x_{l_m}^m)`$ is equal to $`T_{x_j^i}^{}C_g`$. Let $`\psi (z_i)`$ be the first Chern class of the line bundle over $`\overline{}_{o,m}`$, whose fiber at a moduli point $`(C_0,z_1,\mathrm{},z_m)`$ is equal to $`T_{z_i}^{}C_g`$.

###### Lemma 4.1.

(Ionel Lemma, ) In cohomology ring of $`\widehat{H}`$ we have:

(4.5)
$$a_j^i\mathrm{𝗌𝗍}^{}\psi (x_j^i)=\mathrm{𝗅𝗅}^{}\psi (z_i).$$

### 4.3. Proof of Theorem 2.2

#### 4.3.1.

Consider the space $`V_g(a_1,\mathrm{},a_n)`$. Let $`\widehat{H}`$ be the space of admissible coverings of genus $`g`$, of degree $`N=a_1+\mathrm{}+a_n`$, with $`m=2g+n+1`$ critical values, and with partitions $`A_1=(N)`$, $`A_2=(a_1,\mathrm{},a_n)`$, $`A_3=\mathrm{}=A_m=(2,1,\mathrm{},1)`$ over these critical values.

In the foregoing we use the notations from the previous subsection.

Consider the projection $`\pi :\overline{}_{g,_{i=1}^ml_i}\overline{}_{g,1+n}`$, forgetting all marked points except for $`x_1^1,x_1^2,\mathrm{},x_n^2`$. Note that $`\pi \mathrm{𝗌𝗍}(\widehat{H})=V_g(a_1,\mathrm{},a_n)`$. Moreover, $`\pi _{}\mathrm{𝗌𝗍}_{}[\widehat{H}]=(m2)![V_g(a_1,\mathrm{},a_n)]`$.

We know that $`\psi (x_1^1)|_{\mathrm{𝗌𝗍}(\widehat{H})}=\pi ^{}\psi (x_1^1)`$ (this is proved in ). Therefore,

(4.6)
$$(m2)!\psi (x_1^1)|_{V_g(a_1,\mathrm{},a_n)}=\pi _{}\mathrm{𝗌𝗍}_{}\mathrm{𝗌𝗍}^{}\psi (x_1^1).$$

Since $`N\mathrm{𝗌𝗍}^{}\pi ^{}\psi (x_1^1)=\mathrm{𝗅𝗅}^{}\psi (z_1)`$ (this is Ionel Lemma), it follows that

(4.7)
$$(m2)!\psi (x_1^1)|_{V_g(a_1,\mathrm{},a_n)}=\frac{1}{N}\pi _{}\mathrm{𝗌𝗍}_{}\mathrm{𝗅𝗅}^{}\psi (z_1).$$

So, we are to take a divisor dual to $`\psi (z_1)`$ on $`\overline{}_{0,m}`$, then we get its preimage in $`\widehat{H}`$, and the mapping $`\pi \mathrm{𝗌𝗍}`$ takes this preimage to the divisor in $`V_g(a_1,\mathrm{},a_n)`$ dual to $`\psi (x_1^1)|_{V_g(a_1,\mathrm{},a_n)}`$.

Note that $`\psi (z_1)`$ on $`\overline{}_{0,m}`$ is dual to the divisor, whose generic point is represented by a two-component curve such that $`z_1`$ lie on one component and $`z_2`$ and $`z_3`$ lie on the other component.

#### 4.3.2.

Consider $`\psi (x_1^1)^{g+k2}\lambda _g[V_g(a_1,\mathrm{},a_k)]`$. If $`g+k2=0`$, then we have one of the cases considered in Theorem 2.3. Suppose that $`g+k2>0`$. Then we have

(4.8)
$$\begin{array}{c}\psi (x_1^1)^{g+k2}\lambda _g[V_g(a_1,\mathrm{},a_k)]=\hfill \\ \hfill \frac{1}{N(m2)!}\psi (x_1^1)^{g+k3}\lambda _g\pi _{}\mathrm{𝗌𝗍}_{}\mathrm{𝗅𝗅}^{}(\psi (z_1)[\overline{}_{0,m}])\end{array}$$

From dimensional conditions and since $`\lambda _g`$ restricted to the divisor of irreducible self-intersecting curves equals zero, it follows that only two types of divisors contribute to $`\psi (x_1^1)^{g+k3}\lambda _g\pi _{}\mathrm{𝗌𝗍}_{}\mathrm{𝗅𝗅}^{}(\psi (z_1)\overline{}_{0,m})`$. (We skip here some argument on the boundary behaviour of the space $`\widehat{H}`$. We refer to  for details.)

A divisor $`D_{i,j}`$ of the first type consists of two-compenent curves $`(C,x_1^1,x_1^2,\mathrm{},x_n^2)V_g(a_1,\mathrm{},a_n)`$ such that one component of $`C`$ has genus zero and contains only $`x_i^2`$ and $`x_j^2`$. Here pairs $`(i,j)`$ enumerate such divisors. Obviously, the restriction of $`\psi (x_1^1)^{g+k3}\lambda _g`$ to the divisor $`D_{i,j}`$ is equal to the integral of this class over

$$V_g(a_1,\mathrm{},\widehat{a}_i,\mathrm{},\widehat{a}_j,\mathrm{},a_n,a_i+a_j).$$

The multiplicity of the mapping $`\pi \mathrm{𝗌𝗍}`$ over $`D_{i,j}`$ equals $`(m3)!`$. The multiplicity of the mapping $`\mathrm{𝗅𝗅}`$ at $`(\pi \mathrm{𝗌𝗍})^1(D_{i,j})`$ equals $`a_i+a_j`$. Thus we obtain that the coefficient of the correspoding summand in Equation 2.3 equals

(4.9)
$$\frac{(a_i+a_j)(m3)!}{N(m2)!}=\frac{(a_i+a_j)}{(2g+n1)(_{i=1}^na_i)}.$$

A divisor $`D_i`$ of the second type consists of two-component curves $`(C,x_1^1,x_1^2,\mathrm{},x_n^2)V_g(a_1,\mathrm{},a_n)`$ such that one component of $`C`$ has genus one and contains only $`x_i`$. Obviously, the restriction of $`\psi (x_1^1)^{g+k3}\lambda _g`$ to the divisor $`D_{i,j}`$ is equal to the integral of $`\psi (x_1^1)^{g+k3}\lambda _{g1}`$ over $`V_{g1}(a_1,\mathrm{},a_n)`$ multiplied by the integral of $`\lambda _1`$ over $`V_1(a_i)`$. It follows from Theorem 2.3 that last factor equals $`(a_i^21)/24`$.

The multiplicity of the mapping $`\pi \mathrm{𝗌𝗍}`$ over $`D_i`$ equals $`2(m3)!`$. The multiplicity of the mapping $`\mathrm{𝗅𝗅}`$ at $`(\pi \mathrm{𝗌𝗍})^1(D_{i,j})`$ equals $`a_i`$. Thus we obtain that the coefficient of the correspoding summand in Equation 2.3 equals

(4.10)
$$a_i\frac{(a_i^21)}{24}\frac{2(m3)!}{N(m2)!}=\frac{a_i^3a_i}{12(2g+n1)(_{i=1}^na_i)}.$$

This concludes the proof.

### 4.4. Proof of Theorem 2.1

#### 4.4.1.

Let us fix $`g`$ and $`a_1,\mathrm{},a_n`$. By $`V_g^i`$ denote

(4.11)
$$V_g^i:=V_g(a_1,\mathrm{},a_n\underset{i}{\underset{}{1,\mathrm{},1}}).$$

Recall that $`V_g^i`$ is the subspace of $`\overline{}_{g,n+i+1}`$ consisting of curves $`(C,x_1,\mathrm{},x_{n+i+1})`$ such that

$$(N+i)x_1+a_1x_2+\mathrm{}+a_nx_{n+1}+x_{n+2}+\mathrm{}+x_{n+i+1}$$

is the divisor of a meromorphic function.

Consider the mappings $`\pi _{j,i}:V_g^j\overline{}_{g,n+j+1i}`$ forgetting the marked points $`x_{n+j+2i},\mathrm{},x_{n+j+1}`$. Note that $`\pi _{j,i,}[V_g^j]=i![\pi _{i,}(V_g^j)]`$, $`\pi _{j,i}(V_g^j)=\pi _{j+1,i+1}(V_g^{j+1})`$, and $`\pi _{g,g}(V_g^g)=\overline{}_{g,n+1}`$.

Recall that our goal is to get an expression of $`_{\overline{}_{g,1}}\psi _1^{2g2}\lambda _g=_{\overline{}_{g,n+1}}\psi _1^{2g+n2}\lambda _g`$. We shall do this in $`g`$ steps.

#### 4.4.2.

Consider the projection $`\sigma \overline{}_{g,n+2}\overline{}_{g,n+1}`$ forgetting the last marked point. We have

(4.12)
$$\sigma ^{}(\psi _1)^{2g+n2}=\psi _1^{2g+n2}\sigma ^{}(\psi _1)^{2g+n3}D,$$

where $`D`$ is the class of the divisor, whose generic point is represented by a two-component curve such that one component has genus zero and contains $`x_1`$ and $`x_{n+2}`$ and the other component has genus $`g`$ and contains all other points.

Since $`\sigma ^{}\lambda =\lambda `$, we have:

(4.13)
$$\begin{array}{c}I:=_{\overline{}_{g,n+1}}\psi _1^{2g+n2}\lambda _g=\hfill \\ \hfill _{\pi _{g,g}(V_g^g)}\psi _1^{2g+n2}\lambda _g=\frac{1}{g}_{\pi _{g,g1}(V_g^g)}\sigma ^{}(\psi _1)^{2g+n2}\lambda _g\end{array}$$

Note that

(4.14)
$$\sigma (D\pi _{g,g1}(V_g^g))=\pi _{g1,g1}(V_g^{g1}).$$

Therefore,

(4.15)
$$I=\frac{1}{g}_{\pi _{g,g1}(V_g^g)}\psi _1^{2g+n2}\lambda _g\frac{1}{g}_{\pi _{g1,g1}(V_g^{g1})}\psi _1^{2g+n3}\lambda _g.$$

#### 4.4.3.

Applying the same argument to the right hand side of Equation 4.15 we get:

(4.16) $`{\displaystyle _{\pi _{g,g1}(V_g^g)}}\psi _1^{2g+n2}\lambda _g=`$ $`{\displaystyle \frac{1}{g1}}{\displaystyle _{\pi _{g,g2}(V_g^g)}}\psi _1^{2g+n2}\lambda _g`$
$`{\displaystyle \frac{1}{g1}}{\displaystyle _{\pi _{g1,g2}(V_g^{g1})}}\psi _1^{2g+n3}\lambda _g`$
and

(4.17) $`{\displaystyle _{\pi _{g1,g1}(V_g^{g1})}}\psi _1^{2g+n3}\lambda _g=`$ $`{\displaystyle \frac{1}{g1}}{\displaystyle _{\pi _{g1,g2}(V_g^{g1})}}\psi _1^{2g+n3}\lambda _g`$
$`{\displaystyle \frac{1}{g1}}{\displaystyle _{\pi _{g2,g2}(V_g^{g2})}}\psi _1^{2g+n4}\lambda _g`$
Thus we have:

(4.18) $`g(g1)I=`$ $`{\displaystyle _{\pi _{g,g2}(V_g^g)}}\psi _1^{2g+n2}\lambda _g2{\displaystyle _{\pi _{g1,g2}(V_g^{g1})}}\psi _1^{2g+n3}\lambda _g`$
$`+{\displaystyle _{\pi _{g2,g2}(V_g^{g2})}}\psi _1^{2g+n4}\lambda _g.`$
Continue with this procedure we obtain:

(4.19) $`g!I=`$ $`\left({\displaystyle \genfrac{}{}{0pt}{}{g}{0}}\right){\displaystyle _{\pi _{g,0}(V_g^g)}}\psi _1^{2g+n2}\lambda _g\left({\displaystyle \genfrac{}{}{0pt}{}{g}{1}}\right){\displaystyle _{\pi _{g1,0}(V_g^{g1})}}\psi _1^{2g+n3}\lambda _g`$
$`+\mathrm{}+(1)^g\left({\displaystyle \genfrac{}{}{0pt}{}{g}{g}}\right){\displaystyle _{\pi _{0,0}(V_g^0)}}\psi _1^{g+n2}\lambda _g.`$
Since $`\pi _{i,0}`$ are identical mappings, this equation is exactly the statement of Theorem 2.1.

## Appendix A Some calculations in genus 2

Here we give some calculations checking independently in a special case Corollary 3.2 and therefore the whole algorithm for computing Hodge integrals.

Let us put $`g=2`$, $`n=1`$. Recall that $`B_4=1/30`$. So, we would like to check that

(A.1)
$$S_{2,3}2S_{2,2}=\frac{72}{82430}=\frac{7}{2^63^25}$$

We have already studied in examples all types of graphs contributing to $`S_{2,3}`$ and $`S_{2,2}`$:

The number $`S_{2,3}`$ is determined by the first three types of graphs. These graphs have 3 possible mappings $`\mathrm{𝗇𝗆}`$. The mappings $`\mathrm{𝖼𝗉}`$ and $`\mathrm{𝗆𝗅}`$ for these graphs are defined above. Thus we have that the first type of graphs contributes

(A.2)
$$3\frac{1}{3^4}\frac{23}{2456}\left(\frac{24}{12}\right)^2=\frac{1}{23^35},$$

the second type of graphs contributes

(A.3)
$$3\frac{1}{3^4}\frac{23}{2356}\frac{624}{12^2}=\frac{1}{23^45},$$

and the third type of graphs contributes

(A.4)
$$3\frac{1}{3^4}\frac{23}{1356}\left(\frac{6}{12}\right)^2=\frac{1}{2^23^45}.$$

Therefore,

(A.5)
$$S_{2,3}=\frac{1}{2^23^25}.$$

The number $`S_{2,2}`$ is determined by the fourth type of graph. This graph has the unique possible mapping $`\mathrm{𝗇𝗆}`$. The mappings $`\mathrm{𝖼𝗉}`$ and $`\mathrm{𝗆𝗅}`$ for this graph are also defined above. Thus we have

(A.6)
$$S_{2,2}=\frac{1}{2^3}\frac{2}{245}\left(\frac{6}{12}\right)^2=\frac{1}{2^75}.$$

Therefore,

(A.7)
$$S_{2,3}2S_{2,2}=\frac{1}{2^23^25}\frac{1}{2^65}=\frac{7}{2^63^25}.$$

The same equality is given by Corollary 3.2.

## Appendix B Genuz $`0`$ case

In genus zero we have the most simple and beautiful combinatorics. Moreover, in this case our argument with intersections on the moduli spaces of curves could be considered as a purely combinatorial argument.

### B.1. Genus zero combinatorial statement

Let us fix $`g0`$ and $`n1`$. We describe here trees corresponding to the number $`W_g(\eta _1^n)`$.

We consider rooted trees. Each vertex has either $`2`$ sons or no sons. We have exactly $`n`$ vertices with no sons (leaves) an $`n1`$ vertices with two sons.

By $`V_0`$ denote the set of leaves. An item of the construction is a one-to-one correspondence $`\mathrm{𝗇𝗆}:V_0\{1,\mathrm{},n\}`$.

By $`V_2`$ denote the set of vertices with two sons. Consider a one-to-one map $`\mathrm{𝖼𝗉}:V_2\{1,\mathrm{},n1\}`$ satifying the following property: If vertex $`v`$ is a ‘descendant’ of vertex $`v^{}`$, then $`\mathrm{𝖼𝗉}(v)>\mathrm{𝖼𝗉}(v^{})`$.

By a decorated $`n`$-tree we call all this data, i. e. a rooted tree with mappings $`\mathrm{𝗇𝗆}`$ and $`\mathrm{𝖼𝗉}`$.

Consider a decorated $`n`$-tree. Let us define one more function $`\mathrm{𝗆𝗅}:V_2\{1,\mathrm{},n\}`$. The mapping $`\mathrm{𝗆𝗅}`$ takes a vertex to the number of its descendants in $`V_0`$.

Let $`\mathrm{\Gamma }`$ be a decorated tree. By $`N(\mathrm{\Gamma })`$ denote the number

(B.1)
$$N(\mathrm{\Gamma }):=\frac{1}{n^{(n1)}}\underset{vV_2}{}\frac{\mathrm{𝗆𝗅}(v)}{\mathrm{𝖼𝗉}(v)}$$

The special case of Theorem 3.1 looks like follows:

###### Theorem B.1.

For any $`n`$ we have

(B.2)
$$\underset{\mathrm{\Gamma }}{}N(\mathrm{\Gamma })=1,$$

where the sum is taken over all decorated $`n`$-trees $`\mathrm{\Gamma }`$.

### B.2. Proof of Theorem B.1

As we have already shown in Section 3, $`_\mathrm{\Gamma }N(\mathrm{\Gamma })`$ equals the number $`W_0(\eta _1^n)`$, where the numbers $`W_0(_{i=1}^k\eta _{a_i})`$ are defined by the recursion relation

(B.3)
$$(\underset{i=1}{\overset{k}{}}a_i)(k1)W_0(\underset{i=1}{\overset{k}{}}\eta _{a_i})=\underset{k<l}{}(a_k+a_l)W_0(\eta _{a_k+a_l}\underset{ik,l}{}\eta _{a_i}),$$

and initial data

(B.4)
$$W_0(\eta _{a_1}\eta _{a_2})=1$$

(we give here the special case of this relation for genus $`0`$).

Note that the numbers $`W_0(_{i=1}^k\eta _{a_i})`$ are uniquely determined by this relation. Note also that $`W_0(_{i=1}^k\eta _{a_i})=1`$ obviously satisfy this relation and the initial data. So, for any $`a_1,\mathrm{},a_k`$ $`W_0(_{i=1}^k\eta _{a_i})=1`$. In particular, $`W_0(\eta _1^n)=1`$.

## Appendix C The other Hodge integrals

In this section we give an algorithm to calculate any Hodge integral

(C.1)
$$_{\overline{}_{g,1}}\psi _1^{3g2i}\lambda _i.$$

### C.1. Algorithm

By $`W_g^i(\eta _{a_1}\mathrm{}\eta _{a_n})`$ denote the intersection number

(C.2)
$$W_g^i(\eta _{a_1}\mathrm{}\eta _{a_n}):=_{V_g(a_1,\mathrm{},a_n)}\psi _1^{2g+n2i}\lambda _i$$

The first step of the algorithm is just the same as in the $`\lambda _g`$-case.

###### Theorem C.1.

For arbitrary positive integers $`a_1,\mathrm{},a_n`$ we have

(C.3)
$$\begin{array}{c}(1)^gg!_{\overline{}_{g,1}}\psi _1^{3g2i}\lambda _i=\left(\genfrac{}{}{0pt}{}{g}{0}\right)W_g^i(\underset{i=1}{\overset{n}{}}\eta _{a_i})\left(\genfrac{}{}{0pt}{}{g}{1}\right)W_g^i(\eta _1\underset{i=1}{\overset{n}{}}\eta _{a_i})+\hfill \\ \hfill \left(\genfrac{}{}{0pt}{}{g}{2}\right)W_g^i(\eta _1^2\underset{i=1}{\overset{n}{}}\eta _{a_i})\mathrm{}+(1)^g\left(\genfrac{}{}{0pt}{}{g}{g}\right)W_g^i(\eta _1^g\underset{i=1}{\overset{n}{}}\eta _{a_i})\end{array}$$

The recursion relation for the numbers $`W_g^i(_{i=1}^n\eta _{a_i})`$ looks like follows:

###### Theorem C.2.

If $`2g+n2i>0`$, then

(C.4)
$$\begin{array}{c}(\underset{i=1}{\overset{n}{}}a_i)(2g+n1)W_g^i(\underset{i=1}{\overset{n}{}}\eta _{a_i})=\underset{k<l}{}(a_k+a_l)W_g^i(\eta _{a_k+a_l}\underset{ik,l}{}\eta _{a_i})\hfill \\ \hfill +\underset{k=1}{\overset{n}{}}\frac{a_k^3a_k}{12}W_{g1}^{i1}(\underset{i=1}{\overset{n}{}}\eta _{a_i})+\frac{1}{2}\underset{k=1}{\overset{n}{}}\underset{a_k^{}+a_k^{\prime \prime }=a_k}{}a_k^{}a_k^{\prime \prime }W_{g1}^i(\eta _{a_k^{}}\eta _{a_k^{\prime \prime }}\underset{ik}{}\eta _{a_i}).\end{array}$$

The initial values are just the same as in the $`\lambda _g`$-case.

###### Theorem C.3.

If $`i>g`$ then $`W_g^i(\eta _{a_1}\mathrm{}\eta _{a_n})=0`$. Besides,

(C.5)
$$W_1^1(\eta _{a_1})=\frac{a_1^21}{24};W_0^0(\eta _{a_1}\eta _{a_2})=1.$$

Proofs of these Theorems are very similiar to the proofs of Theorems 2.1-2.3. So we skip the proofs.

### C.2. Some calculations

Let us apply our algorithm to compute the integral $`_{\overline{}_{2,1}}\psi _1^3\lambda _1`$. Using Theorem C.1, we get

(C.6)
$$_{\overline{}_{2,1}}\psi _1^3\lambda _1=\frac{1}{2}W_2^1(\eta _1^3)W_2^1(\eta _1^2).$$

Applying many times Theorems C.2 and C.3, we obtain

(C.7)
$$W_2^1(\eta _1^3)=\frac{1}{120};W_2^1(\eta _1^2)=\frac{1}{480}.$$

Therefore,

(C.8)
$$_{\overline{}_{2,1}}\psi _1^3\lambda _1=\frac{1}{240}\frac{1}{480}=\frac{1}{480}.$$

The same number is given by Equation 1.2.