text:
# Combinatorial pseudo-Triangulations

## 1. Introduction

The study of pseudo-triangulations in the plane was initiated recently , but it is rapidly becoming a standard topic in Computational Geometry. This paper continues the program established in , showing that pseudo-triangulations provide a missing link between planarity and rigidity in geometric graph theory. Our main result is:

###### Theorem 1.

For a plane graph $`G`$, the following conditions are equivalent:

1. $`G`$ is generically rigid in the plane.
2. $`G`$ can be stretched to become a pseudo-triangulation of its vertex set with the given topological embedding.

Recall that a *plane graph* is a graph together with a given (non-crossing) topological embedding in the plane. It is interesting to observe that property (1) is a property of the underlying (abstract) graph, while property (2) in principle depends on the embedding. That is, our result in particular implies that pseudo-triangulation stretchability of a plane graph is independent of the embedding. Another consequence is that:

###### Corollary 1.

The class of planar and generically rigid (in the plane) graphs coincides with the class of graphs of pseudo-triangulations.

The implication from (2) to (1) in Theorem 1 follows from . Here we prove the implication from (1) to (2) in two steps, via the concept of combinatorial pseudo-triangulation  introduced in Section 3. Section 5 proves that generically rigid plane graphs can be turned into combinatorial pseudo-triangulations with a certain “generalized Laman” property, and Section 4 proves that combinatorial pseudo-triangulations with this property can be stretched. In Section 6 we initiate the study of combinatorial pseudo-triangulations on closed surfaces, which we think is an interesting topic to be developed further.

## 2. Pseudo-triangulations and rigidity

Let $`A`$ be a finite point set in the Euclidean plane, in general position. A pseudo-triangle in the plane is a simple polygon with exactly three convex angles. A pseudo-triangulation of $`A`$ is a geometric (i.e., with straight edges) non-crossing graph with vertex set $`A`$, containing the convex hull edges of $`A`$ and in which every bounded region is a pseudo-triangle. A vertex $`v`$ in a geometric graph $`G`$ is called pointed if all the edges of $`G`$ lie in a half-plane supported at $`v`$ or, equivalently, if one of the angles incident to $`v`$ is greater than $`180^{}`$. A pseudo-triangulation is called pointed if all its vertices are pointed. The following numerical result has been stated several times in different forms, and is crucial to some of the nice properties of pseudo-triangulations:

###### Lemma 1.

Let $`G`$ be a non-crossing straight-line embedding of a connected graph in the plane. Let $`e`$, $`x`$ and $`y`$ denote the numbers of edges, non-pointed vertices and pointed vertices in $`G`$. Then, $`e3x+2y3`$, with equality if and only if the embedding is a pseudo-triangulation.

###### Proof.

Let $`f`$ be the number of bounded faces of the embedding. By Euler’s formula, $`x+y+f=e+1`$. We now double-count the number of “big” and “small” angles in the embedding (that is, angles bigger and smaller than 180 degrees, respectively). The total number of angles equals $`2e`$. The number of big angles equals $`y`$, and the number of small angles is at least $`3f`$ (every bounded face has at least three corners) with equality if and only if the embedding is a pseudo-triangulation. These equations give the statement. ∎

Recall that a graph is generically rigid in the plane, see  or , if any generically embedded bar and joint framework corresponding to the graph has no non-trivial infinitesimal motions. Generic rigidity is a property of the graph, and not of any particular embedding. In fact, edge-minimal generically rigid graphs on a given number $`n`$ of vertices are characterized by Laman’s Condition: they have exactly $`2n3`$ edges and every subset of $`k`$ vertices spans a subgraph with at most $`2k3`$ edges, see . Generically rigid graphs with $`|E|=2n3`$ are also known as Laman graphs.

The connection between rigidity and pseudo-triangulations was first pointed out in Streinu’s seminal paper  where it is proved that the graphs of pointed pseudo-triangulations are minimally generically rigid graphs, i.e. Laman graphs. In  it was shown that a graph $`G`$ has a realization as a pointed pseudo-triangulation in the plane if and only if the graph is a planar Laman graph. The following theorem in  extends Streinu’s result to non-minimally rigid graphs and relates the number of non-pointed vertices to the degree to which a planar rigid graph is overbraced.

###### Theorem 2.

Let $`G`$ be the graph of a pseudo-triangulation of a planar point set in general position. Then:

1. $`G`$ is infinitesimally rigid, hence rigid and generically rigid.
2. Every subset of $`x`$ non-pointed plus $`y`$ pointed vertices of $`G`$, with $`x+y2`$, spans a subgraph with at most $`3x+2y3`$ edges.

Property (2) will be crucial in our proof of Theorem 1. Observe, however, that it is not a property of the graph $`G`$, but a property of the specific straight-line embedding of $`G`$.

Another remarkable connection between planarity, rigidity, and pseudo-triangulations concerns planar rigidity circuits. These are redundantly rigid graphs such that the removal of any edge leaves a minimally rigid graph. They can, by our results, be realized as pseudo-triangulations with exactly one non-pointed vertex. Rigidity circuits, or Laman circuits, have the nice property that the number of faces equals the number of vertices and that their geometric dual (which exists and is unique) is also a Laman circuit, see . In  we show, using techniques developed here and Maxwell’s classical theory of reciprocal diagrams , that if $`C`$ is a planar Laman circuit, then $`C`$ and its geometric dual $`C^{}`$ can be realized as pseudo-triangulations with the same directions for corresponding edges.

## 3. Combinatorial pseudo-triangulations in the plane

We now consider a combinatorial analog of pseudo-triangulations. Let $`G`$ be a plane graph. We call angles of $`G`$ the pairs of consecutive edges in the vertex rotations corresponding to the embedding. Equivalently, an angle is a vertex-face incidence. By a labelling of angles of $`G`$ we mean an assignment of “big” or “small” to every angle of $`G`$. Such a labelling is called a combinatorial pseudo-triangulation labelling (or CPT-labelling, for short) if every bounded face has exactly three angles labelled “small”, all the angles in the unbounded face are labelled “big”, and no vertex is incident to more than one “big” angle.

The embedded graph $`G`$ together with a CPT-labelling of its angles is called a combinatorial pseudo-triangulation, or CPT. In figures we will indicate the large angles by an arc near the vertex between the edge pair. Figure 1 shows three graphs with large angles labelled. The one in the left is not a CPT, because the exterior face has three small angles.

Figure 1b is a CPT, whose bounded faces are three “triangles” and a hexagonal “pseudo-triangle”. If possible we shall draw large angles larger than $`180^{}`$, small ones as angles smaller than $`180^{}`$ and edges as straight non-crossing segments, but it has to be observed that this is sometimes not possible, since there are non-stretchable CPT’s, such as the one in Figure 1c.

Following the terminology of true pseudo-triangulations we say that the interior faces of a CPT are pseudo-triangles with the three small angles joined by three pseudo-edges. As in the geometric case, a vertex is called pointed if there is a big angle incident to it and the CPT is called pointed if this happens at every vertex, see Figure 1b. The following result and its proof, a straightforward counting argument using Euler’s formula, are completely analogous to the geometric situation.

###### Lemma 2.

Every combinatorial pseudo-triangulation in the plane with $`x`$ non-pointed and $`y`$ pointed vertices has exactly $`3x+2y3`$ edges.

We recall here the main result of :

###### Theorem 3.

Given a plane graph $`G`$, the following conditions are equivalent:

* $`G`$ is generically minimally rigid (isostatic),
* $`G`$ satisfies Laman’s condition,
* $`G`$ can be labelled as a pointed CPT.
* $`G`$ can be stretched to a pointed pseudo-triangulation preserving the given topological embedding.

Throughout the paper, we say that a combinatorial pseudo-triangulation $`G`$ has the *generalized Laman property* or is *generalized Laman* if every subset of $`x`$ non-pointed plus $`y`$ pointed vertices, with $`x+y2`$, induces a subgraph with at most $`3x+2y3`$ edges. This property is inspired by Theorem 2 and it is crucial to our proof; see Theorem 4. We call it the generalized Laman property because it restricts to the Laman condition for the pointed case.

###### Lemma 3.

The generalized Laman property is equivalent to requiring that every subset of $`x^{}`$ non-pointed plus $`y^{}`$ pointed vertices of $`G`$, with $`x^{}+y^{}n2`$ be incident to at least $`3x^{}+2y^{}`$ edges.

###### Proof.

Using Lemma 2, $`x`$ plus $`y`$ vertices satisfy the condition in the definition of generalized Laman if and only if the cardinalities, $`x^{}`$ and $`y^{}`$, of the complementary sets of vertices satisfy this reformulated one. ∎

Lemma 3 implies that the generalized Laman property forbids vertices of degree 1 and that vertices of degree 2 must be pointed. Moreover, any edge cutset separating the graph into two components, each containing more than a single vertex, has cardinality at least 3.

The following is a more detailed formulation of our main result, Theorem 1.

###### Theorem 4.

Given a plane graph $`G`$, the following conditions are equivalent:

* $`G`$ is generically rigid,
* $`G`$ contains a spanning Laman subgraph,
* $`G`$ can be labelled as a CPT with the generalized Laman property.
* $`G`$ can be stretched as a pseudo-triangulation (with the given embedding and outer face).

The equivalence of (i) and (ii) is Laman’s theorem and the fact that (i) and (iii) follow from (iv) is Theorem 2. We will prove (ii)$``$(iii) (Section 5) and (iii)$``$(iv) (Section 4).

Note that having the generalized Laman property is not superfluous in the statement, even for pointed CPT’s. Figure 2a shows a combinatorial pointed pseudo-triangulation (CPPT) which is not rigid because the innermost three link chain has a motion or, equivalently, which is not Laman because those four pointed vertices are incident to only seven edges.

It is also not true that every rigid CPT has the generalized Laman property, as Figure 2b shows, where the two non-pointed vertices are incident to only five edges.

If we do not require the generalized Laman property, it is easy to show that every rigid graph possesses a CPT labelling. One can start with a minimally rigid spanning subgraph, which has a CPPT labelling by Theorem 3, and then insert edges while only relabelling angles of the subdivided face. For details see . At each step one pointed vertex must be sacrificed. But it is not obvious how to preserve the generalized Laman condition in this process, even though one starts out with a Laman graph. In Section 5 we show that this can be done.

