text:
# Zeros of Chromatic and Flow Polynomials of Graphs

## 1 Introduction

The study of chromatic polynomials of graphs was initiated by Birkhoff  in 1912 and followed by Whitney  in 1932. Inspired by the 4-Colour Conjecture, Birkhoff and Lewis , obtained results concerning the distribution of the real zeros of chromatic polynomials of planar graphs and made the stronger conjecture that chromatic polynomials of planar graphs have no real zeros greater than or equal to four. Their hope was that results from analysis and algebra could be used to prove their stronger conjecture and hence deduce that the 4-colour conjecture was true. This has not yet occured: indeed the 4-colour conjecture is now a theorem , but the stronger conjecture of Birkhoff and Lewis remains unsolved. Nevertheless, many beautiful results have been obtained concerning the zero distibution of chromatic polynomials both on the real line and in the complex plane, and many other intriguing problems remain open. I will summarise these in Section 2 below.

Flow polynomials were introduced by Tutte in  as dual polynomials to chromatic polynomials. This duality holds only for planar graphs, however, and the zero distributions of chromatic and flow polynomials for non-planar graphs seem to be quite different. There are many similarities between the zero distribution of flow polynomials for general graphs and for planar graphs. This is not the case for chromatic polynomials. One possible reason for this is that chromatic polynomials of planar graphs are strongly influenced by the fact that the cycle space of a planar graph has a basis consisting of a set of circuits which cover every edge at most twice (obtained by taking the boundaries of all but one of the faces). The dual property, that the cocycle space has a basis consisting of a set of cocircuits which cover every edge at most twice holds for all graphs, and can be obtained by taking the stars centred on all but one of the vertices. Flow polynomials have received much less attention than chromatic polynomials in the literature. I will summarise what little is known about their zero distribution in Section 3.

Characteristic polynomials of matroids provide a common generalization of chromatic and flow polynomials of graphs. I will describe how some of the results from Sections 2 and 3 can be extended to this more general setting in Section 4.

All graphs considered are finite and may contain loops and multiple edges. We shall refer to graphs without loops and multiple edges as simple graphs. We use $`K_n`$ and $`K_{m,n}`$ to denote the complete graph on $`n`$ vertices and the complete bipartite graph with vertex sets of sizes $`m`$ and $`n`$, respectively.

A graph $`G`$ is said to be non-separable if $`G`$ is connected and $`Gv`$ is connected for all $`vV(G)`$. A subgraph $`H`$ of $`G`$ is a component, respectively block, of $`G`$ if it is a maximal connected, respectively non-separable, subgraph of $`G`$. The graph $`G`$ is $`k`$-connected if $`|V(G)|k+1`$ and $`GU`$ is connected for all $`UV(G)`$ with $`|U|<k`$. Given an edge $`e`$ in $`G`$, we use $`Ge`$ to denote the graph obtained from $`G`$ by deleting $`e`$, and $`G/e`$ to denote the graph obtained from $`G`$ by contracting $`e`$. We say that $`e`$ is a bridge of $`G`$ if $`Ge`$ has more components than $`G`$.

## 2 Chromatic Polynomials

Let $`t`$ be a positive integer and $`G`$ be a graph. A proper $`t`$-colouring of $`G`$ is an assignment of $`t`$ colours to the vertices of $`G`$ in such a way that adjacent vertices of $`G`$ receive different colours. If $`G`$ has a loop then $`G`$ does not have a proper $`t`$-colouring for any $`t`$. If $`G`$ is loopless, then the chromatic number, $`\chi (G)`$ is the minimum value of $`t`$ for which $`G`$ has a proper $`t`$-colouring. We use $`P(G,t)`$ to denote the chromatic polynomial of $`G`$. This is defined for integer values of $`t1`$ as the number of distinct $`t`$-colourings of $`G`$. (Hence $`P(G,t)0`$ if $`G`$ has a loop.) The fact that $`P(G,t)`$ is a polynomial in $`t`$ and many other properties of $`P(G,t)`$ can be deduced from the following elementary lemma.

###### Lemma 1

Let $`G`$ be a graph and $`e`$ be an edge of $`G`$. Then

$$P(G,t)=P(Ge,t)P(G/e,t).$$

Lemma 1 also gives rise to a recursive procedure for calculating chromatic polynomials. This calculation can often be simplified using:

###### Lemma 2

Let $`G`$ be a graph and $`G_1`$ and $`G_2`$ be subgraphs of $`G`$ such that $`G_1G_2=G`$ and $`G_1G_2K_r`$. Then

$$P(G,t)=\frac{P(G_1,t)P(G_2,t)}{t(t1)\mathrm{}(tr+1)}.$$

Note that it is NP-hard to determine the chromatic number of a graph. Since the chromatic number of $`G`$ is one greater than than the smallest positive integer root of $`P(G,t)`$, it is also NP-hard to determine $`P(G,t)`$.

I will refer to the zeros of $`P(G,t)`$ as chromatic roots of $`G`$. The distribution of chromatic roots either on the real line or in the complex plane is of interest to graph theorists principally because of its implication for the integer chromatic roots and hence the chromatic number of a graph. The distribution of chromatic roots in the complex plane is also of independent interest to physicists because of its relevence to phase transitions via the Potts model partition function, see for example \[27, Section 1\].

### 2.1 General Graphs

Since graphs can have arbitrarily large chromatic numbers (for example $`K_n`$ has chromatic number $`n`$) they can have arbitrarily large integer chromatic roots. It follows, from the definition of $`P(G,t)`$, however, that a graph $`G`$ can have no integer chromatic root in the interval $`[\chi (G),\mathrm{})`$. One might hope that this result can be extended to real chromatic roots but this is not the case. Woodall  has shown that complete bipartite graphs (which have chromatic number two) have arbitrarily large chromatic roots. More precisely, he showed that if $`n`$ is large enough compared to $`m`$, then $`K_{m,n}`$ has chromatic roots arbitarily close to $`i`$, for all integers $`i`$, $`2im/2`$.

On the other hand, the following results due to Tutte, Woodall and the author imply that the only real numbers in $`(\mathrm{},\frac{32}{27}]`$ which are chromatic roots are $`0`$ and $`1`$.

###### Theorem 3

Let $`G`$ be a loopless graph with $`n`$ vertices, $`c`$ components, and $`b`$ blocks which are not isolated vertices. Then:

1. $`P(G,t)`$ is non-zero with sign $`(1)^n`$ for $`t(\mathrm{},0)`$ ;
2. $`P(G,t)`$ has a zero of multiplicity $`c`$ at $`t=0`$ ;
3. $`P(G,t)`$ is non-zero with sign $`(1)^{n+c}`$ for $`t(0,1)`$, ;
4. $`P(G,t)`$ has a zero of multiplicity $`b`$ at $`t=1`$, ;
5. $`P(G,t)`$ is non-zero with sign $`(1)^{n+c+b}`$ for $`t(1,\frac{32}{27}](1,1.185]`$, ;

The next result, due to Thomassen and Sokal, indicates that it is not possible to extend Theorem 3 beyond the real interval $`(\mathrm{},\frac{32}{27}]`$ or into any region of the complex plane.

###### Theorem 4

1. The real chromatic roots of graphs are dense everywhere in $`[\frac{32}{27},\mathrm{})`$
2. The complex chromatic roots of graphs are dense everywhere in the complex plane. .

### 2.2 3-connected graphs

We can construct 2-connected graphs with real chromatic roots in $`(1,2)`$ as follows. Let $`G`$ be a 2-connected graph with an odd number of vertices. It follows from Theorem 3(c),(d) that $`P(G,1)=0`$ and that $`P(G,t)`$ becomes negative when $`t`$ increases from 1. If, in addition, we assume that $`G`$ is bipartite, then $`P(G,2)=2`$ and hence $`P(G,t)`$ must have a zero in $`(1,2)`$. We may combine these graphs with any other graph using Lemma 2, with $`r=2`$, to construct 2-connected non-bipartite graphs with chromatic roots in $`(1,2)`$. It is conceivable, however, that Theorem 3 can be extended if we add the hypothesis that $`G`$ is 3-connected. (The same construction cannot be used to construct 3-connected non-bipartite examples because $`K_r`$ is not bipartite when $`r=3`$.)

###### Conjecture 5

Let $`G`$ be a loopless 3-connected graph.

1. $`P(G,t)`$ is non-zero with sign $`(1)^n`$ for $`t(1,\alpha )`$, where $`\alpha 1.781`$ is the chromatic root of $`K_{3,4}`$ in $`(1,2)`$.
2. If $`G`$ is not a bipartite graph with an odd number of vertices, then $`P(G,t)`$ is non-zero with sign $`(1)^n`$ for $`t(1,2)`$.

Conjecture 5(b) is a slight strengthening of a conjecture given in .

The proof technique used in proving Theorem 3 is inductive, using Lemmas 1 and 2. The main difficulty in extending this technique to prove Conjecture 5, is that edge deletion and contraction may result in a graph of connectivity 2, to which Lemma 2 cannot be directly applied.

There seems to be no hope of extending Theorem 3 into the complex plane by adding a connectivity hypothesis since Sokal’s result Theorem 4(b) holds for chromatic roots of $`k`$-connected graphs for any fixed $`k`$.

### 2.3 Hamiltonian graphs

Thomassen  suggested that the family of hamiltonian graphs may be another family for which Theorem 3 can be extended. He made the following attractive conjecture:

###### Conjecture 6

 If $`G`$ is hamiltonian and loopless then $`P(G,t)`$ is non-zero with sign $`(1)^n`$ for $`t(1,2)`$.

As evidence in favour of this conjecture, Thomassen showed in  that the zero free interval of $`(1,\frac{32}{27}]`$ can be extended for graphs with a Hamilton path.

###### Theorem 7

Let $`G`$ be a loopless graph with $`n`$ vertices and $`b`$ blocks. If $`G`$ has a Hamilton path, then $`P(G,t)`$ is non-zero with sign $`(1)^{n+b+1}`$ for $`t(1,\gamma ]`$ where $`\gamma 1.296`$ is the real root of $`(2t)^3=4(t1)^2`$.

Thomassen  also constructed a sequence of graphs with Hamilton paths and with chromatic roots converging to $`\gamma `$.

We can use Lemmas 1 and 2 to show that a smallest conterexample to Conjecture 6 would be 3-connected, see . Thus Conjecture 6 would follow from Conjecture 5(b). Conjecture 6 would also follow from an affirmative answer to the following intriguing problem posed by Thomassen, using Lemmmas 1 and 2, see .

###### Problem 8

 Does every hamiltonian graph of minimum degree at least three have an edge $`e`$ such that both $`Ge`$ and $`G/e`$ are hamiltonian?

### 2.4 Planar Graphs

As mentioned above, chromatic polynomials were introduced by Birkhoff and Lewis  in 1946 as a means of attacking the four colour conjecture. Heawood  had already proved that the chromatic number of any planar graph is at most five. One of their main results in  is the following nice generalization of Heawood’s theorem.

###### Theorem 9

Let $`G`$ be a loopless planar graph. Then $`P(G,t)>0`$ for $`t[5,\mathrm{})`$.

Birkhoff and Lewis  conjecture that a similar extension of the 4-colour theorem holds.

###### Conjecture 10

Let $`G`$ be a loopless planar graph. Then $`P(G,t)>0`$ for $`t[4,\mathrm{})`$.

One might hope that Theorem 3 could also be extended into the real interval $`(\frac{32}{27},4)`$ for the special case of planar graphs. The following result and conjecture of Thomassen  indicate that this is probably not the case.

###### Theorem 11

The real chromatic roots of planar graphs are dense everywhere in $`[\frac{32}{27},3]`$.

###### Conjecture 12

The real chromatic roots of planar graphs are dense everywhere in $`[\frac{32}{27},4]`$.

One may also hope that the complex plane may contain zero-free regions for chromatic polynomials of planar graphs. The following result of Sokal  limits the location of any such region.

###### Theorem 13

The complex chromatic roots of planar graphs are dense everywhere in the complex plane with the possible exception of the disc $`|t1|<1`$.

The planar graphs which Sokal uses to prove Theorem 13 are simply two vertices joined by $`p`$ internally disjoint paths of length $`d`$. He shows that as $`p`$ and $`d`$ vary, the complex chromatic roots of graphs in this family are dense everywhere outside $`|t1|<1`$. Graphs in the family also have roots inside the disc $`|t1|<1`$, but it is still an open problem to determine whether the complex roots of planar graphs are dense everywhere in the complex plane. Theorem 13 shows that Theorem 9 cannot be extended to the complex plane.