## 4. Generalized Laman CPT’s can be stretched

Here we prove the implication (iii)$``$(iv) of Theorem 4. Our proof is based on a partial result contained in Section 5 of . To state that result we need to introduce the concept of corners of a subgraph.

Let $`G=(V,E)`$ be a CPT. Since $`G`$ comes (at least topologically) embedded in the plane, we have an embedding of every subgraph of $`G`$. If $`H`$ is such a subgraph, every angle in $`H`$ is a union of one or more angles of $`G`$. Also, $`H`$ comes with a well-defined outer face, namely the region containing the outer face of $`G`$. We say that a vertex $`v`$ of $`H`$ incident to the outer face is a corner of $`H`$ if either

1. $`v`$ is pointed in $`G`$ and its big angle is contained in the outer face of $`H`$, or
2. $`v`$ is non-pointed in $`G`$ and it has two or more consecutive small angles contained in the outer face of $`H`$.

The following statement is Lemma 15 in :

###### Lemma 4.

Let $`HG`$ be a subgraph of a CPT and suppose that it is connected and contains all the edges interior to its boundary cycle (that is to say, $`H`$ is the graph of a simply connected subcomplex of $`G`$).

Let $`e`$, $`x`$, $`y`$ and $`b`$ denote the numbers of edges, non-pointed vertices, pointed vertices and length of the boundary cycle in $`S`$, respectively. Then, the number $`c_1`$ of corners of the first type (big angles in the outer boundary) of $`H`$ equals

$$c_1=e3x2y+3+b.$$

We say that a plane graph has *non-degenerate faces* if the edges incident to every face form a simple closed cycle. The following statement is part of Theorem 7 of :

###### Theorem 5.

For a combinatorial pseudo-triangulation $`G`$ with non-degenerate faces the following properties are equivalent:

1. $`G`$ can be stretched to become a pseudo-triangulation with the given assignment of angles.
2. Every subgraph of $`G`$ with at least three vertices has at least three corners.

With this, in this section we only need to prove that:

###### Theorem 6.

Let $`G`$ be a generalized Laman CPT. Then:

1. Faces of $`G`$ are non-degenerate.
2. Every subgraph $`H`$ of $`G`$ on at least 3 vertices has at least 3 corners.

Hence, $`G`$ can be stretched.

###### Proof.

1. Every face in a plane graph has a well-defined contour cycle. What we need to prove is that no edge appears twice in the cycle. For the outer face this is obvious, since all angles in it are big: a repeated edge in the cycle would produce two big angles at each of its end-points. Hence, assume that there is a repeated edge $`a`$ in the contour cycle of a pseudo-triangle of $`G`$. This implies that $`Ga`$ has two components, “one inside the other”. Let us call $`H`$ the interior component. We will show that the set of vertices of $`H`$ violates the generalized Laman property by Lemma 3.

Indeed, let $`f`$ and $`e`$ be the number of bounded faces and edges of $`H`$. Let $`x`$ and $`y`$ be the numbers of non-pointed and pointed vertices in it. The number of edges incident to the component is $`e+1`$ (for the edge $`a`$). Hence, the generalized Laman property says that:

$$e+13x+2y.$$

On the other hand, twice the number of edges of $`H`$ equals the number of angles of $`G`$ incident to $`H`$ minus one (because the removal of the edge $`a`$ merges two angles into one). The number of small angles is at least $`3f`$ and the number of big angles is exactly $`y`$. Hence,

$$2e+13f+y.$$

Adding these two equalities we get $`3e+23f+3y+3x`$, which violates Euler’s formula $`e+1=f+y+x`$.

2. Observe first that there is no loss of generality in assuming that $`H`$ is connected (if it is not, the statement applies to each connected component and the number of corners of $`H`$ is the sum of corners of its components) and that $`H`$ contains all the edges of $`G`$ interior to its boundary cycle (because these edges are irrelevant to the concept of corner). We claim further that there is no loss of generality in assuming that the boundary cycle of $`H`$ is non-degenerate. Indeed, if $`H`$ has an edge $`a`$ that appears twice in its boundary cycle, its removal creates two connected components $`H_1`$ and $`H_2`$, whose numbers of vertices we denote $`v_1`$ and $`v_2`$. We claim that each $`H_i`$ contributes at least $`\mathrm{min}\{v_i,2\}`$ corners to $`H`$. Indeed, if $`v_i`$ is 1 or 2, then all vertices of $`H_i`$ are corners in $`H`$. If $`v_i3`$, then $`H_i`$ has at least three corners and all but perhaps one are corners in $`H`$. Hence, $`H`$ has at least $`\mathrm{min}\{v_1,2\}+\mathrm{min}\{v_2,2\}\mathrm{min}\{v_1+v_2,3\}`$ corners, as desired.

Hence, we assume that $`H`$ consists of a simple closed cycle plus all the edges of $`G`$ interior to it.

Let $`y`$, $`x`$, $`e`$, and $`b`$ be the numbers of pointed vertices, non-pointed vertices, edges and boundary vertices of $`H`$, respectively. Let $`V`$ be the set of vertices of $`H`$ which are either interior to $`H`$ or boundary vertices, but not corners. $`V`$ consists of $`x+yc_1c_2`$ vertices, where $`c_1`$ and $`c_2`$ are the corners of type 1 and 2 of $`H`$, respectively. Hence, Lemma 3 implies that the number of edges incident to $`V`$ is at least

$$2(yc_1)+3(xc_2)=3x+2y2c_13c_2.$$

(Remark: $`V`$ certainly does not contain the corners of the whole CPT, whose number is at least three. This guarantees that we can apply Lemma 3 to $`V`$).

On the other hand, the edges incident to $`V`$ are the $`eb`$ interior edges of $`H`$ plus at most two edges per each boundary non-corner vertex. Hence,

$$3x+2y2c_13c_2eb+2(bc_1c_2),$$

or, equivalently,

$$c_23x+2yeb.$$

Using Lemma 4 this gives $`c_1+c_23`$. ∎

###### Corollary 2.

The following properties are equivalent for a combinatorial pseudo-triangulation $`G`$:

1. $`G`$ can be stretched to become a pseudo-triangulation (with the given assignment of angles).
2. $`G`$ has the generalized Laman property.
3. $`G`$ has non-degenerate faces and every subgraph of $`G`$ with at least three vertices has at least three corners.

###### Proof.

The implications (i)$``$(ii), (ii)$``$(iii), and (iii)$``$(i), are, respectively, Theorems 2, 6 and 5. ∎

To these three equivalences, Theorem 7 of  adds a fourth one: that a certain auxiliary graph constructed from $`G`$ is 3-connected in a directed sense. That property was actually the key to the proof of (iii)$``$(i), in which the stretching of $`G`$ is obtained using a directed version of Tutte’s Theorem saying that 3-connected planar graphs can be embedded with convex faces.

## 5. Obtaining Generalized Laman CPT-labellings

###### Theorem 7.

The angles of a generically rigid plane graph can be labelled so that the labelling is a CPT satisfying the generalized Laman condition.

The proof of the theorem proceeds by induction on the number $`n`$ of vertices. As base case $`n=3`$ suffices. Consider a generically rigid graph $`G`$ with more than three vertices. Since $`G`$ is generically rigid it contains a Laman spanning subgraph $`L`$. Let $`v`$ be a vertex of minimal degree in $`L`$. Vertices in $`L`$ have minimum degree at least two and $`L`$ has fewer than $`2n`$ edges (where $`n`$ is the number of vertices), so $`v`$ has degree two or three:

* If $`v`$ has degree two in $`L`$, then $`Gv`$ is generically rigid, because $`Lv`$ is a spanning Laman subgraph of it. By inductive hypothesis, $`Gv`$ has a generalized Laman CPT labelling. Lemma 5 shows that $`G`$ has one as well.
* If $`v`$ has degree three in $`L`$, then $`Gv`$ is either generically rigid (and then we proceed as in the previous case) or it has one degree of freedom. If the latter happens there must be two neighbors $`a`$ and $`b`$ of $`v`$ such that if we insert the edge $`e=ab`$ into $`Gv`$ we get again a generically rigid graph. Since the plane embedding of $`G`$ induces a plane embedding of $`G^{}:=Gve`$, we have by inductive hypothesis a generalized Laman CPT labelling of $`G^{}`$. Lemma 6 shows that $`a`$ and $`b`$ can be chosen so that there is a CPT labelling of $`G^{}`$ extending to one of $`G`$.

###### Lemma 5.

If $`Gv`$ is generically rigid, then every generalized Laman CPT labelling of $`Gv`$ extends to one of $`G`$.

###### Proof.

Let $`T`$ be the region of $`Gv`$ where $`v`$ needs to be inserted. This region will either be a pseudo-triangle (of the CPT labelling of $`G`$) or the exterior region of the embedding. For now, we assume that $`T`$ is a pseudo-triangle. At the end of the proof we mention how to proceed in the (easier) case where $`T`$ is the exterior region.

Let $`a`$, $`b`$ and $`c`$ be the three corners of $`T`$. There are the following cases:

1. If there is a pseudo-edge, say $`ab`$, containing at least two neighbors of $`v`$, then let $`a^{}`$ and $`b^{}`$ be the neighbors closest to $`a`$ and $`b`$ on that pseudo-edge. We may have $`a=a^{}`$ or $`b=b^{}`$, but certainly $`a^{}b^{}`$. We separate two subcases:

1. If *all* the neighbors of $`v`$ are on the pseudo-edge $`ab`$, then let us label $`v`$ as pointed, with the big angle in the face containing $`c`$. The vertices which are not neighbors of $`v`$ keep the angles they had in $`Gv`$. The neighbors of $`v`$ are labelled with both angles small, except that if $`aa^{}`$ (respectively, $`bb^{}`$) then $`a^{}`$ (resp. $`b^{}`$) gets a big angle in the face containing $`a`$ (resp. $`b`$). See Figure 3(a.1).
    2. If there is a neighbor of $`v`$ not on $`ab`$, let $`c^{}`$ be one of them, chosen closest to $`c`$ (it may be $`c`$ itself). We label $`v`$ as non-pointed, and the remaining angles as before except if $`c^{}c`$, we also put a big angle at $`c^{}`$, in the face containing $`c`$. See Figure 3(a.2).
2. If no pseudo-edge contains two neighbors, then $`v`$ has either two or three neighbors. The labelling is as in Figure 3(b), with one of the edges from $`v`$ removed (and hence $`v`$ pointed) in the case of only two neighbors. One of the corners of $`T`$ may coincide with the corresponding neighbor of $`v`$. In this case that neighbor will get two small angles.

In all cases, the CPT labelling has the property that every vertex that was non-pointed on $`Gv`$ will remain non-pointed in $`G`$. This in turn has the following consequence: let $`l`$ be the number of neighbors of $`v`$ that were pointed in $`Gv`$ and are not pointed in $`G`$. By the count of edges in a CPT, the degree $`d`$ of $`v`$ equals $`l+2`$ if $`v`$ is pointed and $`l+3`$ if $`v`$ is not pointed. This relation follows also from the above case study. The neighbors of $`v`$ that keep their status are precisely the points $`a^{}`$, $`b^{}`$ and (if it exists) $`c^{}`$ in each case.

This is crucial in order to prove the generalized Laman property, which we now do. Let $`S`$ be a subset of vertices of $`Gv`$. Since the subgraph induced by $`S`$ on $`G`$ and $`Gv`$ is the same, and since no vertex changed from non-pointed to pointed, the generalized Laman property of $`S`$ in $`Gv`$ implies the same for $`S`$ in $`G`$. But we also need to check the property for $`Sv`$. For this, by Lemma 3 it will be enough if the number of neighbors of $`v`$ in $`S`$ that did not change from pointed to non-pointed is at most two if $`v`$ is pointed and at most three if $`v`$ is non-pointed. This follows from the above equations $`d=l+2`$ and $`d=l+3`$ respectively.

As promised, we now address the case where $`T`$ is the exterior region of the embedding of $`Gv`$. This case can actually be considered a special case of (a.1) above, since the exterior region has only “one pseudo-edge”. And, indeed, a labelling similar to the one shown in Figure 3(a.1) works in this case, where the arc $`a^{}b^{}`$ now should be understood as the segment of the boundary of the exterior region of $`Gv`$ that becomes interior in $`G`$. ∎

###### Lemma 6.

Let $`v`$ be a vertex of degree three in a Laman spanning subgraph of $`G`$ and let $`e=ab`$ be an edge between two neighbors of $`v`$ such that $`G^{}:=Gve`$ is generically rigid.

1. Every CPT labelling of $`G^{}`$ extends to one of $`G`$.
2. If $`a`$ and $`b`$ are consecutive neighbors of $`v`$, then every generalized Laman CPT labelling of $`G^{}`$ extends to a generalized Laman CPT labelling of $`G`$.
3. If $`a`$ and $`b`$ are at “distance two” among neighbors of $`v`$, that is, if there is a vertex $`w`$ such that $`a`$, $`w`$ and $`b`$ are consecutive neighbors of $`v`$, then either

1. every generalized Laman CPT labelling of $`G^{}`$ extends to a generalized Laman CPT labelling of $`G`$, or
    2. there is a generically rigid subgraph $`H`$ of $`Gv`$ containing $`w`$ and with $`v`$ lying inside a bounded region of $`H`$.

It should be clarified what we mean by “extends” here. We mean that all the labels of angles common to $`G`$ and $`G^{}`$ have the same status. We exclude from this the angles at the end-points of the edge $`ab`$, which may change status, even if these angles could in principle be considered to survive in $`G`$, split into two edges $`av`$ and $`vb`$.

###### Proof.

1. As in the previous Lemma, we start with a generalized Laman CPT labelling of $`G^{}=Gve`$. Let $`T_1`$ and $`T_2`$ be the two pseudo-triangles containing $`e`$. (As in the previous Lemma, the case where one of them, say $`T_1`$, is the exterior region can be treated as if $`T_1`$ was a pseudo-triangle with all neighbors of $`v`$ in the same pseudo-edge). We call $`a_i`$, $`b_i`$ and $`c_i`$ the vertices of $`T_i`$, in such a way that the pseudo-edge from $`a_i`$ to $`b_i`$ contains $`a`$ and $`b`$, in this order. Clearly, $`a`$ coincides with at least one of $`a_1`$ and $`a_2`$, and $`b`$ with one of $`b_1`$ and $`b_2`$. Figure 4 shows the four possibilities, modulo exchange of all $`a`$’s and $`b`$’s or all $`1`$’s and $`2`$’s. In all cases we have drawn the union as a pseudo-quadrilateral even if in parts (a) and (b) a pseudo-triangle would in principle be possible. But that would actually imply that $`Gv`$ is generically rigid (because it can be realized as a generalized Laman CPT), in which case we could use Lemma 5.

We will try to extend the labelling independently in $`T_1`$ and $`T_2`$. We concentrate on one of them, say $`T_1`$. Let $`a_1^{}`$ and $`b_1^{}`$ be the neighbors of $`v`$ closest to $`a_1`$ and $`b_1`$, respectively, on the pseudo-edge $`a_1b_1`$. Observe that $`a_1^{}`$ will coincide with $`a_1`$ if $`a_1`$ is a neighbor, and will coincide with $`a`$ if $`a`$ is the only neighbor on the path $`aa_1`$. If not all the neighbors of $`v`$ in $`T_1`$ are on the pseudo-edge $`a_1b_1`$, let $`c_1^{}`$ be one which is closest to $`c_1`$ (possibly $`c_1`$ itself). We assign labels as follows: All non-neighbors of $`v`$ keep their labels. All the angles at $`v`$ and at neighbors of $`v`$ are labelled small, with the following exceptions: If $`a_1^{}a_1`$, (respectively, $`b_1^{}b_1`$ or $`c_1^{}c_1`$) the angle at $`a_1^{}`$ on the edge to $`a_1`$ is big (respectively, the angle at $`b_1^{}`$ on the edge to $`b_1`$ or the angle at $`c_1^{}`$ on the edge to $`c_1`$). Also, if all neighbors are on the pseudo-edge $`a_1b_1`$, then the angle at $`v`$ on the pseudo-triangle $`a_1b_1c_1`$ is labelled big. Figure 5 schematically shows the two cases. For future reference, observe that the neighbors of $`v`$ whose status does not change are precisely $`a_1^{}`$, $`b_1^{}`$ and, unless $`v`$ gets a big angle, $`c_1^{}`$.

This clearly produces a pseudo-triangulation of $`T_1`$, and we use the same idea in $`T_2`$. Observe also that we have not put big angles where there were none before. In particular, no vertex other than perhaps $`v`$ will receive two big angles, and no vertex that was not pointed in $`G^{}`$ will be pointed in $`G`$.

But $`v`$ itself may actually get two big angles, one on $`T_1`$ and one on $`T_2`$. This will happen if all neighbors of $`v`$ in $`T_1`$ are on the pseudo-edge $`a_1b_1`$ and all neighbors in $`T_2`$ are on the pseudo-edge $`a_2b_2`$. In this case, since $`v`$ has at least three neighbors, one of $`a_1^{}`$, $`a_2^{}`$, $`b_1^{}`$ or $`b_2^{}`$ is different from $`a`$ and $`b`$. Without loss of generality, suppose that $`a_2^{}`$ is different from $`a`$. In particular $`a_2a`$ and then $`a_1=a=a_1^{}`$ (as in parts (b), (c) or (d) of Figure 4). In this case $`a`$ has received a small angle both in $`T_1`$ and in $`T_2`$, but it was originally pointed in $`G^{}`$. We are then allowed to change the angle of $`a`$ in $`T_1`$ to be big, and that of $`v`$ in the same pseudo-triangle to be small. Figure 6 shows the change. This finishes the proof of part 1 of the Lemma.

Before going into the proofs of parts 2 and 3 we make the following observations about the CPT labelling that we have just constructed:

1. The number of neighbors of $`v`$ that do not change status is three if $`v`$ is pointed and four if $`v`$ is non-pointed. This can be proved with a case study using our explicit way of labelling, but it also follows from global counts of small angles in the CPT’s $`G`$ and $`G^{}`$.
2. Assume now that $`G^{}`$ has the generalized Laman property, and let us try to prove the property for $`G`$. Every subset $`S`$ of vertices of $`G`$ not containing $`v`$ satisfies the generalized Laman count in this CPT labelling: indeed, the subgraph induced by $`G`$ on $`S`$ is contained in the one induced by $`G^{}`$, and no vertex changed from non-pointed to pointed. Hence, the Laman count translates from $`G^{}`$ to $`G`$.
3. But if we try to prove the generalized Laman property for $`Sv`$, we encounter a problem: Suppose that $`a`$ and $`b`$ do not both belong to $`S`$, so that the subgraph induced by $`G`$ on $`S`$ is the same as that induced by $`G^{}`$. Suppose also that $`S`$ is tight in $`G^{}`$, meaning that the subgraph induced has exactly the number of edges permitted by the generalized Laman count. Then, we need to prove that if $`v`$ is pointed (respectively, non-pointed) at most two (respectively, three) of the neighbors of $`v`$ in $`S`$ keep their pointedness status. But, globally, we know that three (respectively, four) of the neighbors of $`v`$ keep their status, so we cannot finish the proof.

However, from this analysis we get very precise information on the cases where $`G`$ happens not to have the generalized Laman property. Namely, if $`Sv`$ fails to satisfy the generalized Laman count, $`S`$ has the following four properties:

* $`S`$ does not contain both $`a`$ and $`b`$. Otherwise, the deleted edge $`ab`$ allows for one extra edge to be inserted and the count is satisfied.
    * $`S`$ is tight in $`G^{}`$, otherwise again an extra edge is allowed to be inserted. This implies that if $`G^{}`$ is embedded as a pseudo-triangulation (via Theorem 6), then the subgraph $`G^{}|_S`$ induced by $`S`$ is itself a pseudo-triangulation. Indeed, let $`e_S`$, $`x_S`$ and $`y_S`$ be the numbers of edges, non-pointed vertices and pointed vertices of $`G^{}|_S`$. Let $`x`$ and $`y`$ be the numbers of vertices of $`S`$ which are non-pointed and pointed in $`G^{}`$, we have

    $$e_S=3x+2y33x_S+2y_S3.$$

    Hence, $`G^{}|_S`$ is a pseudo-triangulation by Lemma 1.
    * In particular, $`G^{}|_S`$ is generically rigid. Since $`G^{}|_S`$ does not contain $`ab`$, this implies that $`S`$ moves rigidly in the 1-degree of freedom (*1-dof*) mechanism $`Gv`$.
    * $`S`$ contains all the neighbors of $`v`$ that did not change their status when we extended the CPT labelling. In particular, at least one of $`a`$ or $`b`$ did change its status.