Much less is known about complex chromatic roots of planar graphs of connectivity greater than 2. Read and Tutte  have shown that the ‘bipyramids’ $`C_n+\overline{K_2}`$ are examples of 4-connected plane triangulations with complex chromatic roots of unbounded modulus, and Jacobsen, Salas, and Sokal  have constructed 4-connected plane graphs which have complex chromatic roots with real part greater than 4. Thus there is no obvious extension of Conjecture 10 to the complex plane, even for 4-connected planar graphs.

### 2.5 Plane Triangulations

A plane triangulation is a loopless plane graph in which all faces have size three. They have a special significance in the study of chromatic roots of planar graphs; for example, we can use Lemma 1 to show that Conjecture 10 is true if and only if it is true for plane triangulations. We shall see below that the chromatic roots of plane triangulations are much better behaved than those of planar graphs in general.

Birkhoff and Lewis, and Woodall, have shown that Theorem 3 can be extended beyond $`(\mathrm{},\frac{32}{27}]`$ for plane triangulations.

###### Theorem 14

Let $`G`$ be a 3-connected plane triangulation with $`n`$ vertices. Then:

1. $`P(G,t)`$ is non-zero with sign $`(1)^n`$ for $`t(1,2)`$ ;
2. $`P(G,t)`$ has a simple zero at $`t=2`$ ;
3. $`P(G,t)`$ is non-zero with sign $`(1)^{n+1}`$ for $`t(2,\delta )`$, where $`\delta 2.546`$ is the chromatic root of the octahedron in $`(2,3)`$ .

One may construct infinite families of 3-connected plane triangulations with a chromatic root at $`\delta `$ by combining the octahedron with an arbitary plane triangultaion using Lemma 2 with $`r=3`$. In particular, if we iteratively combine copies of the octahedron with itself, we obtain an infinite family of plane triangulations whose only chromatic root in $`(2,3)`$ is $`\delta `$. On the other hand, the following beautiful conjectures of Woodall  suggest that it may be possible to extend Theorem 14 for plane triangulations of connectivity greater than three.

###### Conjecture 15

Let $`G`$ be a plane triangulation.

1. If $`G`$ is 4-connected then $`P(G,t)`$ has at most one zero in $`(2,\tau ^2)`$, where $`\tau =\frac{1+\sqrt{5}}{2}`$ is the golden ratio, and $`\tau ^22.61803`$.
2. If $`G`$ is 5-connected then $`P(G,t)`$ has exactly one zero in $`(2,\theta )`$, and no zeros in $`(\theta ,3)`$, where $`\theta 2.61819`$ is the chromatic root of the icosahedron in $`(2,3)`$.

###### Conjecture 16

1. Fot all $`ϵ>0`$, there exist only finitely many 4-connected plane triangulations with a chromatic root in $`(2,\tau ^2ϵ)`$.
2. For all $`ϵ>0`$, there exist only finitely many 5-connected plane triangulations with a chromatic root in $`(\tau ^2+ϵ,3)`$.

The following intriguing result of Tutte  shows that $`\tau ^2`$ has a special significance for chromatic polynomials of plane triangulations.

###### Theorem 17

Let $`G`$ be a plane triangulation with $`n`$ vertices. Then
$`0|P(G,\tau ^2)|\tau ^{5n}`$.

Note however that Tutte’s result should not be seen as evidence that plane triangulations have chromatic roots close to $`\tau ^2`$: we have seen above that there exists an infinite family of 3-connected plane triangulations whose only chromatic root in $`(2,3)`$ is $`\delta 2.546`$.

The number $`\tau ^2`$ is an element of an infinite sequence of real numbers, called the Beraha numbers, which seem to have a special significance for chromatic polynomials of plane triangulations, see . For each integer $`r2`$, let $`b_r=2+2\mathrm{cos}\frac{2\pi }{r}`$. Thus $`b_2=0,b_3=1,b_4=2,b_5=\tau ^2,b_6=3`$, and $`lim_r\mathrm{}b_r=4`$.

###### Conjecture 18

(Beraha , see \[18, 14.6\]) There exists a plane triangulation with a real chromatic root in $`(b_rϵ,b_r+ϵ)`$ for all $`r2`$ and all $`ϵ>0`$.

This conjecture would imply that there exist plane triangulations with real chromatic roots arbitrarily close to 4. Note that it is mistakenly stated in  that Beraha and Kahane  have shown that this is true: in fact they construct plane triangulations with complex chromatic roots arbitrarily close to 4. Indeed it is an open problem to determine the supremum of the real chromatic roots of plane triangulations. (Lemma 1 can be used to show that this will be equal to the supremum over all planar graphs, and hence Conjecture 12 would also imply that the supremum is 4.) The largest real chromatic root of a plane triangulation that I know of, 3.8267…, is a root of a plane triangulation found by D.R. Woodall .

One could also consider the supremum of the real chromatic roots of planar bipartite graphs. Salas and Sokal conjecture that this is $`\tau ^2`$.

###### Conjecture 19

 Let $`G`$ be a planar bipartite graph. Then $`P(G,t)>0`$ for $`t[\tau ^2,\mathrm{})`$.

They constructed families of planar bipartite graphs with chromatic roots tending to $`\tau ^2`$ in .

### 2.6 Graphs of Bounded Degree

Let $`G`$ be a connected graph and $`\mathrm{\Delta }(G)`$ denote the maximum degree of $`G`$. Brooks  has shown that the chromatic number of $`G`$ is at most $`\mathrm{\Delta }(G)+1`$ with equality if and only if $`G`$ is a complete graph or an odd circuit. Brenti, Royle and Wagner  asked whether some form of Brooks’s theorem could be true for the complex chromatic roots of $`G`$. More precisely, they asked whether there exists a real function $`f`$ such that all complex chromatic roots of $`G`$ lie in the disc $`|t|<f(\mathrm{\Delta }(G))`$. (This is, in fact, equivalent to an earlier conjecture for regular graphs due to Biggs, Damerell and Sands .) The conjectures have recently been verified by Sokal  using an exciting new proof technique.

###### Theorem 20

Let $`G`$ be a graph. Then $`|P(G,t)|>0`$ for all complex $`t`$ with $`|t|C\mathrm{\Delta }(G)`$, where $`C7.9639`$.

It is conceivable that Sokal’s theorem is valid for some $`C<2`$, although there are examples which show that we must take $`C>1`$, see \[27, Section 7\], and hence Brooks’s theorem cannot be extended to a disc in the complex plane. It is possible however that the following extension of Brooks’s theorem is valid.

###### Conjecture 21

 Let $`G`$ be a graph. Then $`|P(G,t)|>0`$ for all complex $`t`$ with $`\mathrm{}(t)>\mathrm{\Delta }(G)`$.

A graph $`G`$ is said to be $`𝒅`$-degenerate if every subgraph of $`G`$ has a vertex of degree at most $`d`$. Let $`D(G)`$ denote the minimum value of $`d`$ for which $`G`$ is $`d`$-degenerate. Clearly $`D(G)\mathrm{\Delta }(G)`$. It is well known that $`\chi (G)D(G)+1`$. It is not possible, however, to extend this result on integer chromatic roots to the real line, let alone the complex plane, since Thomassen  has constructed 2-degenerate graphs with arbitrarily large real chromatic roots.

Let $`G`$ and $`H`$ be graphs. We say that $`H`$ is a minor of $`G`$ if $`H`$ can be obtained from $`G`$ by a sequence of edge deletions and contractions. A simple minor of $`G`$ is a minor which contains no loops or multiple edges. If we modify the definition of $`d`$-degenerate by replacing the condition that “every subgraph of $`G`$ has a vertex of degree at most $`d`$” by the condition that “every simple minor of $`G`$ has a vertex of degree at most $`d`$” then Woodall  has shown that we do obtain a bound on the size of the real chromatic roots of $`G`$.

###### Theorem 22

Let $`G`$ be a graph. Suppose that every simple minor of $`G`$ has a vertex of degree at most $`d`$. Then $`P(G,t)>0`$ for all real $`t(d,\mathrm{})`$.

Since every simple planar graph has a vertex of degree at most five, his result implies Theorem 9 for all $`t>5`$. Note that Theorem 22 cannot be extended to a disc in the complex plane since even Theorem 9 does not extend to a disc in the complex plane.

The following conjecture of Sokal, which was inspired by a remark of Shrock and Tsai \[26, p220\], suggests a possible way to extend Theorem 20 to a larger family of graphs. Let $`𝚲\mathbf{(}𝑮\mathbf{)}`$ denote the maximum number of edge-disjoint paths joining any pair of vertices of $`G`$. Thus $`\mathrm{\Lambda }(G)\mathrm{\Delta }(G)`$. Furthermore, it can be seen that $`D(G)\mathrm{\Lambda }(G)`$ and hence $`\chi (G)\mathrm{\Lambda }(G)+1`$, see .

###### Conjecture 23

\[27, Section 7\] There exists a constant $`C`$ such that $`|P(G,t)|>0`$ for all complex $`t`$ with $`|t|C\mathrm{\Lambda }(G)`$.

## 3 Flow Polynomials

Let $`\mathrm{\Gamma }`$ be an additive abelian group and $`G`$ be a graph. Suppose we construct a digraph $`\stackrel{}{G}`$ by giving the edges of $`G`$ an arbitrary orientation. For $`UV(G)`$ and $`\overline{U}=V(G)U`$, let $`E^+(U)`$ be the set of arcs from $`U`$ to $`\overline{U}`$ in $`\stackrel{}{G}`$ and $`E^{}(U)=E^+(\overline{U})`$. Let $`f:E(\stackrel{}{G})\mathrm{\Gamma }`$ and put $`f^+(U)=_{eE^+(U)}f(e)`$ and $`f^{}(U)=_{eE^{}(U)}f(e)`$. For $`vV(G)`$ let $`f^+(v)=f^+(\{v\})`$ and $`f^{}(v)=f^{}(\{v\})`$. Then $`f`$ is a $`𝚪`$-flow for $`G`$, with respect to $`\stackrel{}{G}`$, if $`f^+(v)=f^{}(v)`$ for all $`vV(G)`$. If in addition, $`f(e)0`$ for all $`eE(G)`$, then we say that $`f`$ is a nowhere-zero $`𝚪`$-flow of $`G`$. It can be seen that the condition $`f^+(v)=f^{}(v)`$ for all $`vV(G)`$ is equivalent to the apparently stronger condition that $`f^+(U)=f^{}(U)`$ for all $`UV(G)`$. Thus, if $`G`$ has a nowhere zero $`\mathrm{\Gamma }`$-flow, then $`G`$ is bridgeless. Since reversing the orientation on an edge $`e`$ of $`\stackrel{}{G}`$ is equivalent to replacing $`f(e)`$ by $`f(e)`$, the number of distinct nowhere-zero $`\mathrm{\Gamma }`$-flows for $`G`$ is independent of the chosen orientation $`\stackrel{}{G}`$ of $`G`$.

A nowhere-zero $`t`$-flow of $`G`$ is a nowhere-zero $``$-flow, $`f`$, such that $`|f(e)|t1`$ for all $`eE(G)`$. Tutte  has shown that $`G`$ has a nowhere-zero $`t`$-flow if and only if $`G`$ has a nowhere-zero $`_t`$-flow. Furthermore, the number of distinct nowhere-zero $`\mathrm{\Gamma }`$-flows of $`G`$ is the same for all abelian groups $`\mathrm{\Gamma }`$ of the same order. Note, however, that the number of nowhere-zero $`_t`$-flows of $`G`$ may differ from the number of nowhere-zero $`t`$-flows of $`G`$. Nowhere-zero flows were introduced by Tutte  as a dual concept to proper colourings. He showed that a connected plane graph $`G`$ has a proper $`t`$-colouring if and only if its planar dual $`G^{}`$ has a nowhere-zero $`t`$-flow. The two concepts differ for non-planar graphs, however. Indeed, whereas there exist loopless graphs which are not $`t`$-colourable for arbitrarily large integers $`t`$, the same is not true for bridgeless graphs and nowhere-zero $`t`$-flows.

###### Theorem 24

Let $`G`$ be a bridgeless graph. Then:

1. $`G`$ has a nowhere-zero $`6`$-flow, (Seymour );
2. if $`G`$ has no 3-edge cuts then $`G`$ has a nowhere-zero $`4`$-flow, (Jaeger ).

Tutte conjectures that both of these results can be strengthened.

###### Conjecture 25

Let $`G`$ be a bridgeless graph. Then

1. $`G`$ has a nowhere-zero $`5`$-flow ;
2. if $`G`$ has no 3-edge cuts then $`G`$ has a nowhere-zero $`3`$-flow.

Conjecture 25(b) was stated by Tutte in 1972.

Following Tutte  we define the flow polynomial $`F\mathbf{(}G\mathbf{,}t\mathbf{)}`$ of $`G`$ as the number of distinct nowhere-zero $`_t`$-flows of $`G`$ for any positive integer $`t`$. Thus $`F(G,t)1`$ if $`E(G)=\mathrm{}`$ and $`F(G,t)0`$ if $`G`$ has a bridge. We shall refer to the zeros of $`F(G,t)`$ as flow roots of $`G`$.

By the above remarks, $`F(G,t)`$ is independent of the chosen orientation of $`G`$, and remains the same if we replace $`_t`$ by any other abelian group of order $`t`$. Note also that since the existence of a nowhere-zero $`t`$-flow for $`G`$ implies the existence of a nowhere-zero $`(t+1)`$-flow by definition, and is equivalent to the existence of a nowhere-zero $`_t`$-flow as noted above, we may deduce that if $`F(G,t_0)0`$ for some positive integer $`t_0`$, then $`F(G,t)0`$ for all integers $`tt_0`$.

We could also consider the polynomial $`I(G,t)`$ defined to be the number of distinct nowhere-zero $`t`$-flows of $`G`$. Kochol  gives relationships between $`I(G,t)`$ and $`F(G,t)`$, but these seem to be the only results on $`I(G,t)`$ in the literature. Attention has concentrated on $`F(G,t)`$ because it is dual to $`P(G,t)`$ for plane graphs. Let $`G`$ be a connected plane graph and $`G^{}`$ be is its planar dual. There is a surjection from the $`t`$-vertex-colourings of $`G^{}`$ to the nowhere-zero $`_t`$-flows of $`G`$, such that each nowhere-zero $`_t`$-flow of $`G`$ has exactly $`t`$ pre-images, see . Thus

$$F(G,t)=t^1P(G^{},t).$$

We may use this identity to restate the results and conjectures on chromatic roots of plane graphs in subsections 2.4 and 2.5 in terms of flow roots of plane graphs. In the remainder of this section we shall survey results and conjectures on flow roots of graphs which are not necessarily planar.

We first state some fundamental recurrence relations for flow polynomials.

###### Lemma 26

Let $`G`$ be a graph and $`e`$ be an edge of $`G`$.

1. If $`e`$ is a loop, then $`F(G,t)=(t1)F(Ge,t)`$.
2. If $`e`$ is not a loop, then $`F(G,t)=F(G/e,t)F(Ge,t)`$.

###### Lemma 27

Let $`G`$ be a graph, $`v`$ be a vertex of $`G`$, and $`G_1`$ and $`G_2`$ be edge-disjoint subgraphs of $`G`$ such that $`G_1G_2=G`$ and $`G_1G_2=\{v\}`$. Then

$$F(G,t)=F(G_1,t)F(G_2,t).$$

###### Lemma 28

Let $`G`$ be a 2-connected graph, $`v`$ be a vertex of $`G`$, $`e`$ be an edge of $`G`$, and $`H_1`$ and $`H_2`$ be edge-disjoint subgraphs of $`G`$ such that $`H_1H_2=Ge`$ and $`H_1H_2=\{v\}`$. Let $`G_1`$ be obtained from $`G`$ by contracting $`E(H_2)`$, and define $`G_2`$ analogously. Then

$$F(G,t)=\frac{F(G_1,t)F(G_2,t)}{(t1)}.$$

###### Lemma 29

Let $`G`$ be a graph, $`S`$ be a 3-edge-cut of $`G`$, and $`H_1`$ and $`H_2`$ be the components of $`GS`$. Let $`G_1`$ be obtained from $`G`$ by contracting $`E(H_2)`$, and define $`G_2`$ analogously. Then

$$F(G,t)=\frac{F(G_1,t)F(G_2,t)}{(t1)(t2)}.$$

### 3.1 General Graphs

Wakelin  obtained the following analogue of Theorem 3 for flow roots of graphs.

###### Theorem 30

Let $`G`$ be a bridgeless graph with $`n`$ vertices, $`m`$ edges, $`b`$ blocks, and no isolated vertices. Then:

1. $`F(G,t)`$ is non-zero with sign $`(1)^{mn+1}`$ for $`t(\mathrm{},1)`$;
2. $`F(G,t)`$ has a zero of multiplicity $`b`$ at $`t=1`$;
3. $`F(G,t)`$ is non-zero with sign $`(1)^{mn+b+1}`$ for $`t(1,\frac{32}{27}]`$.

Using planar duality, we can restate Theorems 11 and 13 in terms of flow roots to deduce that there is no obvious way to extend Theorem 30 beyond the real interval $`(\mathrm{},\frac{32}{27}]`$, or into the complex plane.

###### Theorem 31

1. The real flow roots of planar graphs are dense everywhere in $`[\frac{32}{27},3]`$.
2. The complex flow roots of planar graphs are dense everywhere in the complex plane with the possible exception of the disc $`|t1|<1`$.

We can construct 2-connected graphs with real flow roots in $`(1,2)`$ as follows. Let $`G`$ be a 2-connected graph with $`n`$ vertices and $`m`$ edges and suppose that $`mn`$ is odd. It follows from Theorem 30(b),(c) that $`F(G,1)=0`$ and that $`F(G,t)`$ becomes negative when $`t`$ increases from 1. If, in addition, we assume that $`G`$ is Eulerian, then $`F(G,2)=1`$ and hence $`F(G,t)`$ must have a zero in $`(1,2)`$. We may combine these graphs with any other graph using Lemma 28 to construct non-Eulerian 2-connected graphs with flow roots in $`(1,2)`$. It is conceivable, however, that Theorem 30 can be extended if we add the hypothesis that $`G`$ is 3-connected.

###### Conjecture 32

Let $`G`$ be a 3-connected graph with $`n`$ vertices, and $`m`$ edges. Then:

1. $`F(G,t)`$ is non-zero with sign $`(1)^{mn}`$ for $`t(1,\varphi )`$, where $`\varphi 1.749`$ is the flow root of $`K_5`$ in $`(1,2)`$.
2. If $`G`$ is not an Eulerian graph with $`mn`$ odd, then $`F(G,t)`$ is non-zero with sign $`(1)^{mn}`$ for $`t(1,2)`$.

Welsh  has conjectured that the dual form of Conjecture 10 holds for all graphs (with the slight relaxation that 4 is allowed to be a flow root).

###### Conjecture 33

Let $`G`$ be a bridgeless graph. Then $`F(G,t)>0`$ for all real $`t(4,\mathrm{})`$.

It is not even known whether this conjecture is true if 4 is replaced by any large constant $`C`$. Note however that there seems to be no obvious analogue of Conjecture 33 for the complex plane: by applying planar duality to the remark given at the end of subsection 2.4, we may deduce that there exist 3-connected plane cubic graphs with complex flow roots of unbounded modulus, and that there exist 3-connected plane graphs with complex flow roots whose real part is greater than 4.

### 3.2 Cubic Graphs

A graph $`G`$ is cubic if all its vertices have degree three. They have a special significance in the study of flow roots of graphs; for example, we can use Lemma 26 to show that Conjectures 25(a) and 33 are true if and only if they are true for cubic graphs. We shall see below that the flow roots of cubic graphs are much better behaved than those of graphs in general. Note that, using planar duality, we can restate the results and conjectures on chromatic roots of plane triangulations in terms of flow roots of planar cubic graphs. I have recently obtained the following extension of (the dual form of) Theorem 14 to cubic graphs which are not necessarily planar.

###### Theorem 34

 Let $`G`$ be a 3-connected cubic graph with $`n`$ vertices, and $`m`$ edges. Then

1. $`F(G,t)`$ is non-zero with sign $`(1)^{mn}`$ for $`t(1,2)`$;
2. $`F(G,t)`$ has a zero of multiplicity $`1`$ at $`t=2`$;
3. $`F(G,t)`$ is non-zero with sign $`(1)^{mn+1}`$ for $`t(2,\delta )`$, where $`\delta 2.546`$ is the flow root of the cube in $`(2,3)`$.

It seems likely that the non-zero interval given in Theorem 34(c) may be extended beyond $`\delta `$ for cubic graphs of ‘higher connectivity’. We use the following concept to give a measure of ‘4-connectivity’ in cubic graphs. A graph $`G`$ is cyclically $`k`$-connected if, whenever we can express $`G`$ as $`G=G_1G_2`$, where $`E(G_1)E(G_2)=\mathrm{}`$ and $`G_1`$ and $`G_2`$ both contain circuits, we must have $`|V(G_1)V(G_2)|k`$. (Cyclic $`k`$-connectivity is the dual concept to $`k`$-connectivity in plane graphs.) Using this concept we may pose the following strengthenings of Conjectures 15(a) and 16(a).

###### Conjecture 35

Let $`G`$ be a cyclically-4-connected cubic graph. Then $`F(G,t)`$ has at most one zero in $`(2,\tau ^2)`$.

###### Conjecture 36

For all $`ϵ>0`$, there exist only finitely many cyclically-4-connected cubic graphs with a flow root in $`(2,\tau ^2ϵ)`$.

## 4 Characteristic Polynomials of Matroids

The reader may have wondered whether there is a more general framework in which the duality between chromatic and flow polynomials of plane graphs can be extended. Matroids provide us with such a framework. I refer the reader to Oxley  or Welsh  for matroid definitions not explicitly stated in this article.

The characteristic polynomial $`C\mathbf{(}M\mathbf{,}t\mathbf{)}`$ of a matroid $`M=(E,r)`$ is the polynomial in $`t`$ defined by

$$C(M,t)=\underset{AE}{}(1)^{\left|A\right|}t^{r(E)r(A)}.$$

We can define the dual matroid $`M^{}`$ for any matroid $`M`$. We can also associate a pair of dual matroids to every graph $`G`$, the cycle matroid $`M_G`$ and the cocycle matroid $`M_G^{}`$. Then $`C(M_G,t)=t^cP(G,t)`$, where $`c`$ is the number of components of $`G`$, and $`C(M_G^{},t)=F(G,t)`$. Furthermore, when $`G`$ is a connected plane graph with planar dual $`G^{}`$, the cycle matroid of $`G^{}`$ is equal to the cocycle matroid of $`G`$. This gives the above mentioned identity $`F(G,t)=t^1P(G^{},t)`$.

The integer chromatic roots and flow roots of a graph both occur as sequences of consecutive integers. Examples are given in \[39, p254\] to show that this basic property may not hold for the integer zeros of the chracteristic polynomial of a matroid. Nevertheless, some of the above mentioned results on real and complex chromatic roots do extend to matroids. The following result from  gives a common generalization of Theorems 3 and 30.

###### Theorem 37

Let $`M`$ be a loopless matroid with rank $`r`$ and $`b`$ components. Then:

1. $`C(M,t)`$ is non-zero with sign $`(1)^r`$ for $`t(\mathrm{},1)`$;
2. $`C(M,t)`$ has a zero of multiplicity $`b`$ at $`t=1`$;
3. $`C(M,t)`$ is non-zero with sign $`(1)^{r+b}`$ for $`t(1,\frac{32}{27}]`$.

Let $`M`$ and $`N`$ be matroids. We say that $`N`$ is a minor of $`M`$ if $`N`$ can be obtained from $`M`$ by a sequence of deletions and contractions. A simple minor of $`M`$ is a minor which contains no loops or circuits of length two. Oxley  has shown that if every cocircuit of $`M`$ has size at most $`d`$ then $`C(M,t)>0`$ for all real $`t(d,\mathrm{})`$. His proof, which uses induction on $`|E(M)|`$, can be used to prove a stronger inductive statement which extends Theorem 22.

###### Theorem 38

Let $`M`$ be a matroid. Suppose that every simple minor of $`M`$ has a cocircuit of size at most $`d`$. Then $`C(M,t)>0`$ for all real $`t(d,\mathrm{})`$.