2. We now suppose that $`a`$ and $`b`$ are consecutive neighbors of $`v`$. Suppose that $`T_1`$ is the pseudo-triangle in which there is no other neighbor. Certainly, $`T_1`$ does not impose any change of status for $`a`$ or $`b`$. So, if $`a`$ or $`b`$ change their status, this must be because of what happens in the pseudo-triangle $`T_2`$. There are two cases:

* If our CPT-labelling of $`T_2`$ only changes the status of one of $`a`$ or $`b`$, we can restore its status by the same type of change that we used when $`v`$ got two big angles: in the pseudo-triangle $`T_1`$ we change the angle of $`v`$ from big to small, and that of the neighbor that changed status in $`T_2`$ (which, clearly, had a big angle on $`T_2`$ and hence a small angle in $`T_1`$), from small to big. We now have a CPT-labelling where neither $`a`$ nor $`b`$ changed status, hence the generalized Laman property holds.
* If our CPT-labelling of $`T_2`$ changes the status of both $`a`$ and $`b`$, let $`a^{}`$ and $`b^{}`$ be the neighbors of $`v`$ in the pseudo-edge $`a_2b_2`$ that do not change their status by the CPT-labelling of $`T_2`$. We can try to apply the trick of the previous case at vertex $`a`$ and at vertex $`b`$. If the first one fails, we have a CPT-labelling where $`a`$, $`a^{}`$ and $`b^{}`$ did not change their status and without the generalized Laman property. By our final remarks in the proof of part 1, this implies that $`a`$, $`a^{}`$ and $`b^{}`$ move rigidly in the 1-dof mechanism $`Gv`$. Similarly, if the second fails, $`b`$, $`b^{}`$ and $`a^{}`$ move rigidly. Hence, if both fail, $`a`$, $`b`$, $`a^{}`$ and $`b^{}`$ move rigidly in $`Gv`$, which contradicts our initial choice of the edge $`e=ab`$.

3. Applying the construction of part 1 to the edge $`e`$, it turns out that $`w`$ must be one of the points that does not change status (that is, one of the points $`a_i^{}`$, $`b_i^{}`$ or $`c_i^{}`$ of Figure 5). Suppose that the resulting CPT is not generalized Laman, for some generalized Laman CPT of $`G^{}`$. We want to prove that there is a rigid component of $`Gv`$ that includes $`w`$ and contains $`v`$ in the interior of a cycle.

By the remarks at the end of the proof of part 1, if the generalized Laman property fails in $`G`$, then there is an induced subgraph $`S`$ of $`Gv`$ that contains all the neighbors of $`v`$ that did not change status (in particular, contains $`w`$), and which is itself a pseudo-triangulation (with respect to the CPT labelling of $`G^{}`$). If this pseudo-triangulation already contains $`v`$ in the interior of a pseudo-triangle, then the claim is proved. But it may happen that $`v`$ is in the exterior of this sub-pseudo-triangulation (see a schematic picture in Figure 7).

The crucial point now is that in the construction of part 1 the vertices that do not change status cannot all lie on the same pseudo-edge of the pseudo-quadrilateral of $`Gv`$ containing $`v`$. Indeed, one of them is either $`a_1^{}`$ or $`a_2^{}`$ (this is the point marked $`a^{}`$ in Figure 7), and lies on one of the two pseudo-edges “on the $`a`$ side”. Another one is either $`b_1^{}`$ or $`b_2^{}`$ (marked $`b^{}`$ in Figure 7), and lies on the two pseudo-edges “on the $`b`$-side”.

So, if $`v`$ is exterior to $`S`$, then the boundary of $`S`$ contains a concave chain connecting two different pseudo-edges of the pseudo-quadrilateral. Together with the opposite part of the pseudo-quadrilateral this produces a pseudo-triangle in $`Gv`$ that contains $`v`$ in its interior and all the vertices that did not change status on its boundary. This pseudo-triangle, together with everything in its exterior, is a pseudo-triangulation, hence generically rigid (here, we are assuming that $`G^{}`$ and, in particular, $`Gv=G^{}e`$ has been stretched, via Theorem 6). ∎

###### Corollary 3.

Let $`v`$ be a vertex of degree three in a Laman spanning subgraph of $`G`$. Then, there is an edge $`e=ab`$ between two neighbors of $`v`$ such that $`G^{}:=Gve`$ is generically rigid and every generalized Laman CPT labelling of $`G^{}`$ extends to a generalized Laman CPT labelling of $`G`$.

###### Proof.

Let $`w_1,\mathrm{},w_k`$ be the cyclic list of neighbors of $`v`$ in $`G`$. If there is an edge $`e=w_iw_{i+1}`$ (with indices meant modulo $`k`$) between consecutive neighbors of $`v`$ that restores rigidity in $`Gve`$, then part 2 of the previous Lemma gives the statement for that $`e`$. Hence, in the rest of the proof we suppose that this is not the case.

We now look at edges of the form $`e=w_{i1}w_{i+1}`$. At least one of them must restore rigidity in $`Gve`$: if not, let $`G_0`$ be the graph consisting of the $`2k`$ edges $`w_iw_{i+1}`$ and $`w_{i1}w_{i+1}`$. Our hypothesis is that $`GvG_0`$ is still a 1-dof mechanism. But, since $`G_0`$ is rigid and contains all neighbors of $`v`$, this implies that $`GG_0`$, hence $`G`$, is a 1-dof mechanism too, a contradiction.

Let $`S`$ be the set of neighbors of $`v`$ in $`G`$ with the property that $`w_{i1}w_{i+1}`$ restores rigidity. In the rest of the proof we show that there is a $`w_iS`$ such that $`e=w_{i1}w_{i+1}`$ is as claimed in the statement. We argue by contradiction, so assume the claim is not true. Part 3 of the previous Lemma says that then for each $`w_iS`$ there is a generically rigid subgraph of $`Gv`$, let us denote it $`H_{w_i}`$, such that $`w_iH_{w_i}`$ and $`v`$ lies in the interior of a bounded face of $`H_{w_i}`$. We now claim that the same holds for every $`S^{}S`$: there is a generically rigid subgraph $`H_S^{}`$ of $`Gv`$ such that (1) $`S^{}H_S^{}`$ and (2) $`v`$ lies in the interior of a bounded face of $`H_S^{}`$. Indeed, after we know this for one-element subsets we just need to show that from $`H_{S_1}`$ and $`H_{S_2}`$ we can construct $`H_{S_1S_2}`$. We consider first the union of the two graphs $`H_{S_1}`$ and $`H_{S_2}`$. It clearly contains both $`S_1`$ and $`S_2`$, and $`v`$ lies in the interior of a face: the intersection of the faces $`F_1`$ of $`H_{S_1}`$ and $`F_2`$ of $`H_{S_2}`$ that contain $`v`$. The only problem is that $`H_{S_1}H_{S_2}`$ may not be generically rigid. Since $`H_{S_1}`$ and $`H_{S_2}`$ clearly intersect (the boundaries $`F_1`$ and $`F_2`$ of $`F_1`$ and $`F_2`$ are two cycles around $`v`$ that must intersect because they both contain neighbors of $`v`$ in $`G`$), if their union is not generically rigid then they intersect in a single point. This point must actually be in the two cycles $`F_1`$ and $`F_2`$. That is, the cycles “are tangent and one is inside the other”. Since $`S_1F_1`$ and $`S_2F_2`$ consist only of neighbors of $`v`$ in $`G`$, this implies that one of $`S_1`$ and $`S_2`$ (say $`S_1`$) consists of a single point $`w_i`$, which is the intersection point. In particular, $`S_1H_{S_2}`$ and we can take $`H_{S_1S_2}=H_{S_2}`$.

So, taking $`S^{}=S`$, the conclusion is that all the $`w_i`$’s such that $`w_{i1}w_{i+1}`$ restores rigidity lie in a rigid subgraph of $`Gv`$. Our final claim is that under these conditions all neighbors of $`v`$ move rigidly in the 1-dof mechanism $`Gv`$, which (as above) contradicts the fact that $`G`$ is rigid. Indeed, assume without loss of generality that the vertex $`w_1`$ is such that $`w_kw_2`$ restores rigidity. To seek a contradiction, let $`w_{i+1}`$ be the first neighbor of $`v`$ (in the order $`w_1,\mathrm{},w_k`$) which does not move rigidly with $`w_1`$ and $`w_2`$, and let $`w_{j+1}`$ be the first neighbor after $`w_i`$ which does not move rigidly with $`w_iw_{i+1}`$. In particular, both $`w_{i1}w_{i+1}`$ and $`w_{j1}w_{j+1}`$ restore rigidity and, by the above conclusion, the three vertices $`w_1`$, $`w_i`$ and $`w_j`$ lie in a rigid subgraph. This subgraph has two vertices in common with both $`\{w_1,\mathrm{},w_i\}`$ and $`\{w_i,\mathrm{},w_j\}`$, which lie respectively in two rigid subgraphs by the choice of $`w_i`$ and $`w_j`$. Hence, all $`\{w_1,\mathrm{},w_j\}`$ lies in a rigid subgraph, in contradiction with the choice of $`w_i`$. ∎

## 6. Pseudo-triangulations on closed surfaces

This section contains a couple of observations on the concept of pseudo-triangulations (and combinatorial ones) on closed surfaces. We believe it would be interesting to develop this concept further.