Applying this result to the special case of cographic matroids, we obtain:

###### Corollary 39

Let $`G`$ be a bridgeless graph. Suppose that every 3-edge-connected minor of $`G`$ has a circuit of length at most $`d`$. Then $`F(G,t)>0`$ for all real $`t(d,\mathrm{})`$.

Since every 3-connected graph $`G`$ has a circuit of length at most $`2\mathrm{log}_2|V(G)|`$, this gives:

###### Corollary 40

Let $`G`$ be a bridgeless graph on $`n`$ vertices. Then $`F(G,t)>0`$ for all real $`t(2\mathrm{log}_2n,\mathrm{})`$.

It is also possible that Theorem 20 and Conjecture 23 can be extended to binary matroids. Given a binary matroid $`M`$, let $`\mathrm{\Lambda }(M)=\mathrm{min}_B\mathrm{max}_{CB}\{|C|\}`$ where the minimum is taken over all bases $`B`$ of the cocycle space of $`M`$. (It can be seen that if $`M`$ is the cycle matroid of a graph $`G`$ then $`\mathrm{\Lambda }(M)=\mathrm{\Lambda }(G)`$, see .)

###### Conjecture 41

 There exists a constant $`D`$ such that for all loopless binary matroids $`M`$ and all complex numbers $`t`$ with $`|t|D\mathrm{\Lambda }(M)`$, we have $`C(M,t)0`$.

Applying this conjecture when $`M`$ is the cographic matroid of a graph $`G`$ we obtain a conjecture for flow roots of graphs. Let $`\mathrm{\Lambda }^{}(G)=\mathrm{min}_B\mathrm{max}_{CB}\{|C|\}`$, where the minimum is taken over all bases $`B`$ of the cycle space of $`G`$.

###### Conjecture 42

 There exists a constant $`D`$ such that for all bridgeless graphs $`G`$ and all complex numbers $`t`$ with $`|t|D\mathrm{\Lambda }^{}(G)`$, we have $`F(M,t)0`$.

### Acknowledgements

I would like to thank Alan Sokal and Douglas Woodall for many helpful remarks and inspiring conversations on chromatic roots which have greatly contributed to this survey.


format: text

text:
# Convergence of the Gaussian Expansion Method in Dimensionally Reduced Yang-Mills Integrals

## 1 Introduction

It is well appreciated that perturbation theory has a limited range of applicability, although its importance in theoretical physics can never be overstated. First of all, perturbative expansions in most cases yield merely an asymptotic series, which starts to diverge at some finite order. There are also situations in which the expansion parameter is too large to make perturbative calculations reliable or even meaningful.

Superstring theory provides such a situation where nonperturbative effects are considered to be extremely important. From this point of view, the recent proposals for its nonperturbative formulations should be considered as a substantial progress. For instance the IIB matrix model  is conjectured to be a nonperturbative definition of type IIB superstring theory in ten dimensions, and it is speculated to explain the dynamical origin of the Standard Model including the space-time dimensionality, the gauge group and the number of generations. Much effort has been made to understand the dynamics of this model. In particular, Monte Carlo simulations may be as useful as in lattice gauge theories, and indeed various simplified versions of the IIB matrix model have been successfully studied . However, it is not straightforward to extend these studies to the IIB matrix model, where the complex fermion determinant causes the notorious complex-action problem. In fact it is speculated that the phase of the fermion determinant plays a crucial role in the dynamical generation of four-dimensional space-time . Recently a new Monte Carlo technique  is developed to include the effect of the phase. Preliminary results concerning the space-time dimensionality are encouraging, but it remains to be seen whether definite conclusions can be reached along this line. In any case it would be certainly desirable to develop an alternative method which enables a nonperturbative access to the dynamics of the model.

In this Letter, we are going to advocate a method to systematically improve the self-consistent harmonic approximation (or the Gaussian approximation), which has been widely used in condensed matter physics. (See Ref.  and references therein.) Indeed such a method was applied to the IIB matrix model up to the 3rd order in Ref. . This provided the first analytical evidence for the dynamical generation of 4d space-time, which is both surprising and encouraging since the model describes superstrings in 10 dimensions. Stability of this conclusion against higher order corrections has been confirmed recently by explicit 5th order calculations . There the method is also interpreted as an improved Taylor expansion. The Gaussian approximation (the leading order of the Gaussian expansion) has been applied to random matrix models earlier in Ref. . Its application to supersymmetric matrix quantum mechanics (including the Matrix Theory) was advocated by Kabat and Lifschytz , and Refs.  succeeded in revealing interesting blackhole thermodynamics even at the leading order.

Here we apply the method to the bosonic version of the IIB matrix model. More generally we consider the model  obtained from dimensional reduction of SU($`N`$) Yang-Mills theory in $`D`$ dimensions, where the $`D=10`$ case corresponds to the bosonic IIB matrix model. The model can also be regarded as a Hermitian matrix version of the Eguchi-Kawai model , which was proposed as an equivalent description of large-$`N`$ gauge theory. This equivalence in the case of the present model has been investigated recently . Hence we expect that our results would also have some implications to field theoretical applications of the method.

In the present bosonic model, we perform calculations up to the 7th order, which allows us to convincingly demonstrate the convergence of the method. Although the model is much simpler than the IIB matrix model, it is still nontrivial, and in particular it has not been solved exactly so far. Also the conventional perturbative approach cannot be applied as in the IIB matrix model, since the action does not contain a quadratic term. However, standard Monte Carlo simulation is applicable, and there are some results  that can be compared with ours. As another advantage of studying this model, we can perform analytic calculations leaving $`D`$ as a free parameter. We observe that the convergence is fast in particular for large $`D`$. For $`D10`$, for instance, a reasonable convergence is already achieved at the 3rd order, which supports the validity of the aforementioned calculations in the IIB matrix model.

We would like to point out that actually the Gaussian expansion method has a long history , although its application to matrix models is new. Originally it was developed to obtain the energy spectrum in quantum mechanical systems. The most striking aspect of the method is that the results converge, although the expansion is not based on any small parameter 111There are rigorous proofs of convergence in certain examples . Very recently Ref.  has shown that complex solutions to the $`d(\text{result})/d(\text{unphysical parameter})=0`$ equation (in fact, the solution with the largest imaginary part) works extremely well. . It is also interesting that the results contain fully nonperturbative effects, although the actual calculations are nothing but the familar ones in standard perturbation theory. In this approach one typically encounters a situation in which the approximants depend on free parameters. In fact the power of the method comes from the flexibility to adjust these parameters depending on the order of the expansion. Common wisdom suggests to determine them by ‘the principle of minimum sensitivity’ . This is usually achieved by solving the ‘self-consistency equation’. However, we will encounter some problems with this strategy. Here we propose a novel prescription based on histograms, with which one can naturally obtain the ‘best approximation’ at each order without such problems. We hope that our histogram prescription is useful in other applications as well.

## 2 Dimensionally reduced Yang-Mills integrals

The model we study in this work is defined by the partition function

$`Z`$ $`=`$ $`{\displaystyle \text{d}A\text{e}^S},`$ (1)
$`S`$ $`=`$ $`{\displaystyle \frac{1}{4}}N\beta {\displaystyle \underset{\mu ,\nu }{}}\mathrm{tr}[A_\mu ,A_\nu ]^2,`$ (2)
where $`A_\mu `$ ($`\mu =1,\mathrm{},D`$) are $`N\times N`$ Hermitian matrices. The integration measure $`\text{d}A`$ is defined by $`\text{d}A=_{a=1}^{N^21}_{\mu =1}^D\frac{dA_\mu ^a}{\sqrt{2\pi }}`$, where $`A_\mu ^a`$ are the coefficients in the expansion $`A_\mu =_aA_\mu ^aT^a`$ with respect to the SU($`N`$) generators $`T^a`$ normalized as $`\mathrm{tr}(T^aT^b)=\frac{1}{2}\delta ^{ab}`$. The model can be regarded as the zero-volume limit of SU($`N`$) Yang-Mills theory in $`D`$ dimensions. As a result of this limit, we can actually absorb $`\beta `$ in (2) by rescaling $`A_\mu \beta ^{1/4}A_\mu `$. Thus $`\beta `$ is not so much a coupling constant as a scale parameter, which we set to $`\beta =1`$ without loss of generality. The partition function was conjectured  and proved  to be finite for $`N>D/(D2)`$. Note in particular that the model is ill-defined for $`D2`$. A systematic $`1/D`$ expansion was formulated in . In particular the absence of SO($`D`$) breaking was shown to all orders of the $`1/D`$ expansion and this conclusion was also confirmed by Monte Carlo simulations  for various $`D=3,4,6,\mathrm{},20`$. The Gaussian expansion method is also capable of addressing such an issue , but here we assume the absence of the SSB in order to focus on the convergence of the method itself. In Ref.  Polyakov line and Wilson loop were calculated by the (next-)leading Gaussian approximation, and Monte Carlo results  were reproduced qualitatively. An equally successful result was obtained in the supersymmetric case .

## 3 The Gaussian expansion method

The Gaussian action which has both SU($`N`$) and SO($`D`$) symmetries can be written as

$$S_0=\frac{N}{v}\frac{\sqrt{D}}{2}\underset{\mu =1}{\overset{D}{}}\mathrm{tr}\left(A_\mu \right)^2,$$
(3)
where $`v`$ is a positive real parameter. (The constant factor $`\frac{\sqrt{D}}{2}`$ is introduced for convenience.) Then we rewrite the partition function (1) as

$`Z`$ $`=`$ $`Z_0\text{e}^{(SS_0)}_0,`$ (4)
$`Z_0`$ $`=`$ $`{\displaystyle \text{d}A\text{e}^{S_0}},`$ (5)
where $`_0`$ is a VEV with respect to the partition function $`Z_0`$. From (4) it follows that the free energy $`F=\mathrm{ln}Z`$ can be expanded as

$`F`$ $`=`$ $`{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}F_k;F_0\mathrm{ln}Z_0,`$ (6)
$`F_k`$ $``$ $`{\displaystyle \frac{(1)^k}{k!}}(SS_0)^k_{\mathrm{C},0}(\text{for}k1),`$ (7)
where the suffix ‘C’ in $`_{\mathrm{C},0}`$ means that the connected part is taken. Each term $`F_k`$ in the above expansion can be calculated conveniently by using Feynman diagrams. In actual calculations we have to truncate the infinite series (6) at some finite order. In Ref. , Schwinger-Dyson equations were used to reduce the number of diagrams considerably. Using this technique, we were able to proceed up to the 7th order in the present model with reasonable efforts (e.g., we evaluated 21 eight-loop diagrams.).

Once we truncate the expansion (6), the calculated free energy depends on the parameter $`v`$ introduced in the Gaussian action (3). In the large-$`N`$ limit 222This simply amounts to considering only the planar diagrams. Although it reduces our effort considerably, the method itself is applicable to arbitrary finite $`N`$.  we compute the ‘free energy density’ defined by

$$f=\underset{N\mathrm{}}{lim}\left\{\frac{1}{D(N^21)}F\frac{1}{2}\mathrm{ln}\left(\sqrt{\frac{D}{2}}N\right)\right\}.$$
(8)
The second term is subtracted in order to make the quantity finite. (In particular $`f=1/4`$ for $`D=\mathrm{}`$.) In Fig. 1 we plot the result at each order as a function of $`v`$ for $`D=10`$. Formation of a plateau is clearly seen. We may understand this phenomenon as a reflection of the fact that the formal expansion (6), if not truncated, should not depend on $`v`$. According to this interpretation, the height of the plateau observed for the truncated free energy is expected to provide a good approximation. This is the philosophy behind ‘the principle of minimum sensitivity’, which is known in a more general context .

Next we need to specify a prescription to obtain a concrete value which approximates the free energy at each order. In Refs.  the free parameters in the Gaussian action were determined such that the truncated free energy becomes stationary. This amounts to solving the ‘self-consistency equation’