Let $`G`$ be a graph embedded on some closed surface of genus $`g`$. Every closed surface can be realized as the quotient of the sphere, the Euclidean plane, or the hyperbolic plane, by a discrete group of isometries, so in each case there is a well defined notion of distance and angle. Similar to the situation in the plane, a pseudo-triangulation of the surface is a graph embedding with geodesic arcs such that every face has exactly three angles smaller than $`180^{}`$. A combinatorial pseudo-triangulation is a (topological) embedding together with an assignment of “big” and “small” to angles such that every face has exactly three small angles and every vertex has at most one big angle. One difference with the situation in the plane is that now there is no “outer” face.

###### Proposition 1.

Let $`G`$ be embedded on a surface $`S`$ of genus $`g`$. If $`G`$ possesses a combinatorial pseudo-triangular assignment then the numbers $`e`$, $`x`$ and $`y`$ of edges, non-pointed vertices and pointed vertices satisfy $`e=3x+2y6+6g`$ if $`S`$ is orientable, and $`e=3x+2y6+3g`$ if $`S`$ is non-orientable.

###### Proof.

The number of angles equals twice the number of edges. There are $`2ey`$ small angles. The number of small angles equals three times the number of faces, $`f`$, which together with Euler’s formula $`x+ye+f=22g`$ in the orientable case, or $`x+ye+f=2g`$ in the non-orientable case yields the desired relationship between $`x`$, $`y`$ and $`e`$. ∎

The tree in Figure 1a is an example of a pointed pseudo-triangulation of the sphere. A triangular prism which can realized as a pointed pseudo-triangulation in the plane, cannot be realized as a pointed pseudo-triangulation of the sphere since, by Proposition 1, any CPT labelling of the prism for the sphere must have three non-pointed vertices. The graph of a cube, which has no CPT labelling for the plane, since it has too few edges to be rigid, can be realized as a pseudo-triangulation of the sphere, with two non-pointed vertices, see Figure 8

in which the pointed vertices are placed on the equator, and the two non-pointed vertices are at the poles. In this geometric realization the large angles are exactly $`180^{}`$, so that pseudo-triangles are actual triangles, although the complex is not a triangulation since it is not regular.

In Figure 9 we see the well known embedding of the one-skeleton of the octahedron into the torus with all square faces.

In Figure 10

we have modified this construction to embed the octahedron graph as a pointed pseudo-triangulation of the torus. The octahedron graph, which is overbraced as a framework in the plane, has no pointed pseudo-triangular embedding in either the plane or the sphere.

## Acknowledgements

This research was initiated at the Workshops on Topics in Computational Geometry organized by Ileana Streinu at the Bellairs Research Institute of McGill University in Barbados, Jan. 2002 and 2003, and partially supported by NSF Grant CCR-0203224. We also thank G. Rote and an anonymous referee for comments that helped us improve the presentation.


format: text

text:
# Improving the Security and Performance of the BaBar Detector Controls System

## I Introduction

This paper describes the motivation behind and implementation of a CA Gateway gw-ref  in the BaBar Online Detector Controls System.

## II Motivation

With the IOCs on the BaBar public network, there were no limits on the number of clients (aside from the limit of 384 ssh sessions) that could connect and request values. These clients could run on any of the 63 workstations on the BaBar public network. Remote access to the BaBar public network was possible via ssh.

As a result, the number of open file descriptors on an IOC could exceed the 150 limit (already increased significantly from the default 50) and the CPU usage of an IOC could go as high as 100

## III Implementation

The IOCs were moved to a private network and the four servers running EPICS client software that were essential for data-taking were given a secondary network interface so that they could access the private network. CA gateway software was installed on one of these servers, ”bbr-srv01”. Statistics of the gateway are displayed instantaneously in Figure 1 and over time in Figure 2.

The gateway acts as a client to the IOCs, requesting channels and receiving replies at the rate of approximately 285 channels per sec (Figure 1).

The gateway also acts as a server, providing a cached superset of all the IOCs’ values to public EPICS clients. In Figure 1, we see that the number of channels active in the current cache is 15692 and the number of channels that will be held in the cache for up to two more hours is 17854.

The server is receiving requests and responding to them at the rate of 1343.56 channels per second. The software was built without the flags to monitor the number of file descriptors in use, so this explains ”FDs: 0”.

Plotted against time (Figure 2), we see that the number of alive and active channels is near constant and that there are small fluctuations in the event and post rates.

The dual network interface card (NIC) servers required a special EPICS configuration to avoid seeing ambiguous replies to their request for data (since they could access both the IOCs directly and the CA gateway for values).

The BaBar private network is not routed, so IOCs are hidden from the public internet address space.

IOCs use security access files to define access security groups and rules to specify which users can carry out which actions. For example, the access security group “dchexpert” may contain a list of users who are allowed to turn on the high voltage for the drift chamber. A security access file for the gateway was constructed from the sum of the individual IOC access security files. The userid running the gateway processes had to be added to the individual IOC’s security rules since requests to do secure transactions at the IOC level were being made by the gateway process and not the expert user, if initiated from the public network.

## IV Results

The number of file descriptors decreased by 25% and the CPU usage decreased by 20–40%, on average for the 17 IOCs. There were fewer IOC hangs/disconnects which helped to improve BaBar’s data-taking efficiency.

Internal IOC security is maintained by propagating the IOC security access definitions to the gateway security definitions. External IOC security is improved since IOCs are no longer publicly visible.

## V Appendix

The poster displayed at CHEP 2003, in two halves (Figures 3 and 4).


text:
# Thermal equilibrium under the influence of gravitation

(Auf der Hoehe 82, 52223 Stolberg, Germany)

## Abstract

Gas clouds under the influence of gravitation in thermodynamic equilibrium cannot be isothermal due to the Dufour effect, the energy flux induced by density gradients. In galaxy clusters this effect may be responsible for most of the ”cooling flows” instead of radiative cooling of the gas.

Recent observations of galaxy clusters with high spatial resolution have shown that in most of them the intracluster plasma is far from being isothermal, exhibiting strong decrease of the plasma temperature in the vicinity of individual large galaxies. This effect is commonly attributed to ”cooling flows”, that means, increasing radiative energy loss with increasing density of the gas, which is gravitationally attracted by the galaxies. But several discussions (Voigt et al. , Markevitch et al. ) have shown that most of the temperature gradients would be washed out by thermal conduction, if the thermal conductivity of the plasma were of the magnitude given in the classical book by Spitzer .

It has been proposed that magnetic fields may reduce the thermal conductivity. The existence of magnetic fields in the order of $`0.11\mu \mathrm{G}`$ has been confirmed by various observations (see e.g. Dolag et al. ). But to produce the required reduction, ordered magnetic fields of a still higher magnitude would be necessary, as the heat flux reduction works only perpendicular to the magnetic field lines. Narayan and Medvedev  have shown that fields fluctuating on a large range of length scales can produce only minor changes in the thermal conductivity.

In all these discussions it is implicitly assumed that in thermodynamic equilibrium conduction leads to a uniform temperature, though it is well known that density gradients may cause a flux of energy and thus induce temperature gradients, an effect known from the textbooks as ”Dufour effect” (see e.g. Hirschfelder et al. ).

Speaking of equilibrium means that the net fluxes of all properties determining the state of a system are locally balanced. Normally in a gas we associate this with constant pressure, density and temperature. But in a system, which is influenced by volume forces such as gravitation, the equilibrium state may well exhibit gradients of the state variables. Mass flow equilibrium in these systems is obtained by the balance between the gravitational force and the counteracting pressure gradient, which is related to the density gradient by some equation of state.

But if there is a density gradient, there must be also a temperature gradient, balancing the Dufour effect, to obtain zero net energy flux. Below we will derive the equilibrium conditions for a system, which is fully relaxed with respect to flux of mass, momentum and energy, within the scope of a simplified kinetic model.

For this purpose we determine the net flux of mass and energy through a control area $`\mathrm{\Delta }F`$ under the condition that the particles in the gas have a Maxwellian distribution everywhere, but with number density and mean energy varying perpendicular to the control area. The net flux is calculated then under the assumption, that any particle crossing the control area retains its velocity and direction, which it has obtained in the last collision, one mean free path from the surface, and in addition is subjected to some acceleration from the force field. In the energy balance the gain and loss of kinetic energy due to the changing gravitational potential will be omitted, as it cancels out from the balance exactly, when the net particle flux through the control area is zero.

Denoting the direction perpendicular to the surface as z and the angle between this and the direction of particle motion as $`\theta `$, the flux of some property $`G`$ through the surface is

$$j=\mathrm{\Delta }F\mathrm{cos}\theta (j^+j^{})𝑑\mathrm{\Omega },$$
(1)
where $`j^+`$ and $`j^{}`$ are the normal components of the flux of $`G`$ carried by particles moving towards the surface in positive and negative $`z`$ direction under the angle $`\theta `$. The integration has to be taken over half the solid angle $`\pi /2\theta 0`$. Denoting the amount of property $`G`$ carried by particles moving with velocity $`v`$ by $`g(v)`$, the flux components of $`g(v)`$ are

$$j^+=(g(v)\frac{dg(v)}{dz}\lambda \mathrm{cos}\theta )(v\mathrm{cos}\theta +b\frac{\lambda }{v})$$
(2)
$$j^{}=(g(v)+\frac{dg(v)}{dz}\lambda \mathrm{cos}\theta )(v\mathrm{cos}\theta b\frac{\lambda }{v})$$
(3)
$`\lambda `$ is the mean free path, which may depend also on the velocity. The last term denotes the acceleration of the particles during their flight from the last collision to the control surface. Integrating eq.(1) over $`d\mathrm{\Omega }`$ yields the equation

$$j=\pi \mathrm{\Delta }F\left(\lambda v\frac{dg(v)}{dz}\frac{2b\lambda }{v}g(v)\right)$$
(4)
To determine mass and energy transport by particles moving with velocity $`v`$, $`g`$ has to be set to

$$g_\mathrm{M}=n(z)mf(v,z)dv,g_\mathrm{E}=n(z)m\frac{v^2}{2}f(v,z)dv$$
(5)
In case of a neutral gas $`n(z)`$ and $`m`$ are the density and mass of atoms, $`f(v,z)`$ is the distribution function

$$f(v)dv=\frac{4}{\sqrt{\pi }}\frac{v^2}{\beta ^3}e^{\frac{v^2}{\beta ^2}}dv$$
(6)
$`\beta (z)`$ being the abbreviation $`\beta (z)=\sqrt{2kT(z)/m}`$. To calculate the quantity $`dg/dz`$ we also need the derivative