$$\frac{}{v}\left(\underset{k=0}{\overset{n}{}}F_k\right)=0.$$
(9)
In Table 1 we list the number of solutions to the ‘self-consistency equation’ for each $`D`$, which already reveals some problems. For example, for $`D=10`$ we find that the number of solutions increases as we go to higher orders, and we have to decide which one to choose. A similar ambiguity was encountered in the IIB matrix model , where the solution that gives the smallest free energy has been chosen. While this prescription seems reasonable at relatively small orders, we have problems at higher orders, in particular when we are discussing the convergence. In Fig. 2 we zoom up the plateau seen at the order 7 in Fig. 1. We observe some oscillations, whose amplitude becomes larger towards the left edge of the plateau. If we used the prescription described above in the present situation, we would clearly underestimate the height of the plateau. This will be even more problematic at higher orders since the dip at the left edge seems to become deeper as the order increases. It may also happen in general that the truncated free energy acquires a global minimum which has nothing to do with the plateau formation.

From Table 1 one also finds that there are cases where the ‘self-consistency equation’ has no solutions. (This was encountered in the study of the IIB matrix model at the orders 2 and 4 .) For instance there is no solution at the orders 2,4,6 for $`D=4`$. As we show in the Appendix, a well-defined plateau is developing even in this case. The question is how to extract the height of the plateau in such cases.

## 4 The histogram prescription

All these problems arise from trying to determine the free parameters by local information such as ‘self-consistency equations’. In fact it is more natural to extract the height of the plateau directly. As a first step, let us make a histogram of the truncated free energy calculated at points which are uniformly distributed in the parameter space of the Gaussian action. Fig. 3 shows the histogram for $`D=10`$ at order 7. Whenever we make histograms in what follows, the range of $`v`$ is restricted to $`0.01v1.4`$, and the vertical axis is normalized such that the integration gives unity. In Fig. 3 the bin size is chosen to be very small, and as a result we obtain many peaks, each of which corresponds to a solution of the ‘self-consistency equation’ (Actually the highest peak contains the two solutions which lie at the right edge of the plateau in Fig. 2.). Hence we are back in the previous situation, and we cannot reasonably extract the height of the plateau. In order to identify the plateau, we clearly need some kind of coarse graining. Let us note here that the bin size of the histogram represents the precision at which we search for the plateau. Therefore, we increase the bin size gradually until a single peak becomes ‘dominant’. As a criterion of the dominance, we require the highest bin to be more than twice as high as the second highest one. We further require the dominance to persist for larger bin size. The resulting histogram is shown in Fig. 4.

Fig. 5 shows the histograms obtained in this way at each order for $`D=10`$. The peak becomes sharper and sharper as we go to higher order. Thus the histogram serves as a clear indicator of the plateau formation. Moreover, now we can obtain the ‘best approximation’ at each order from the position of the peak, while the bin size (chosen by the above criterion) roughly represents the theoretical uncertainty of the method. In the Appendix, we present a similar analysis for $`D=4`$. In this case the ‘self-consistency equation’ has no solutions at orders 2,4,6 as mentioned above. However, the histogram prescription is as successful as in $`D=10`$.

In Fig. 6, we plot the approximated value of the free energy for various $`D`$ obtained at each order by our histogram prescription. The ‘error bars’ represent a rough estimate for the theoretical uncertainty explained above 333We did not put error bars to the order 1 results. This is because our criterion for the dominance of a single bin is satisfied even for an infinitesimal bin size. Thus at the order 1, the histogram prescription does nothing more than just solving the ‘self-consistency equation’. . (Remark: Unlike usual error bars, they do not represent an estimate for possible discrepancies from the correct value. For the latter, one should also consider the changes of the results as the order is increased.) We observe a clear convergence for each $`D`$. The convergence becomes fast in particular for large $`D`$.

## 5 Observables

Similarly to the free energy (6), the expectation value of an operator $`𝒪`$ is expanded as

$`𝒪`$ $`=`$ $`{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}O_k;O_0𝒪_0,`$ (10)
$`O_k`$ $``$ $`{\displaystyle \frac{(1)^k}{k!}}(SS_0)^k𝒪_{\mathrm{C},0}(\text{for}k1).`$ (11)
As a fundamental object in this model , we consider

$$𝒪=\frac{1}{N}\underset{\mu =1}{\overset{D}{}}\mathrm{tr}\left(A_\mu \right)^2\times \sqrt{\frac{2}{D}}.$$
(12)
The normalization is chosen such that $`𝒪=1`$ for $`D=\mathrm{}`$ in the large-$`N`$ limit . We calculate $`𝒪`$ by the series expansion (10) truncated at some order. In Fig. 7 we plot the result at each order as a function of $`v`$ for $`D=10`$.

In Refs. , the truncated expectation value was evaluated at the same value of $`v`$ as the one used to evaluate the free energy. Note, however, that the region of the parameter $`v`$ where the plateau develops for the expectation value is slightly shifted from the corresponding region for the free energy. It is therefore safer to extract an approximated value for the observable by repeating the same procedure as we did for the free energy.

Fig. 8 shows the results of the histogram prescription at each order. The growth of the peak is clearly observed, which confirms the plateau formation. Fig. 9 summarizes the final results for the observables, where the ‘error bars’ again represent the theoretical uncertainty. Comparison with the Monte Carlo data  confirms that our results do converge to the correct values. For $`D10`$ in particular, the convergence is already achieved at order 3.

It was previously noted that the leading Gaussian approximation becomes ‘exact’ at $`D=\mathrm{}`$ . The precise statement is that if we evaluate the free energy density and the observable (truncated at the 1st order) at the value of $`v`$ which solves the 1st order ‘self-consistency equation’ for the free energy, they agree with the exact results at $`D=\mathrm{}`$. Although this can be naturally understood from the viewpoint of the $`1/D`$ expansion , it looks rather accidental in the present framework. If we evaluate the truncated observable at $`v`$ which solves the ‘self-consistency equation’ for the observable, we obtain 1.08866 instead of 1. Also there is no plateau yet at order 1. Figs. 6 and 9 show that the convergence of the method as it stands is achieved at order 3 (but not yet at order 1) even for $`D=\mathrm{}`$.

In this regard, it should be emphasized that the Gaussian expansion is different from the $`1/D`$ expansion. Each term in the expansions for the free energy density and the observable is of order 1 with respect to $`1/D`$ for generic $`v`$. Still the height of the plateau converges due to nontrivial cancellations among diagrams. Note also that the Gaussian expansion can be applied to the supersymmetric case (including the IIB matrix model), while the $`1/D`$ expansion cannot be formulated there.

## 6 Summary and Discussions

The most important conclusion of our study is that the Gaussian expansion method converges in the dimensionally reduced Yang-Mills integrals. In particular the convergence is achieved already at order 3 for $`D=10`$, which corresponds to the bosonic IIB matrix model. This suggests the particular usefulness of the method in studying the IIB matrix model. In demonstrating the convergence we encountered problems associated with the commonly used prescription based on ‘self-consistency equations’. We solved these problems by extracting the height of the plateau directly using a novel prescription based on histograms.

The histogram prescription is expected to be particularly useful in the case where the parameter space of the Gaussian action becomes multi-dimensional. If there are more than two parameters, it is already difficult to visualize the plateau formation as we did in Figs. 1, 7 and 10. When we study the SSB of SO(10) symmetry in the IIB matrix model, we have to introduce 10 real and 120 complex parameters . Here we will need some kind of important sampling technique like Monte Carlo simulations in order to explore such a huge parameter space. In the previous works  based on ‘self-consistency equations’, there were problems like the ones we saw in this work. At order 2 and 4 there were no solution to the ‘self-consistency equations’, and in the other cases the solution was not unique. We are currently reinvestigating the IIB matrix model by using the histogram prescription with the above extension .

Finally we would like to emphasize that the dimensionally reduced model we studied in this paper is a system of infinitely many degrees of freedom, since we have taken the size of the matrices $`A_\mu `$ to be infinite. In this regard, let us recall that the model has also connections to SU($`N`$) gauge theories in $`D`$-dimensional space time in the large-$`N`$ limit . The dimensional reduction amounts to reducing the base space of the SU($`N`$) gauge theories to a point, but the original space-time degrees of freedom are still somehow encoded in the internal degrees of freedom. This is possible precisely because there are infinitely many internal degrees of freedom after taking the large-$`N`$ limit. From this point of view the convergence of the Gaussian expansion method in the present model is interesting since the examples for which the convergence is shown in the literature have been restricted to simple quantum-mechanical systems. Although higher order calculations in field-theoretical applications would be technically more involved due to the necessity of the renormalization procedure (See, however, Ref. ), we hope that our results open up a new perspective in that direction as well.

###### Acknowledgments.

We would like to thank the authors of Ref.  for stimulating discussions. The work of J.N. is supported in part by Grant-in-Aid for Scientific Research (No. 14740163) from the Ministry of Education, Culture, Sports, Science and Technology.

## Appendix A The situation in $`D=4`$ : plateau without extrema

In this Appendix, we present our results for $`D=4`$. As we see from Fig. 10, a well-defined plateau is clearly developing. However, if we zoom up the curves for order 2,4,6 (Fig. 11), we find that there are no extrema, in agreement with the absence of solutions to the ‘self-consistency equation’ (See Table 1). We will see that the histogram prescription works even in this case.

Figs. 12 and 13 show the histograms at order 6 before and after ‘coarse-graining’. As we increase the bin size gradually, a single bin becomes dominant (See Section 4 for the precise criterion.). Thus the histogram prescription allows us to obtain explicit results at each order including orders 2,4,6, where the ‘self-consistency equation’ has no solutions. Fig. 14 shows the results at orders $`1,\mathrm{},7`$. The growth of the peak is clearly observed, which confirms the plateau formation. Moreover, the results obtained in this way show a clear convergence as we have seen in Fig. 6.


text:
# Complexity of triangulations of the projective space

## 1 Introduction

By the “Hauptvermutung”, that was proven by Moise , any two triangulations $`𝒯_1`$ and $`𝒯_2`$ of a compact $`3`$–manifold $`M`$ have a common subdivision. This allows to show that $`𝒯_1`$ and $`𝒯_2`$ are related by finite sequences of certain local transformations of triangulations, e.g., stellar subdivisions  or elementary shellings . These results do not provide explicit constructions of transformation sequences and do not yield a recognition algorithm for $`M`$. In this paper, we construct transformation sequences for triangulations of the $`3`$–dimensional projective space $`^3`$. We consider the following local transformations, that generalise stellar subdivisions.

###### Definition 1

Let $`𝒯`$ and $`\stackrel{~}{𝒯}`$ be PL–triangulations of a closed PL–manifold, and let $`e`$ be an edge of $`𝒯`$ with $`e=\{a,b\}`$. Suppose that $`\stackrel{~}{𝒯}`$ is obtained from $`𝒯`$ by removing the open star of $`e`$ and identifying $`a\sigma `$ with $`b\sigma `$ for any simplex $`\sigma `$ in the link of $`e`$. Then $`\stackrel{~}{𝒯}`$ is the result of the edge contraction of $`𝒯`$ along $`e`$, and $`𝒯`$ is the result an edge expansion of $`\stackrel{~}{𝒯}`$ along $`e`$.

In general, there are edges of $`𝒯`$ along which a contraction is impossible. This is the case, e.g., if the edge is part of an edge path of length 3 that does not bound a 2–simplex of $`𝒯`$. It is easy to see that any PL–triangulation admits only a finite number of edge expansions.

Let $`d(𝒯_1,𝒯_2)`$ be the length of a shortest sequence of edge contractions and expansions relating two triangulations $`𝒯_1`$ and $`𝒯_2`$ of a closed $`3`$–manifold $`M`$. The aim of this paper is to provide an upper bound for $`d(𝒯_1,𝒯_2)`$ when $`M`$ is homeomorphic to $`^3`$, as stated in Theorem 1 below. The proof is partially based on our work on the $`3`$–sphere (see ). This paper is thought of as a first step towards a study of more general $`3`$–dimensional manifolds, e.g., (atoroidal) Haken manifolds. A generalisation to *all* compact $`3`$–manifolds, which would solve the algorithmic classification problem for compact $`3`$–manifolds, is out of reach, as yet.

###### Theorem 1

Any two triangulations of $`^3`$ with at most $`t`$ tetrahedra are related by a sequence of less than $`2^{27000t^2}`$ edge contractions and expansions.

The constant factor in the exponent is certainly not optimal. According to the examples in , concerning the minimal number of edge expansions needed to transform a triangulation of $`S^3`$ into a *polytopal* triangulation, we believe that the bound in Theorem 1 can not be replaced by a subexponential bound.