$$\frac{df}{dz}=\frac{d\beta }{dz}\frac{4}{\sqrt{\pi }}\left(\frac{2v^4}{\beta ^6}\frac{3v^2}{\beta ^4}\right)e^{\frac{v^2}{\beta ^2}}=\frac{1}{\beta }\frac{d\beta }{dz}\left(\frac{2v^2}{\beta ^2}3\right)f(v)$$
(7)
While in a neutral gas the parameter $`b`$ in eq.(4) is the normal gravitational acceleration, in a plasma the action of the force is somewhat indirect. Energy transport is mediated preferably by electrons. Thus in eqs.(5) $`n(z)`$ and $`m`$ are the electron density and mass. But in this case acceleration by the external force is acting also on the ions, which transfer the force to the electrons by Coulomb interaction. Thus the parameter $`b`$ in eqs.(2) and (3) is not the gravitational acceleration of free moving electrons. But for the equilibrium condition of zero transport the absolute magnitude of $`b`$ is not relevant, when we only want to know, under which conditions the net flux of electrons and the flux of energy carried by them are in balance.

An additional difference between neutral gas and plasma results from the fact that the collision cross section between neutral atoms is nearly independent of the collision energy, so that the mean free path $`\lambda `$ does not depend on $`v`$. In plasmas, where Coulomb interaction is dominant, the mean free path increases with $`v^2`$. Thus in the further calculations we set $`\lambda =\lambda _0(v/v_0)^\alpha `$ with $`\alpha =0`$ for neutral gas and $`\alpha =2`$ for a fully ionised plasma.

Introducing eqs.(5) to (7) into eq.(4), we get for the mass and energy flux

$$j_\mathrm{M}=2\beta ^\alpha \left(x\beta \frac{dn}{dz}+x(2x^23)n\frac{d\beta }{dz}\frac{2bn}{\beta }\frac{1}{x}\right)h(x)dx$$
(8)
$$j_\mathrm{E}=\beta ^{\alpha +2}\left(x^3\beta \frac{dn}{dz}+x^3(2x^23)n\frac{d\beta }{dz}\frac{2bn}{\beta }x\right)h(x)dx$$
(9)
with $`x=v/\beta `$ and $`h(x)=2\sqrt{\pi }m\mathrm{\Delta }F(\lambda _0/v_0^\alpha )x^{2+\alpha }e^{x^2}`$.
Integrating these equations over all x, we obtain the conditions for zero mass and energy flux:

$$\beta \frac{dn}{dz}F_{3+\alpha }+n\frac{d\beta }{dz}[2F_{5+\alpha }3F_{3+\alpha }]\frac{2bn}{\beta }F_{1+\alpha }=0$$
(10)
$$\beta \frac{dn}{dz}F_{5+\alpha }+n\frac{d\beta }{dz}[2F_{7+\alpha }3F_{5+\alpha }]\frac{2bn}{\beta }F_{3+\alpha }=0$$
(11)
The abbreviation $`F_k`$ stands for the integral $`F_k=_0^{\mathrm{}}x^ke^{x^2}𝑑x`$. The different arguments of $`F_k`$ in eqs.(10) and (11) can be eliminated by the recurrence formula $`F_{k+2}=(k+1)/2\times F_k`$, so that we finally obtain the equilibrium conditions for mass and energy transport:

$$\frac{2+\alpha }{2}\beta \frac{dn}{dz}+\frac{(2+\alpha )(1+\alpha )}{2}n\frac{d\beta }{dz}\frac{2bn}{\beta }=0$$
(12)
$$\frac{4+\alpha }{2}\beta \frac{dn}{dz}+\frac{(4+\alpha )(3+\alpha )}{2}n\frac{d\beta }{dz}\frac{2bn}{\beta }=0$$
(13)
It is immediately evident that this is a set of linear equations for the gradients $`d\beta /dz`$ and $`dn/dz`$. If there are no external forces $`(b=0)`$, there exists only the trivial solution $`d\beta /dz=0`$ and $`dn/dz=0`$.

In the presence of volume forces such as gravitation eqs.(12) and (13) are inhomogeneous and allow a non-trivial solution, which constitutes a fixed relation between temperature gradient and particle density gradient or, because of quasi-neutrality, also between temperature and mass density gradient. Eliminating $`b`$ leads to the relation

$$\beta \frac{dn}{dz}+(2\alpha +5)n\frac{d\beta }{dz}=0$$
(14)
with the solution $`n\beta ^{(2\alpha +5)}=\mathrm{const}.`$ Replacing the number density by the mass density $`\rho `$ and $`\beta `$ by $`\sqrt{2kT/m}`$ we finally find the condition $`\rho T^{5/2}=\mathrm{const}.`$ for neutral gas and $`\rho T^{9/2}=\mathrm{const}.`$ for a fully ionised plasma.

Though the relative temperature gradients are small compared to the associated density gradients, they may well be important in the hot corona of stars or in the intergalactic gas in galaxy clusters, where temperature changes by a factor of three are reported (Voigt et al. ), while the gas density may change by a few orders of magnitude in the vicinity of large galaxies. It may even be that most of the observed temperature drop in the ”cooling flows” around these galaxies is not caused by radiative cooling but by the ”conductive cooling” associated with the density gradients.

It should be noted that due to the Dufour effect complete galaxy clusters would have cooled off, if thermal conductivity were at the Spitzer value, unless the clusters are embedded in a very hot but thin intergalactic plasma. The existence of a diffuse high energy x-ray background (Boldt ) is a strong hint to its existence. Matter expelled in the jets of quasars may be the origin of this plasma.


text:
# 1 INTRODUCTION

## 1 INTRODUCTION

An important characteristic of an ecosystem is the total set of interactions between the various individuals. Organisms may influence each other in many ways and it is difficult to monitor and quantify all possible interactions except the most direct, such as simple trophic relations. The development of the set of interactions over evolutionary time scales is even more difficult to measure because of random mutations and the resulting adaptations. Gaining an understanding from observations is also problematic since laws may very well only be recognisable at the level of averages, see \[Loreau and Hector, 2001, Yedid and Bell, 2002\]. Here, we approach these issues within the framework of a simple model of ecosystem assembly and evolution \[Christensen et al., 2002, Hall et al., 2002, di Collobiano et al., 2003\].

We compare early and late time connectivity and cluster properties of ecosystems evolving in two differently connected spaces: genotypes influence either a small or a large number of others. Clearly, the actual number of interactions experienced by a site depends on which of all the possible mutations and adaptations have occurred, i.e. the network is dependent on its history. It turns out that the interaction strengths change significantly with time, whilst the degree (number of active interactions) distribution remains close to what would be expected if genotypes were occupied at random. The species abundance curve takes a log-normal form only for spaces where the genotypes are linked to many others. Our model is neutral in some aspects but also draws on concepts from niche theory.

## 2 METHODS

We briefly describe the structure and dynamics of the Tangled Nature model. Details can be found in \[Christensen et al., 2002, Hall et al., 2002\]. An individual is represented by a vector $`𝐒^\alpha =(S_1^\alpha ,S_2^\alpha ,\mathrm{},S_L^\alpha )`$ in the genotype space $`𝒮`$, where the “genes” $`S_i^\alpha `$ may take the values $`\pm 1`$, i.e. $`𝐒^\alpha `$ denotes a corner of the $`L`$-dimensional hypercube. In the present paper we take $`L=20`$. We think of the genotype space $`𝒮`$ as containing all possible ways of combining the genes into genome sequences. Many sequences may not correspond to viable organisms. The viability of a genotype is determined by the evolutionary dynamics. All possible sequences are made available for evolution to select from. The number of occupied sites is referred to as the diversity.

For simplicity, an individual is removed from the system with a constant probability $`p_{kill}`$ per time step. A time step consists of one annihilation attempt followed by one reproduction attempt. One generation consists of $`N(t)/p_{kill}`$ time steps, which is the average time taken to kill all currently living individuals. All references to time will be in units of generational time.

The ability of an individual to reproduce is controlled by a weight function $`H(𝐒^\alpha ,t)`$:

$$H(𝐒^\alpha ,t)=\frac{1}{cN(t)}\left(\underset{𝐒𝒮}{}J(𝐒^\alpha ,𝐒)n(𝐒,t)\right)\mu N(t),$$
(1)
where $`c`$ is a control parameter, $`N(t)`$ is the total number of individuals at time $`t`$, the sum is over the $`2^L`$ locations in $`𝒮`$ and $`n(𝐒,t)`$ is the number of individuals (or occupancy) at position $`𝐒`$. Two positions $`𝐒^a`$ and $`𝐒^b`$ in genome space are coupled with the fixed random strength $`J^{ab}=J(𝐒^a,𝐒^b)`$ which can be either positive, negative or zero. This link is non-zero with probability $`\theta `$. There is no self-interaction, so $`J^{aa}=0`$. The present paper compares the three cases $`\theta =\frac{1}{1000}`$, $`\theta =\frac{1}{200}`$ and $`\theta =\frac{1}{4}`$. The non-zero values of $`J^{ab}J^{ba}`$ are determined by a deterministic but rapidly varying function of the two positions $`𝐒^a`$ and $`𝐒^b`$ \[Hall et al., 2002\].

The conditions of the physical environment are simplistically described by the term $`\mu N(t)`$ in equation (1), where $`\mu `$ determines the average sustainable total population size, i.e. the carrying capacity of the environment. An increase in $`\mu `$ corresponds to harsher physical conditions. Notice that genotypes only adapt to each other and the physical environment represented by $`\mu `$. We use asexual reproduction consisting of one individual being replaced by two copies. Successful reproduction occurs with a probability per unit time given by

$$p_{off}(𝐒^\alpha ,t)=\frac{\mathrm{exp}[H(𝐒^\alpha ,t)]}{1+\mathrm{exp}[H(𝐒^\alpha ,t)]}[0,1].$$
(2)
We allow for mutations in the following way: with probability $`p_{mut}`$ per gene we perform a change of sign $`S_i^\alpha S_i^\alpha `$, during reproduction.

Initially, we place $`N(0)=500`$ individuals at randomly chosen positions. Their initial location in genotype space does not affect the dynamics. A two-phase switching dynamic is seen consisting of long periods of relatively stable configurations (quasi-Evolutionary Stable Strategies or q-ESSs) interrupted by brief spells of reorganisation of occupancy which are terminated when a new q-ESS is found, as discussed in \[Christensen et al., 2002\].

## 3 RESULTS

### a Parameters

As mentioned previously, the only parameter that is changed in this paper is the connectivity, $`\theta `$. The values used throughout are $`L=20`$, $`c=0.005`$, $`\mu =0.01`$, $`p_{kill}=0.2`$ and $`p_{mut}=0.015`$. This selection provides several transitions between different q-ESSs for each run, see \[Hall et al., 2002, di Collobiano et al., 2003\]. We consider three $`\theta `$ values: $`0.001`$, $`0.005`$ and $`0.25`$, which we will refer to as very low, low and high $`\theta `$ respectively. These correspond to below, near and above the percolation threshold. That is, the point where there is a non-zero probability that all living sites are connected in one dominant cluster \[Albert and Barabási, 2002\]. A realistic species abundance curve was only obtained above the threshold. We will be contrasting results at $`t=500`$ (primal time), $`t=\mathrm{5\; 000}`$ (early time) and $`t=\mathrm{500\; 000}`$ (late time). Early time is well outside the system’s initial transient search for a quasi-stable configuration in genotype space. The low and high $`\theta `$ ensembles consist of 500 realisations. Each run uses a different random number seed but, for any given run, only $`\theta `$ is changed between the two ensembles.

Each figure in the paper, apart from figure 4, shows two sets of data: one labelled simulation (which are the results generated by the dynamics of the model) and the other random. In the random case, rather than evolving the network, for any specified time we read in the diversity and number of individuals alive in the simulated run. The individuals are then thrown on to the network of $`2^{20}`$ genotypes at random with the constraint that the diversity is the same as the simulation. Thus, random data is not dependent on the history of the network, but has the same global properties (diversity and population size) as the simulations. This provides a very useful null model. Comparisons with this procedure will reveal whether the network is really evolving, or the results are just by-products of increasing diversity. Simulated data is always shown as a dotted line and random as a continuous line.

### b Connectivity

We study the temporal evolution of the network connectivity in the space of occupied positions for different $`\theta `$ values. Note that the hard-wired configuration of couplings $`J(𝐒^𝐚,𝐒^𝐛)`$ between all $`2^{20}`$ positions in genotype space is determined at $`t=0`$ and remains constant. The network of occupied sites will nevertheless change with time. The degree distributions in figure 1 show the number of genotypes having $`x`$ active interactions.

The leftmost pair of curves represents primal time, the next, early time and the rightmost late time. Considering only the simulation data for now, a clear shift to a greater number of active links is seen in the high $`\theta `$ case, whilst a slight change occurs for low $`\theta `$. The difference between early and late time is bigger than that between early and primal time. The degree of a site is equal to the number of direct interactions it has with all other occupied sites. This explains why any particular site in the low $`\theta `$ runs only has at most nine and usually only one or two direct interactions. The data is integrated over each ensemble. How much of this shift is due to a genuine change in network connectivity? For high $`\theta `$, the null model data shows that there is very little difference between evolving the network and throwing down individuals randomly. Low $`\theta `$ appears to show a change. However, any site that does not interact with any others will die very quickly in a simulation. If for any instant in time genotype positions are chosen by chance, such a low connectivity will give a disproportionate number of isolated genomes that would be forbidden by the dynamics. There is no fair way to simulate this effect, but it can be seen that the differences between the time curves in the random and simulated runs is similar and thus the network connectivity does not evolve for either value of $`\theta `$.

### c Interaction strength

For both $`\theta `$ values, the diversity gradually increases with time. What is causing this? It turns out that the strength of the interaction between sites is crucial to the ability of the network to support larger numbers of individuals. Figure 2 shows the distribution of interaction strengths between each living site and all other living sites at a given time. Interaction strengths are assigned at random and are not necessarily symmetric \[Hall et al., 2002\]. For example, $`J(𝐒^{18},𝐒^{59})=0.3`$, but $`J(𝐒^{59},𝐒^{18})=0.2`$. For all times and both values of $`\theta `$, the distribution for the random data is a sharply pointed, symmetrical curve peaking at $`J=0`$. This makes sense because there is no bias in the ratio of positive to negative links when the links are assigned to the “bare” network at $`t=0`$.

For reasons of clarity, the simulation results are only shown for primal and late time. Clearly, a significant change takes place for high $`\theta `$ between $`t=0`$ and primal time. Some weight is taken in the fall of the peak at $`J=0`$ and the drop in negative J values, and redistributed into positive strengths i.e. the curve shifts right. This comprises a significant shift in the probability density. The move from primal to late time is smaller — but still noticeable — since the large number of reorganisations of genotype space in the early generations drops to occasional punctuation of q-ESSs later in the run. (Typically, there are only one or two transitions from early time onwards.) Despite this, the curve continues to drift to the right. On first inspection, the low $`\theta `$ runs seem to have changed dramatically from the initial configuration. However, nothing particularly interesting is happening here: it is simply an effect of the structure of clusters in the low $`\theta `$ space and is explained below.

### d Clustering

The indirect connectivity or clustering (how sites are linked to each other through other sites) is another useful network measure. For high $`\theta `$ we find that at any given time, all occupied sites in genotype space belong to one and the same cluster. Thus the cluster size for high $`\theta `$ simply follows the diversity. In contrast, we observe the formation of distinct clusters for low $`\theta `$. The rest of this section will deal solely with low $`\theta `$.

The overall structure of the clusters does not seem to change much with time. This is the first indication that the clustering is not an evolving property of the network. As would be expected, one-clusters are transient. They are born on a new site as mutants from a parent but are isolated from other sites and so are extremely unlikely to reproduce. (Since $`\mu =0.01`$ and the average total population is about 2700, $`p_{off}10^{12}p_{kill}=0.2`$ so an isolated site is much more likely to be killed than multiply when chosen.) These sites are simply flashing in and out of existence.

Simulations indicate that the building blocks of larger groups are two-clusters. These tend to be two very old sites that have mutually positive links. Large clusters are formed mainly from very old two-clusters joined together by a mutant. The continual background of mutants flitting in and out of the network plugs these building blocks together. However, the entire cluster is rarely long lived, whereas the two-clusters are formed early in any particular run, quickly build up their population and are very persistent since their occupation is high.

Clusters do indeed generally increase in size with time. There are, however, large fluctuations in the record size which gives an indication of how unstable these large clusters are, see figure 3. The largest recorded cluster in any run at any time contained 281 sites. It is revealing to compare the results from the null model, where the maximum cluster size is much smaller but just as variable. When individuals are thrown down at random, two-clusters are no longer the building blocks of the large clusters and any long string of connected sites is determined purely by chance and hence the biggest cluster will always be smaller than that produced by the dynamics. The temporary nature of the large clusters is further borne out by time and ensemble averaging the cluster sizes. The number of clusters of a particular size $`S`$ is stored at intervals of 5000 generations from early to late time for each of the 500 runs and the time and ensemble average is then calculated. As expected, there are many one-clusters and fewer large clusters.

The distribution follows the functional form $`n_ss^{5/2}e^{(pp_c)^2s}`$ anticipated for the cluster size distribution on a random graph of $`D`$ ($`195`$) nodes. (See equation (36) in \[Albert and Barabási, 2002\].) The percolation threshold $`\frac{1}{D}`$ is very close to the considered connectivity $`\theta =0.005`$. A comparison with the random data shows that this scale-independent distribution is not due to the dynamics of the system, the only difference being the appearance of larger record clusters in the simulation, as shown in figure 3. This is perhaps the most compelling piece of evidence that the low $`\theta `$ regime does not show any emergent structure. We also ran simulations for very low $`\theta `$ ($`0.001`$) and found that the cluster sizes were exponentially distributed as would be expected below the percolation threshold.

Figure 2 (low $`\theta `$) can now be easily explained. Unconnected sites die extremely quickly in the first few generations leaving behind two-clusters and other sites with positive interactions. The slight increase in sites with $`J>0`$ for late time is caused by well established positive-positive two-clusters. So what looked like an interesting result initially proves to be due to the fairly constant microscopic structure of the network.

### e Species abundance

The Species Abundance Distribution or SAD is important in characterising ecosystems. It is the proportion of species that contain $`\rho `$ individuals. We define a species as one site in genotype space. Ideally, we would like to use a coarse-grained definition more likely to reflect real ecologies, where species are defined as groups of points in genotype space echoing the genotypic cluster species definition introduced by Mallet \[Mallet, 1995\]. Since the maximum number of genotypes in our model is only around $`10^6`$ anyway, the single site species approach is more appropriate. We have been able to extend the initial results obtained in \[Hall et al., 2002\] and can consider the evolution of the SAD for high and low $`\theta `$ integrated across all 500 runs, as seen in figure 4. The larger ensembles allow enough statistics for illuminating conclusions to be drawn. Note that the null model is absent since when individuals are sprinkled randomly across the living sites, there is no tendency for accumulation on any particular site, so the individuals follow a multinomial distribution.

The key result of this paper is that only high $`\theta `$ leads to a SAD similar to those observed in nature. Low $`\theta `$ is skewed by its heavily populated two-clusters. The plots for high $`\theta `$ show the log-normal form observed in many real ecosystems and in other ecological models, see \[McKane et al., 2000, Hubbell, 2001\]. They appear to become more log-normal as time increases with the dip between four and eight individuals falling, even though the diversity is rising. Hence, the SAD is evolving. From this, it seems that the high $`\theta `$ case structures itself more like a real ecosystem than low $`\theta `$, whose SAD develops a sharper peak as the two-clusters become densely occupied. The single cluster of highly interdependent genomes produces a reasonable SAD that cannot be formed by patches of isolated clusters.

Thus the abstract parameter $`\theta `$, which cannot be measured in a simple way in real systems, is directly linked to the easily observed SAD. We recall that low values of $`\theta `$ correspond to a world in which different species, or types, are able to influence only a small number of other species. High values of $`\theta `$ correspond to the situation where different types may have an impact on the vitality of a large number of other species.