We outline the proof of Theorem 1. It is based on Haken’s normal surface theory, Barnette’s work  on irreducible triangulations of the projective plane, and our techniques in  and . Let $`𝒯_1`$ be a triangulation of $`^3`$. By means of normal surface theory, we construct a certain projective plane $`P^3`$. The complement of a regular neighbourhood of $`P`$ is a ball. This allows to apply techniques of  and , yielding a sequence of edge contractions and expansions relating $`𝒯_1`$ with a triangulation $`𝒯_P`$ that depends on the choice of $`P`$. The next step is to simplify $`𝒯_P`$ by a certain series of edge contractions. In that way we transform $`𝒯_1`$ via $`𝒯_P`$ into one of two *standard triangulations* of $`^3`$, corresponding to the two irreducible triangulations of the projective plane found by Barnette . In the last step in the proof of Theorem 1, we relate the two standard triangulations of $`^3`$ by an explicit sequence of edge contractions and expansions. In conclusion, we construct transformation sequences that relate any two triangulations of $`^3`$ via the two standard triangulations. The bound stated in Theorem 1 follows from a complexity analysis of the construction.

The paper is organised as follows. In Section 2.1, we briefly outline the results of normal surface theory used in our proofs. Section 2.2 recalls a lemma from  on the construction of sequences of edge contractions. We prove the existence of $`P`$ in Section 3.1. Section 3.2 is devoted to the transformation into $`𝒯_P`$, along the lines of . Section 3.3 is concerned with the transformation into one of the two standard triangulations. A transformation sequence relating the two standard triangulations is finally given in Section 3.4.

## 2 Prerequisites

In this section, we collect some results used in the proof of Theorem 1. We denote the number of connected components of a topological space $`X`$ by $`\mathrm{\#}(X)`$. For a tame subset $`YX`$, we denote an open regular neighbourhood of $`Y`$ in $`X`$ by $`U(Y)`$.

### 2.1 Normal surfaces

Let $`M`$ be a closed 3–manifold with a cellular decomposition $`𝒵`$, so that the closure of any open cell of $`𝒵`$ is homeomorphic to a closed ball. Its $`k`$–skeleton is denoted by $`𝒵^k`$. In our applications, $`𝒵`$ is a triangulation or is dual to a triangulation. A normal isotopy with respect to $`𝒵`$ is an ambient isotopy of $`M`$ that fixes each cell of $`𝒵`$ set-wise.

###### Definition 2

Let $`c`$ be a closed $`2`$–cell of $`𝒵`$ and let $`\gamma c`$ be a closed embedded arc with $`\gamma c=\gamma `$, disjoint from the vertices of $`c`$. If $`\gamma `$ connects two different edges in the boundary of $`c`$ then $`\gamma `$ is a normal arc. Otherwise it is a return.

###### Definition 3

Let $`SM`$ be a closed embedded surface transversal to $`𝒵`$. We call $`S`$ normal with respect to $`𝒵`$, if $`S𝒵^2`$ is a union of normal arcs, $`S𝒵^2`$ is a disjoint union of discs, and the boundary of any connected component of $`S𝒵^2`$ meets any edge of $`𝒵`$ at most once.

When it is clear from the context, we do not specify with respect to which cellular decomposition a surface is normal. In the rest of this section, we focus on normal surfaces with respect to a triangulation $`𝒯`$ of $`M`$. It is well known that normal surfaces in a triangulated $`3`$–manifold are built from copies of so-called *normal triangles* and *normal squares* (see Figure 1).

###### Theorem 2

Let $`𝒯`$ be a triangulation of $`M`$ with $`n`$ tetrahedra. Let $`SM`$ be a normal surface comprising more than $`10n`$ two-sided connected components. Then two connected components of $`S`$ are normally isotopic.

This result is originally due to Kneser and proven, e.g., in Lemma 4 of . We use this result to show that certain iterative constructions of normal surfaces stop after a finite number of steps.

Under a technical condition (see  for details), one can define the *sum* $`S_1+S_2`$ of two normal surfaces $`S_1,S_2M`$. The sum is a normal surface and is determined up to normal isotopy by the condition $`(S_1+S_2)𝒯^1=(S_1S_2)𝒯^1`$. The Euler characteristic is additive, $`\chi (S_1+S_2)=\chi (S_1)+\chi (S_2)`$. Haken has shown that with this notion of a sum, the set of normal surfaces in $`M`$ with respect to $`𝒯`$ is isomorphic to a subgroupoid of the semi group $`G`$ of integer points in a rational convex cone, the so-called Haken cone. The semi group $`G`$ is additively generated by a finite set of elements, that can be constructed by means of integer programming. The set of normal surfaces is finitely generated as well, by the following result. For an embedded surface $`SM`$ that is in general position with respect to $`𝒯`$, denote $`S=\mathrm{\#}(S𝒯^1)`$.

###### Theorem 3

Let $`NMU(𝒯^0)`$ be a sub–$`3`$–manifold whose boundary is a normal surface. There is a system $`F_1,\mathrm{},F_qN`$ of normal surfaces such that

$$F_i<N2^{18n}$$

for $`i=1,\mathrm{},q`$, and any normal surface $`FN`$ can be expressed as a sum $`F=_{i=1}^qk_iF_i`$ with non-negative integers $`k_1,\mathrm{},k_q`$.

The surfaces $`F_1,\mathrm{},F_q`$ are called fundamental surfaces in $`N`$. The preceding theorem is Theorem 3 of , that is formulated in a slightly more general setting, namely for so-called $`2`$–normal surfaces. One can prove slightly better bounds in our special situation, but this concerns only the constant $`18`$. Actually it follows from  that the bound in Theorem 3 can not be replaced by a subexponential bound. In the case $`N=MU(𝒯^0)`$, the existence and constructibility of fundamental surfaces is classical in Haken theory , and bounds for $`F_i`$ were obtained in .

### 2.2 Edge contractions