The initial descent in both curves from the global peak at $`\rho =1`$ is due to the large number of sites with only one occupant. In nature, sampling difficulties would mean that these sites would not be detected so this first aspect is not seen in observed SADs. (It is particularly marked for our model since we use each site as one species and do not coarse-grain.) But the second peak does correspond well to results from the field, though it should be pointed out that the proportion of all sites with more than two individuals is only about $`30\%`$ in each case. However, this is sufficient to detect the evolution of the SAD.

We note that a recent study of a simplified version of the Tangled Nature model by Rikvold and Zia \[Rikvold and Zia, 2003, Rikvold and Zia,\] found no temporal evolution of the statistics of the model. The reason for this may be that they use a relatively short genome length $`L=13`$ together with a very substantial simulation time of order $`10^7`$ generations. We have observed previously that the time to reach a stationary state explodes with genome length \[Christensen et al., 2002\].

### f Neutral and niche theory

There has recently been much interest in the neutral theory of biodiversity \[Hubbell, 2001\], \[Bell, 2001\]. Despite making assumptions that are anathema to traditional niche models (all individuals are the same and adaptations to specific environmental niches are essentially unimportant) it has been successful in making predictions about real world ecology — although its effectiveness in modelling the species abundance has recently been called into question \[McGill, 2003\].

At $`t=0`$, the Tangled Nature model is neutral as all individuals are the same. However, the dynamics immediately breaks this neutrality as configurations are spontaneously generated. Once individuals become differentiated, interactions matter and the evolution is better described by niche-theory — although $`\mu `$ and $`p_{kill}`$ remain neutral. Unlike the models in \[Hubbell, 2001\], we have no spatial aspect: we deal with only one large metacommunity as opposed to many local communities aggregating to form the metacommunity.

The only measure in our model considered by the neutral theory is the species abundance, which we find takes an approximate log-normal form. The shape predicted by neutrality, the zero-sum multinomial (ZSM) distribution, is quite similar to the log-normal except that the ZSM has a long right tail and is much harder to calculate \[McGill, 2003\]. To detect whether our distributions are closer to the ZSM or the log-normal would be computationally prohibitive as the genome length $`L`$ would need to be much larger. Perhaps in the future, models like Tangled Nature could be used to investigate the relative importance of niche and neutral effects.

## Discussion

Our most important results are that temporal evolution of the network properties of an ecosystem and a realistic form for the species abundance are only seen if the genotype space is well connected. This is interpreted here as meaning that an occupied genotype is likely to interact with many other (potentially occupied) genotypes. No evolution at the level of ecosystems can occur in a world where most possible genotypes are inert, i.e. whether they are present or not will have very little influence on other organisms. It is easy to overlook the importance of the entire network of interactions when dealing with small communities of organisms on a macroscopic scale, but easier to visualise with colonies of billions of bacteria.

We suggest that this observation can be used to gain insight into the potential underlying connectivity between biota. Imagine two microbial evolution experiments. In one case, the microbial ecosystem evolves towards an interwoven or entangled ecology. In the other, little evolution is observed in the structure of the ecological properties of the microbial community. One might, according to the result from our model, anticipate that the first system consists of microbes from a part of genotype space in which types influence each other, whereas the second system consists of genotypes from a region of space consisting of mainly inert organisms.

From our results, it is tempting to speculate that the observed degree of diversity, complexity and adaptation of living matter may be directly related to a high level of interdependence between organisms. Thus Darwin’s entangled bank may be a useful image to keep in mind when studying the evolution of large collections of individuals.

We are grateful to Gunnar Pruessner for extensive help with the development of the parallelised code that enabled us to probe the model at much deeper timescales and for broader ensembles than had been possible before. We wish to thank Andy Thomas for his fantastic technical support. Without his help and dedication, this project would not have been possible. We are indebted to Dan Moore, Brendan Maguire and Phil Mayers for their continuous support. We thank Albert Diaz-Guilera for inspiring discussions and Ed Johnson for reading the manuscript. Paul Anderson thanks EPSRC for research funding.


text:
# Pion re-scattering in 𝜋⁰ production near threshold

## 1 Introduction

Due to isospin suppression of the otherwise dominant low-energy isovector Weinberg-Tomosawa $`\pi `$N term in the re-scattering diagram, and the negative interference between the remaining impulse and isoscalar pion re-scattering terms, the empirical data for $`pppp\pi ^0`$ near threshold is only explained by phenomenological non-pionic, short-range, two-body mechanisms, or alternatively by an off-shell extrapolation of the $`\pi N`$ amplitude. The high quality data for $`pppp\pi ^0`$ becomes therefore specially interesting by allowing to establish the importance of the short-range mechanisms, which are difficult to constrain: they are subsumed in the low energy constants appearing also in the two- and three-nucleon potentials, but so far these constants have not yet been precisely determined.

Nevertheless, any conclusion to be read off from the $`\pi ^0`$ production data is only meaningful and quantitative provided that the calculation of the re-scattering diagram is under absolute control. This is not the case in calculations performed till now, where approximations at the level of the energy integration of the corresponding Feynman diagram were considered. Namely, non-relativistic reductions of the Feynman $`\pi `$-exchange diagram were done, through choices for the energy of the exchanged pion, both for its propagator and for the $`\pi N\pi N`$ amplitude at the re-scattering vertex.

This work investigates the validity of the mostly used approximations. It generalizes the work of Refs. which considers a toy model for scalar particles and interactions. Our calculation employs a physical model for nucleons and pions, with a pseudo-vector coupling for the $`\pi NN`$ vertex; the $`\chi `$Pt $`\pi N\pi N`$ re-scattering amplitude and the Bonn B potential for the nucleon-nucleon interaction in the final state.

## 2 From the Feynman diagram to DWBA

Starting with the Feynman diagram, the energy integration in the energy $`Q_0^{}`$ of the exchanged pion was done after a partial fraction decomposition, which isolates the poles of the pion propagator. This way we separated the DWBA amplitude from the stretched boxes (where two exchanged particles may be in flight simultaneously) contribution. Then,

$$_{DWBA}=\frac{1}{2}\frac{d^3q^{}}{\left(2\pi \right)^3}\left[V\left(\omega _\pi \right)G_\pi \frac{\left(\omega _1\omega _2\right)+E_\pi }{\omega _\pi }\right]\frac{1}{\left(E_1+E_2E_\pi \omega _1\omega _2\right)}T_{NN}^{FSI}$$
(1)
is the exact expression for the DWBA amplitude, where $`T`$ stands for the transition-matrix of the final-state interaction and $`V\left(\omega _\pi \right)`$ is the product of the $`\pi N\pi N`$ amplitude with the $`\pi NN`$ vertex. The pion propagator turned to be exactly given by

$$G_\pi =\frac{1}{\left[\frac{\omega _1\omega _2}{2}+\frac{E_\pi }{2}\right]^2\left[\left(E_{tot}E\frac{E_\pi }{2}\right)\frac{\omega _1+\omega _2}{2}\omega _\pi \right]^2},$$
(2)
Thus, Eq.(1) is taken as the reference result, in order to investigate the effect of the most common approximations hitherto used for the pion propagator in a DWBA final-state calculation. These approximations correspond to the following three different choices:

$$\begin{array}{cccccc}G_\pi ^{fk}\hfill & \hfill & \frac{1}{\left(\frac{m_\pi }{2}\right)^2\omega _\pi ^2}\hfill & & & \mathrm{fixed}\mathrm{kinematics}\hfill \\ G_\pi ^{on}\hfill & \hfill & \frac{1}{\left(E\omega _2\right)^2\omega _\pi ^2}\hfill & & & \mathrm{on}\mathrm{shell}\hfill \\ G_\pi ^{st}\hfill & \hfill & \frac{1}{\omega _\pi ^2}\hfill & & & \mathrm{static}\mathrm{approximation}\hfill \end{array}$$
(3)
The “fixed kinematics” approximation “freezes” the energy for the exchanged pion as the difference between the two on-mass-shell energies of the nucleon, before and after re-scattering, at $`m_\pi /2`$, its value at threshold; the “on-shell approximation” considers for the energy of the pion the difference between the same on-mass-shell energies of the nucleon, but it varies with the energy available for the production process, and is not frozen at the threshold point. Naturally, the two approximations coincide at threshold and the deviation between them increases with energy. The “static approximation” makes the pion exchange instantaneous and therefore neglects energy transfer. It is part of the usual non-relativistic approximation for exchange Feynman diagrams.

## 3 Results and Conclusions

For the toy model case of scalar particles and scalar interactions, we verified the dominance of the DWBA amplitude over the stretched boxes amplitude, as obtained in Ref.. Furthermore, our calculations show that the DWBA keeps being dominant, as seen on the left panel of Fig.1, even in a more pronounced way for the physical case considered here.

We found also that within the scalar toy model all the approximations for the pion energy taken at the $`\pi N\pi N`$ re-scattering amplitude overestimate the cross section, as found in Refs.. However, on the right panel of Fig.1, where we describe the nucleon-nucleon interaction by the Bonn B potential T-matrix, only the on-shell $`G^{on}`$ approximation to the exact pion propagator gives a larger cross section (on the right panel of Fig.1 this curve practically coincides with the reference result). The choice for the energy in the pion propagator is not very decisive, justifying the usual low-energy static or instantaneous approximation for exchange Feynman diagrams. However, the choice for the energy of the exchanged pion for the re-scattering vertex, as prescribed from the 4-dimensional Feynman diagram, is crucial for the cross section strength. As shown on the right panel of Fig. 1, the fixed kinematics and the on-shell prescriptions for the re-scattering vertex are not suitable for combination with an energy independent $`NN`$ potential.

Both for the final- and initial-state interaction, our results show that the DWBA formalism is quite adequate at threshold since this part of the full amplitude is clearly dominant over the stretched boxes. Also,the effect of the usual choices for the $`\pi N`$ re-scattering energy, which is not fixed by a non-relativistic formalism, can be significant.

In order to extract quantitatively from the data the unknown strength of the short-range mechanisms for the process $`pppp\pi ^0`$, one has to use for the pion exchange diagram the reference amplitudes. The latter were obtained as non-relativistic reductions of the corresponding Feynman diagrams for the final- and initial-state interactions, respectively.