We recall in this subsection a lemma yielding sequences of edge contractions and expansions. Let $`M`$ be a closed $`3`$–manifold. A cellular decomposition of $`M`$ is simple, if any vertex is adjacent to exactly four edges, and any edge is adjacent to exactly three $`2`$–cells (counted with multiplicity). A cellular decomposition is regular if the closure of any open $`k`$–cell is homeomorphic to a $`k`$–ball ($`k=1,\mathrm{},3`$.

Let $`𝒞_1`$ be a simple regular cellular decomposition. In general, $`𝒞_1`$ is not dual to a triangulation, as multiple edges might occur. However, the barycentric subdivision $`𝒞_1^{}`$ of $`𝒞_1`$ is a triangulation of $`M`$. By the next lemma, that is proven in , the deletion of an appropriate $`2`$–cell of $`𝒞_1`$ gives rise to a sequence of contractions of $`𝒞_1^{}`$.

###### Lemma 1

Let $`𝒞_1,𝒞_2`$ be two simple regular cellular decompositions of $`M`$, so that $`𝒞_1^2𝒞_2^2`$ is an open $`2`$–cell of $`𝒞_1`$ with $`k`$ vertices in its boundary. Then $`𝒞_2^{}`$ is obtained from $`𝒞_1^{}`$ by a series of $`4k+2`$ contractions.

## 3 Transforming triangulations

The four parts of this section form the proof of Theorem 1, as outlined in the introduction. We fix the following notations. Let $`𝒞`$ be a cellular decomposition of $`^3`$ that is dual to a triangulation, and let $`𝒯`$ be its barycentric subdivision. Let $`n`$ be the number of tetrahedra of $`𝒯`$. We consider $`𝒞^2`$ as a subset of $`𝒯^2`$.

### 3.1 Fundamental projective plane

It is well known (see ) that there is a fundamental projective plane with respect to $`𝒯`$. We prove here that we can choose it so that additionally it is normal with respect to $`𝒞`$. This technical condition is needed to make the techniques of  work (see next subsection).

###### Lemma 2

Among the fundamental surfaces with respect to $`𝒯`$ in $`^3U(𝒯^0)`$, there is a projective plane $`P`$ that is normal with respect to $`𝒞`$.

Proof Choose an embedded projective plane $`P^3`$ so that the triple

$$(\mathrm{\#}(P𝒞^1),\mathrm{\#}(P𝒯^1),\mathrm{\#}(P𝒯^2))$$

is minimal in lexicographic order. We first prove that $`P`$ is normal with respect to $`𝒯`$ and $`𝒞`$, by a modification of standard techniques (compare ). Since $`\mathrm{\#}(P𝒞^1)`$ is minimal, $`P𝒞^2`$ contains no returns. Removing a return in $`P𝒯^2`$ does not increase $`\mathrm{\#}(P𝒞^1)`$, thus there is no return in $`P𝒯^2`$ by minimality of $`\mathrm{\#}(P𝒯^1)`$. The minimality of $`\mathrm{\#}(P𝒯^2)`$ excludes circles in $`(P𝒯^2)𝒯^1`$, since cutting-and-pasting along such a circle does not increase $`\mathrm{\#}(P𝒞^1)`$ and $`\mathrm{\#}(P𝒯^1)`$.

Assume that there is a circle $`\gamma `$ in $`(P𝒞^2)𝒞^1`$, contained in a $`2`$–cell $`c`$ of $`𝒞`$. By the preceding paragraph, we know that $`\gamma `$ is a union of normal arcs with respect to $`𝒯`$, and $`\gamma `$ bounds a disc in $`c`$ containing a vertex of $`𝒯`$ (the barycenter of $`c`$). Therefore $`\mathrm{\#}(\gamma 𝒯^1)6`$. Let $`Dc`$ be the disc bounded by $`\gamma `$. Since $`P`$ is incompressible in $`^3`$, there is a disc $`D^{}P`$ bounded by $`\gamma `$. We replace $`D^{}`$ by a parallel copy $`D^{\prime \prime }`$ of $`D`$ with $`D^{\prime \prime }D^{}=\mathrm{}`$. We can choose $`D^{\prime \prime }`$ so that $`\mathrm{\#}(D^{\prime \prime }𝒯^1)=1`$, namely intersecting an edge of $`𝒯`$ that connects the barycenter of $`c`$ with the barycenter of a $`3`$–cell of $`𝒞`$. Hence, the cut-and-paste operation replacing $`D^{}`$ by $`D^{\prime \prime }`$ decreases $`\mathrm{\#}(P𝒯^1)`$ by at least $`5`$, without increasing $`\mathrm{\#}(P𝒞^1)`$. So by minimality of $`\mathrm{\#}(P𝒯^1)`$, there is no circle in $`(P𝒞^2)𝒞^1`$.

By the preceding paragraph, any boundary component of a connected component of $`P𝒞^2`$ meets $`𝒞^1`$. Thus the connected component of $`P𝒞^2`$ are discs, since otherwise one can decrease $`\mathrm{\#}(P𝒞^1)`$ by a cut-and-paste operation. If the boundary of a connected component $`P𝒞^2`$ intersects some edge of $`𝒞`$ at least twice, then there is a closed embedded disc $`D^3`$ so that $`D𝒞^2=D𝒞^1`$ is an arc contained in the interior of an edge of $`𝒞`$, $`DPD`$, and $`DP𝒞^1`$. Sliding $`P`$ across $`D`$ decreases $`\mathrm{\#}(P𝒞^1)`$. The corresponding operations, applied to connected components of $`P𝒯^2`$, decreases $`\mathrm{\#}(P𝒯^1)`$ without increasing $`\mathrm{\#}(P𝒞^1)`$. In conclusion, the minimality of $`(\mathrm{\#}(P𝒞^1),\mathrm{\#}(P𝒯^1),\mathrm{\#}(P𝒯^2))`$ implies that the boundary of any connected component of $`P𝒞^2`$ (resp. $`P𝒯^2`$) meets any edge of $`𝒞`$ (resp. of $`𝒯`$) at most once. Hence $`P`$ is normal both with respect to $`𝒯`$ and to $`𝒞`$.

We represent $`P`$ as a sum $`F_1+\mathrm{}+F_k`$ of fundamental surfaces with respect to $`𝒯`$. We can assume that none of $`F_1,\mathrm{},F_k`$ is a $`2`$–sphere (see ). Since the Euler characteristic is additive under the addition of normal surfaces, one summand (say, $`F_1`$) has positive Euler characteristic, thus, is a projective plane. Since $`𝒞^1𝒯^1`$, we have $`\mathrm{\#}(F_1𝒞^1)\mathrm{\#}(P𝒞^1)`$ and $`\mathrm{\#}(F_1𝒯^1)\mathrm{\#}(P𝒯^1)`$, and $`\mathrm{\#}(F_1𝒯^2)\mathrm{\#}(P𝒯^2)=1`$, since $`P`$ and $`F_1`$ are connected normal surfaces. Thus, the choice of $`P`$ implies $`P=F_1`$, i.e., $`P`$ is fundamental with respect to $`𝒯`$ in $`^3U(𝒯^0)`$.

### 3.2 Transformation into $`𝒯_P`$

For any projective plane $`P`$ as in Lemma 2, we define a $`2`$–dimensional polyhedron

$$Q_P=\left(𝒞^2U(P)\right)U(P).$$

Since $`P`$ is normal with respect to $`𝒞`$ and $`^3U(P)`$ is a ball, $`Q_P`$ is the $`2`$–skeleton of a simple cellular decomposition of $`^3`$, which we denote by $`𝒞_P`$. Any $`2`$–cell of $`𝒞_P`$ is contained in the boundary of two different $`3`$–cells. Thus $`𝒞_P`$ is regular, and the barycentric subdivision $`𝒯_P=𝒞_P^{}`$ of $`𝒞_P`$ is a triangulation of $`^3`$. The aim of this subsection is to relate $`𝒯`$ with $`𝒯_P`$ by a sequence of edge contractions and expansions.

We outline the construction of the transformation sequence. All ingredients are taken from , it is only needed to adapt it to the present situation. Since $`B=^3U(P)`$ is a ball, there is an embedding $`H:S^2\times [0,1]B`$ so that $`H(S^2\times 0)=U(x)`$ for some vertex $`x𝒞^0𝒯^0`$, and $`H(S^2\times 1)=B=U(P)`$. Let $`c(H,𝒯^i)`$ (resp. $`c(H,𝒞^i)`$) be the number of parameters $`\xi [0,1]`$ for which the surface $`H_\xi =H(S^2\times \xi )`$ is not in general position to $`𝒯^i`$ (resp. $`𝒞^i`$), for $`i=1,2`$. We assume that $`c(H,𝒯^1)`$ is minimal. An analysis of the Rubinstein–Thompson algorithm as in  yields an upper bound for $`c(H,𝒞^1)`$ in terms of the number $`n`$ of tetrahedra of $`𝒯`$. Techniques from  allow to bound $`c(H,𝒞^2)`$ as well. To any surface $`H_\xi `$ that is in general position to $`𝒞^2`$, we define an embedded $`2`$–complex $`Q_\xi ^3`$ that is the $`2`$–skeleton of a simple regular cellular decomposition of $`^3`$, and $`Q_1=Q_P`$. If $`H_{\xi _0}`$ is not transversal to $`𝒞^2`$ for some $`\xi _0[0,1]`$ and $`ϵ>0`$ is sufficiently small, the complex $`Q_{\xi _0ϵ}`$ is related to $`Q_{\xi _0+ϵ}`$ by isotopy and a bounded number of deletions and insertions of $`2`$–cells. An application of Lemma 1 yields a transformation of $`𝒯`$ into $`𝒯_P`$ by a bounded number of edge contractions and expansions.

In the following lemma, “normal” shall mean “normal with respect to $`𝒯`$”. The estimate for $`c(H,𝒯^1)`$ is based on the construction of a so-called maximal normal sphere system. This is a system $`\mathrm{\Sigma }^3`$ of disjoint normal $`2`$–spheres that are pairwise not normally isotopic, so that any normal $`2`$–sphere in $`^3\mathrm{\Sigma }`$ is normally isotopic to a connected component of $`\mathrm{\Sigma }`$.

###### Lemma 3

There is a maximal normal sphere system $`\mathrm{\Sigma }^3U(P)`$ with at most $`10n`$ connected components and $`\mathrm{\Sigma }<2^{181n^2}`$.

Proof We construct $`\mathrm{\Sigma }`$ iteratively. Define $`\mathrm{\Sigma }_1=U(P𝒯^0)`$. Since $`U(𝒯^0)`$ meets each edge of $`𝒯`$ exactly twice and $`𝒯`$ has at most $`2n`$ edges, we have $`U(𝒯^0)4n`$. The projective plane $`P`$ is fundamental in $`^3U(𝒯^0)`$. Thus, by Theorem 3 and since $`n24`$, we have

$$\mathrm{\Sigma }_1<4n+4n2^{18n}<2^{19n}.$$

For $`i1`$, suppose that there is a connected component $`N_i`$ of $`^3U(\mathrm{\Sigma }_i)`$ and a normal $`2`$–sphere $`SN_i`$ that is not normally isotopic to a connected component of $`\mathrm{\Sigma }_i`$. It follows that $`N_i`$ is not a regular neighbourhood of $`P`$ or of a vertex of $`𝒯`$. We choose $`S`$ so that $`S`$ is minimal.

Assume that $`S`$ can be represented as a sum $`S_1+S_2`$ of non-empty normal surfaces in $`N_i`$. Since the Euler characteristic is additive and since there is no embedded projective plane in the $`3`$–ball $`B=^3U(P)`$, one of the summands, say $`S_1`$, is a sphere. It is not normally isotopic to a component of $`\mathrm{\Sigma }_i`$, since otherwise $`S_1+S_2`$ would be the disjoint union of $`S_1`$ and $`S_2`$, thus would not be a sphere. We obtain a contradiction to the choice of $`S`$, since $`S_1<S`$. Thus $`S`$ is fundamental in $`N_i`$.

We define $`\mathrm{\Sigma }_{i+1}=\mathrm{\Sigma }_iS`$. By Theorem 3 and since $`N_i\mathrm{\Sigma }_i`$, we have $`\mathrm{\Sigma }_{i+1}\mathrm{\Sigma }_i+\mathrm{\Sigma }_i2^{18n}`$. The iteration stops after at most $`10n`$ steps, by Theorem 2. Thus, we end with a maximal system $`\mathrm{\Sigma }`$ of normal $`2`$–spheres with

$$\mathrm{\Sigma }<\mathrm{\Sigma }_1(2^{18n})^{10n1}<2^{181n^2}$$

and at most $`10n`$ connected components.

###### Lemma 4

One can transform $`𝒯`$ into $`𝒯_P`$ by a sequence of less than $`2^{184n^2}`$ edge contractions and expansions.

Proof This lemma is a variant of Theorem 3 in . We give here an outline of the proof, all details can be found in  and . As in Lemma 34 of , there is an embedding $`H:S^2\times [0,1]^3U(P)`$ in general position to $`𝒯^1`$ so that $`H(S^2\times 0)=U(x)`$ for some $`x𝒞^0𝒯^0`$, $`H(S^2\times 1)=2P`$, and $`c(H,𝒯^1)<\mathrm{\#}(\mathrm{\Sigma })\mathrm{\Sigma }2^{18n}`$. Since $`𝒞^1𝒯^1`$, by Lemma 3, and since $`n24`$, it follows

$`c(H,𝒞^1)`$ $`<`$ $`c(H,𝒯^1)<\mathrm{\#}(\mathrm{\Sigma })\mathrm{\Sigma }2^{18n}`$
$`<`$ $`(10n)2^{181n^2+18n}<\mathrm{\hspace{0.33em}2}^{182n^2}.`$
We denote $`H_\xi =H(S^2\times \{\xi \})`$ for $`\xi [0,1]`$. By the choice of $`P`$ in Lemma 2, both $`H_1=2P`$ and $`H_0=U(x)`$ are normal with respect to $`𝒞`$. In particular, for any $`3`$–cell $`X`$ of $`𝒞`$, any connected component of $`H_0X`$ (resp. of $`H_1X`$) bounds a disc in $`H_0X`$ (resp. in $`H_1X`$). Therefore $`H`$ satisfies the technical assumptions in Subsection 3.1 of . Hence by Lemmas 9 and 10 of , we can choose $`H`$ so that

$`c(H,𝒞^2)`$ $``$ $`1+\chi \left(𝒞^2U(P)\right)\underset{<10n}{\underset{}{\chi (𝒞^2)+\chi (𝒞^0)}}+c(H,𝒞^1)`$
$`<`$ $`1{\displaystyle \frac{1}{2}}\mathrm{\#}(P𝒞^1)+10n+2^{182n^2}`$
$`<`$ $`2^{183n^2}.`$
For $`\xi [0,1]`$, let $`B^+(\xi )`$ be the connected component of $`^3H_\xi `$ that contains $`P`$. We define

$$Q_\xi =H_\xi (𝒞^2B^+(\xi )).$$

If $`H_\xi `$ is in general position to $`𝒞^2`$ then, by Lemma 13 in , $`Q_\xi `$ is the $`2`$–skeleton of a simple regular cellular decomposition of $`^3`$, whose barycentric subdivision is a triangulation $`𝒯_\xi `$. Let $`\xi _0[0,1]`$ so that $`H_{\xi _0}`$ is not in general position with respect to $`𝒞^2`$, and let $`ϵ>0`$ be sufficiently small. It is shown after Lemma 13 in  how one can transform $`Q_{\xi _0ϵ}`$ into $`Q_{\xi _0+ϵ}`$. In the first step, depending on the type of non-transversality of $`H_{\xi _0}`$, one adds two $`2`$–cells to $`Q_{\xi _0ϵ}`$ with $`2`$ vertices in the boundary, or one adds one $`2`$–cell with at most $`5`$ vertices, or one deletes from $`Q_{\xi _0ϵ}`$ a $`2`$–cell with $`3`$ vertices. In the second step, one deletes a $`2`$–cell with at most $`4`$ vertices. By an application of Lemma 1, it follows that $`𝒯_{\xi _0ϵ}`$ can be transformed into $`𝒯_{\xi _0+ϵ}`$ be a sequence of at most $`22+18`$ edge expansions or contractions.

The complex $`Q_0`$ is obtained from $`𝒞^2`$ by insertion of a triangular $`2`$–cell. Hence one can transform $`𝒯=𝒞^{}`$ into $`𝒯_0`$ by $`14`$ edge expansion. Furthermore, we have $`𝒯_1=𝒯_P`$. In conclusion, we obtain a sequence of less than

$$14+(22+18)c(H,𝒞^2)<2^{184n^2}$$

contractions and expansions relating $`𝒯`$ with $`𝒯_P`$.

### 3.3 Standard triangulations

Let $`P`$, $`𝒞_P`$ and $`𝒯_P`$ be as in the preceding subsection. Let $`𝒵`$ be a simple cellular decomposition of $`P`$ that is dual to a triangulation. We lift it along the fibres of the $`I`$–bundle $`\overline{U(P)}`$ over $`P`$, and obtain a simple cellular decomposition of $`\overline{U(P)}`$, so that each $`d`$–cell in $`U(P)`$ corresponds to a $`d`$–cell of $`𝒵`$, and the intersection of a $`d`$–cell in $`U(P)`$ with $`P`$ is a $`(d1)`$–cell of $`𝒵`$, for $`d=1,\mathrm{},3`$. Since $`^3U(P)`$ is a ball, we obtain a simple cellular decomposition of $`^3`$. It is easy to see that its barycentric decomposition is a triangulation. We denote this triangulation by $`𝒯(𝒵)`$.

If there is an edge $`e`$ in $`𝒵^1`$ so that $`𝒵^1e`$ is the $`1`$–skeleton of a cellular decomposition of $`P`$ that is dual to a triangulation, then we replace $`𝒵`$ by this simpler cellular decomposition.

We iterate this process until it stops at a simple cellular decomposition $`\widehat{𝒵}`$. It was proven by Barnette  that $`\widehat{𝒵}`$ is one of the two decompositions $`𝒵_1,𝒵_2`$ depicted in Figure 2 (opposite points in the boundary of the discs are identified to obtain the projective plane $`P`$).

###### Lemma 5

The triangulation $`𝒯_P`$ is related to one of the two standard triangulations $`𝒯(𝒵_1)`$ and $`𝒯(𝒵_2)`$ by a sequence of less than $`2^{20n}`$ edge contractions.

Proof Let $`𝒵`$ be the simple cellular decomposition of $`P`$ induced by $`𝒞`$. We have $`𝒯(𝒵)=𝒯_P`$. The deletion of edges of $`𝒵`$ corresponds to the deletion of $`2`$–cells of $`𝒞_P`$. Each of these $`2`$–cells has four vertices in its boundary. Hence the deletion of one edge gives rise to $`18`$ edge contractions of $`𝒯_P`$, by Lemma 1. Since $`𝒵`$ has $`\frac{3}{2}\mathrm{\#}(P𝒞^1)\frac{3}{2}P<2^{19n}`$ edges, $`𝒯_P`$ is related to $`𝒯(\widehat{𝒵})`$ by a sequence of less then $`182^{19n}<2^{20n}`$ edge contractions.

### 3.4 Proof of Theorem 1

Let $`𝒯_1`$ and $`𝒯_2`$ be two triangulations of $`^3`$ with at most $`t`$ tetrahedra. They are related to its barycentric subdivision $`𝒯_1^{}`$, $`𝒯_2^{}`$ by a sequence of at most $`5t`$ edge expansions. Since $`𝒯_1^{}`$ and $`𝒯_2^{}`$ have at most $`12t`$ tetrahedra, it follows from Lemmas 4 and 5 that $`𝒯_1^{}`$ and $`𝒯_2^{}`$ are related to one of the standard triangulations $`𝒯(𝒵_1)`$ and $`𝒯(𝒵_2)`$ by sequences of less than

$$2^{184(12t)^2}+2^{2012t}<2^{26500t^2}$$

edge expansions and contractions.

Figure 3 shows a transformation of $`𝒵_1`$ into $`𝒵_2`$. One adds to $`𝒵_1`$ four edges (the fat edges in the left part of Figure 3) and deletes three edges of the resulting cellular decomposition (the dotted edges in Figure 3). This corresponds to deletions and insertions of $`2`$–cells with four vertices in the associated simple cellular decompositions of $`^3`$. Thus by Lemma 1, $`𝒯(𝒵_1)`$ is related with $`𝒯(𝒵_2)`$ by a sequence of $`718=126`$ edge expansions and contractions.

In conclusion, one can transform $`𝒯_1`$ into $`𝒯_2`$ by a sequence of less than $`126+10t+22^{26500t^2}<2^{27000t^2}`$ edge expansions and contractions, which proves Theorem 1.


text:
# A Distant Stellar Companion in the 𝜐 Andromedae System

## 1. Introduction

Over the last several years, extrasolar planets have been discovered through precision Doppler velocity surveys (c.f. Marcy & Butler 2000). Butler et al (1999) reported the first evidence for a multiple planetary system around the F8V star $`\upsilon `$ Andromedae. Though the combined M sin$`i`$ values for these three planets implied a mass at least 5 times more than the combined mass of the planets in our own solar system, this discovery was heralded as the first evidence that our own system of planets is not unique. Currently, there are seven systems of multiple planets known, and all are around apparent single stars like our own Sun.

During the course of our standardized search for wide companions to stars within 25 pc of the Sun, we discovered a stellar companion to $`\upsilon `$ Andromedae ($`=`$HD9826:Gl 61; 01:36:47.98 $`+`$41:24:23.0,V$`=`$4.10, d$`=`$13.5pc) at an apparent projected separation of $``$750AU. In this paper we present astrometry and spectroscopy to confirm its companionship and discuss the possible influence this secondary might have on the planetary system.

## 2. Observations

### 2.1. Discovery

Finding companions at wide separations ($`>`$ few hundred AU) involves searching large pieces of the sky around the nearest stars. The Two Micron All Sky Survey (2MASS; Skrutskie et al. 1997) is currently presenting a wealth of new material with which previously unknown low-luminosity companions can be found at wide separations. We are in the middle of a 2MASS-based survey around all stars within the Third Catalogue of Nearby Stars (CNS3; Gliese & Jahreiss 1991) for possible companions out to separations of 0.1 pc. The CNS3 includes some 3800 stars believed to lie within 25 pc of the Sun. Companions that are M, L and T dwarfs will have red optical-to-near-IR colors (R-J). Optical photometry from the USNO-A catalog, which is paired up with 2MASS data during routine 2MASS data processing, can be used for an appropriate color constraint. Our candidates are 2MASS detections within a search radius equivalent to a physical separation of 0.1 pc around the nearby star that either have no optical counterparts or have very red $`RJ`$ colors. Confirmation of companionship and classification are then found by astrometric and spectroscopic follow-up, respectively. Several stellar and substellar companions to nearby, main sequence stars have been found in this manner (Kirkpatrick et al 2001a,2001b; Wilson et al 2001; Gizis, Kirkpatrick & Wilson 2001), and the search has been standardized around all nearby stars to provide more robust statistics on the frequency of brown dwarf companions to stars.

During our search, we uncovered a candidate in proximity to the bright, nearby F8V star $`\upsilon `$ And. The candidate companion, 2MASSI J0136504$`+`$412332, has infrared flux and colors (J$`=`$9.39$`\pm `$0.03; J$``$K$`=`$0.88) consistent with a mid M dwarf (Kirkpatrick & McCarthy 1994) at the distance of $`\upsilon `$ And. As shown in Figure 1, it lies 55$`\mathrm{}`$ from $`\upsilon `$ And at a position angle of 147.

### 2.2. Astrometric Confirmation

The Hipparcos mission (Perryman et al 1997) measured $`\upsilon `$ And to have the proper motion of $`\mu _\alpha =`$ -172.57$`\pm `$0.52 and $`\mu _\delta =`$ -381.03$`\pm `$0.45 mas per year. From positions measured in the POSS-I and POSS-II digitized images and 2MASS (Table 1), we find the candidate companion to have a proper motion over a 44.5 year baseline of $`\mu _\alpha =`$ -175$`\pm `$8 and $`\mu _\delta =`$ -390$`\pm `$6 mas per year. Since the two objects’ $`\mu _\alpha `$’s agree to within 1 $`\sigma `$ and the $`\mu _\delta `$’s within 2 $`\sigma `$, we conclude they have the same proper motion within the errors. We therefore conclude that this object, hereafter referred to as $`\upsilon `$ And B, is a common proper motion companion to the brighter star, which we will refer to as $`\upsilon `$ And A. The known radial velocity planets $`\upsilon `$ And b, $`\upsilon `$ And c, and $`\upsilon `$ And d orbit the brighter star $`\upsilon `$ And A. We note that if planetary and stellar companions are discovered in the same system, confusion can be avoided if stellar objects are noted with a capital letter, and planets noted with a lowercase letter.

### 2.3. Spectroscopic Confirmation

The companion was observed spectroscopically on 26 Jul 2001 UT using the Double Spectrograph (Oke & Gunn 1982) on the Hale 200in telescope at Palomar Observatory. The instrumental setup used the blue grating of 300 lines/mm and the red grating of 316 lines/mm with the 2$`\stackrel{}{\mathrm{.}}`$0 slit to provide a wavelength coverage from 5200 to 9100 Å at a resolution of 9 Å. Observations were reduced using standard techniques following Kirkpatrick, Henry, & McCarthy (1991) and flux calibrated using the standard star LTT 9491 (Hamuy et al 1994). The spectrum is plotted in Figure 2 and compared with spectral standards from Kirkpatrick et al (1991). The companion’s spectrum is best fit by the M4.5V standard’s spectrum. Based upon the spectral-type mass relation for late F stars (Cox 2000,p. 382), we estimate $`\upsilon `$ And A has a mass of $``$ 1.2 M, and using the spectral-type mass relationship of Henry & McCarthy (1993), we estimate a mass of 0.2 M for $`\upsilon `$ And B.

## 3. Discussion

The radial velocity monitoring group of Marcy, Butler and colleagues excluded binaries only if their separations were less than 2$`\mathrm{}`$ (G. Marcy, 2002 pers comm), so this system would still have been monitored had the companion been previously known. For $`\upsilon `$ And A, Butler et al (1999) report a measured rms velocity semiamplitude of 15.1 m s-1, after extracting the three planetary orbits from the measurements. We calculate a 0.2 M stellar companion at 750 AU would have a period of $``$ 20000 yrs and a velocity amplitude of K $``$ 100 m s-1 depending on the eccentricity and inclination of the orbit. However, the maximum radial velocity change Butler et al might have measured over their 11 year baseline would be a much smaller value, $``$ 0.4 m s-1 (for i=60 and e=0.5). For a highly eccentric (e=0.9) orbit, it could reach as large as 0.9 m s-1. Even so, this companion object would have not been detectable in the radial velocity measurements.

Since the announcement of the multiple planets around $`\upsilon `$ And A, there have been many theoretical models of the evolution and stability of three planets around a single star. While the inner planet is a ’typical’ close, hot Jupiter with a small eccentricity (0.04), the eccentricities of the outer two increase to 0.18 and 0.41, respectively. Interaction between the two outer planets has been proposed as the major influence of orbital evolution, but there has been much debate over the stability of such a system. Rivera & Lissauer (2000), who, like Laughlin & Adams (1999), ignore the innermost planet in the numerical simulations, found co-planar systems can be stable on small timescales, but the cause of the high eccentricities does not seem easily explained by only planetary interactions (Jiang & Ip 2001).

What influence would a distant stellar companion have on the orbits of a planetary system? In the numerical models of the stabilty of planets within binary systems, Holman & Weigert (1999) found certain critical semimajor axes for which disruption of the orbit could occur, depending on the eccentricity of the binary stars. For the $`\upsilon `$ And system, the critical orbital radii range from approximately 40AU to 240AU for e=0.8-0.0, respectively. While the known radial velocity planets are all well within this limit, we note that a circumprimary disk or remnant Kuiper-belt could be disrupted by this companion, depending on its inclination and eccentricity. In the HD 141569 disk, it has been suggested that the outer gap observed in the debris disk could have its origin in gravitational perturbations caused by distant companions (Weinberger et al 2000).

Another radial velocity planet with a highly eccentric orbit (e$`=`$0.63) is 16 Cygni Bb. It has been suggested that its high eccentricity might be due to interaction with the stellar companion, 16 Cygni A, at a projected separation of 800 AU (Mazeh, Krymolowski & Rosenfeld 1997; Holman, Touma, & Tremaine 1997). The tidal force of the secondary upon the smaller body was proposed to induce a modulation of the eccentricity over a long time scale ($``$108yr). This would cause a planetary orbit that forms with a small eccentricity to slowly increase its eccentricity over the current age of the star ($``$ 3 Gyr). They calculate the total increase is only weakly sensitive to the semimajor axis ratio if the period of the modulation is long, and therefore can be a large effect over the lifetime of that system.

The projected separation of the 16 Cygni binary is consistent with the projected separation we find here (750 AU), though $`\upsilon `$ And B is approximately 0.4 the mass of 16 Cygni A. However, the presence of multiple planets in the $`\upsilon `$ And system rules out the kind of effect noted above since the apsidal precession rate of the planets due to mutual interactions greatly outweighs any induced by the stellar companion (Chiang & Murray 2002). Just as the Moon, because of its proximity, has a larger effect on the terrestrial tides than the more massive but more distant Sun, the mutual interaction of the planets $`\upsilon `$ And c and $`\upsilon `$ And d is much larger than any tidal forces from distant $`\upsilon `$ And B.

## 4. Conclusion

We present astrometric and spectroscopic evidence that 2MASSI J0136504+412332 is a M4.5V common proper motion companion to the star $`\upsilon `$ And, which harbors a multiple planetary system. This represents the first system in which multiple planets exist within a multiple stellar system, but such a scenario might not be rare. There are residual velocity trends hinting of the presence of more than one planet around the binary stars 55 Cnc and $`\tau `$ Boo (Fischer et al 2001). There are currently only single planets known around the multiple stars 16 Cyg B, 94 Cet, HD 142, HD 179811B, HD 80606, HD 195019, Gl 86, and HD 89774.

Unifying all aspects of extra-solar planetary formation and evolution into a consistent model that accounts for the distribution of known orbital parameters remains a daunting task. Previously unknown stellar or substellar companions might be gravitationally affecting the entire system. The complete picture surely includes several factors including disk viscosities, planetary interactions, and companions.

The authors wish to thank E. Chiang and the anonymous referee for useful comments which helped to clarify the discussion. P.J.L. acknowledges support from a National Research Council Fellowship. P.J.L., J. D. K., and C. A. B. acknowledge the support of the Jet Propulsion Laboratory, California Institute of Technology, which is operated under contract with the National Aeronautics and Space Administration. This publication makes use of data from the Two Micron All-Sky Survey, which is a joint project of the University of Massachusetts and the Infrared Processing and Analysis Center, funded by the National Aeronautics and Space Administration and the National Science Foundation. This research has made use of the SIMBAD database, operated at CDS, Strasbourg, France.