text:
# Extremal Optimization for Graph Partitioning

## I Introduction

Optimizing a system of many variables with respect to some cost function is a task frequently encountered in physics. The determination of ground-state configurations in disordered materials MPV ; Grest ; D+S ; Disorder  and of fast-folding protein conformations Proteins  are but two examples. In cases where the relation between individual components of the system is frustrated Toulouse , the cost function often exhibits a complex “landscape” cnls  in configuration space, posing challenges to neighborhood search procedures. Indeed, for growing system size the cost function may exhibit a rapidly increasing number of unrelated local extrema, separated by sizable barriers that can make the search for the exact optimal solution unreasonably costly. It is of great importance to develop fast and reliable approximation methods for finding optimal or acceptable near-optimal solutions with high probability.

In recent papers we have introduced a new method, called extremal optimization (EO), to tackle such hard optimization problems BoPe1 ; GECCO . EO is a method based on the dynamics of non-equilibrium processes and in particular those exhibiting self-organized criticality BTW , where better solutions emerge dynamically without the need for parameter tuning. Previously, we have discussed the basic EO algorithm, its origin, and its performance compared with other methods. We have demonstrated that the algorithm can be adapted to a wide variety of NP-hard problems PPSN\_CISE . We have shown that for the graph partitioning problem, a simple implementation of EO yields state-of-the-art solutions, even for systems of $`N>10^5`$ variables BoPe1 . For large graphs of low connectivity, EO has been shown to be faster than genetic algorithms Holland  and more accurate than simulated annealing Science , two other widely applied methods. A numerical study EOperc  has shown that EO’s performance relative to simulated annealing is particularly strong in the neighborhood of phase transitions, “where the really hard problems are” Cheeseman . In fact, preliminary studies of the phase transition in the 3-coloring problem PT3COL  as well as studies of ground state configurations in spin glasses EO\_PRL ; D+S  suggest that EO may become a useful tool in the exploration of low-temperature properties of disordered systems.

In the present work we focus on the intrinsic features of the method, by investigating its average performance. For this purpose, we have performed an extensive numerical study of EO on the graph bipartitioning problem. We have considered various kinds of graph ensembles, both with geometric and with random structure, for an increasing number of vertices $`N`$. The results show that for random graphs, EO converges towards the optimal configuration in a power-law manner, typically requiring no more than $`O(N)`$ update steps. For geometric graphs the averaged large-$`N`$ results are less convincing, but if we instead focus on the best out of several trials, near-optimal results emerge. Our implementation of EO has one single tunable parameter, and we find a simple relation to estimate that parameter given the allowed runtime and system size. Many of our numerical results here have been independently confirmed by J. Dall Dall .

The paper is organized as follows. In Sec. II we introduce the graph bipartitioning problem, and in Sec. III we describe the extremal optimization algorithm. Sec. IV deals in detail with our numerical results. In Sec. V we conclude with an outlook on future work.

## II Graph Bipartitioning

### II.1 Definition

The graph bipartitioning problem (GBP) is easy to formulate. Take $`N`$ vertices, where $`N`$ is an even number, and where certain of the vertex pairs are connected by an edge. Then divide the vertices into two sets of equal measure $`N/2`$ such that the number of edges connecting both sets, the “cutsize” $`m`$, is minimized. The global constraint of an equal division of vertices places the GBP among the hardest problems in combinatorial optimization, since determining the exact solution with certainty would in general require a computational effort growing faster than any power of $`N`$ NP\_Hard . It is thus important to find “heuristic” methods that can obtain good approximate solutions in polynomial time. Typical examples of applications of graph partitioning are the design of integrated circuits (VLSI) A+K  and the partitioning of sparse matrices HL .

The general description of a graph in the previous paragraph is usually cast in more specific terms, defining an ensemble of graphs with certain characteristic. These characteristics can affect the optimization problem drastically, and often reflect real-world desiderata such as the geometric lay-out of circuits or the random interconnections in matrices. Therefore, let us consider a variety of different graph ensembles, some random and some geometric in structure.

### II.2 Classes of graphs studied

One class of graphs that has been studied extensively is that of random graphs without geometric structure RandGraph . Here, edges between any two vertices are taken to exist with probability $`p`$: on the average, an instance has a total of $`E=pN(N1)/2`$ vertices and the mean connectivity per vertex is $`\alpha =p(N1)`$. Following standard terminology we refer to graphs of this sort as the ensemble of random graphs, even though the other classes of graphs we consider all have stochastic properties as well.

Another often-studied class of graphs without geometric structure is generated by fixing the number of connections $`\alpha `$ at each vertex, but with random connections between these vertices W+S ; Banavar . In particular, we consider here the case where $`\alpha =3`$: the ensemble of trivalent graphs, randomly connected graphs with exactly three edges originating from each vertex.

The third class we consider is an ensemble with geometric structure, where the vertices are situated on a cubic lattice. Edges are placed so as to connect some (but not all) nearest neighbors on the lattice: a ratio $`x`$ of the total number of nearest-neighboring pairs are occupied by an edge, and those edges are distributed at random over the possible pairs. For a cubic lattice, the average connectivity is then given by $`\alpha =6x`$. This class of graphs corresponds to a dilute ferromagnet, where each lattice site holds a $`\pm `$-spin and some (but not all) nearest-neighboring spins possess a coupling of unit strength. Here, the GBP amounts to the equal partitioning of $`+`$ and $``$ spins while minimizing the interface between the two types M+P , or simply finding the ground state under fixed (zero) magnetization. We thus refer to this class as the ensemble of ferromagnetic graphs.

The final class we consider is that of geometric graphs specified by $`N`$ randomly distributed vertices in the 2-dimensional unit square, where we place edges between all pairs whose two vertices are separated by a distance of no more than $`d`$ JohnsonGBP . The average connectivity is then given by $`\alpha =N\pi d^2`$. The GBP on this class of graphs has the advantage of a simple visual representation, shown in Fig. 1. Again following standard terminology, we refer to this class simply as the ensemble of geometric graphs.

It is known that graphs without geometric structure, such as those in the first two classes, are typically easier to optimize than those with geometric structure, such as those in the final two classes JohnsonGBP . The characteristics of the GBP for non-geometric and geometric graphs at low connectivity appear to be very different, due to the dominance of long loops in the former and short loops in the latter. The ensemble of random graphs has a structure that is locally tree-like, allowing for a mean-field treatment that yields some exact results M+P . By contrast, the ensemble of geometric graphs corresponds to continuum percolation of “soft” (overlapping) circles, for which precise numerical results exist Balberg .

Each of the graph ensembles that we consider is characterized by a control parameter, the average connectivity $`\alpha `$. The difficulty of the optimization problem for each type varies significantly with $`\alpha `$. In this study we focus on sparse graphs for which $`\alpha `$ is kept constant, independent of $`N`$. Sparse graphs have very different properties from the dense graphs studied by Fu and Anderson F+A . These sparse graphs are generally considered to pose the most difficult partitioning problems, and extremal optimization (EO) is particularly competitive in this regime EOperc . In order to facilitate our average performance study, we fix $`\alpha `$ to a given value on each ensemble. For random graphs, where the connectivity varies between vertices according to a Poisson distribution, let $`\alpha =p(N1)=2`$ (and so $`p1/N`$). For trivalent graphs, by construction $`\alpha =3`$. For ferromagnetic graphs, let $`\alpha =6x=2`$. For geometric graphs, let $`\alpha =N\pi d^2=6`$. In all of these cases, the connectivity is chosen to be just above the phase transition at $`\alpha _{\mathrm{crit}}`$, below which the cutsize $`m`$ almost always vanishes EOperc . These critical regions are especially interesting because they have been conjectured to coincide with the hardest-to-solve instances in many combinatorial optimization problems Cheeseman ; PhaseTrans .

Finally, in light of the numerous comparisons in the physics literature between the GBP and the problem of finding ground states of spin glasses MPV , it is important to point out the main difference. This is highlighted by the ensemble of ferromagnetic graphs. Since couplings between spins are purely ferromagnetic, all connected spins invariably would like to be in the same state; there is no possibility of local frustration. Frustration in the GBP merely arises from the global constraint of an equal partition, forcing spins along an interface to attain an unfavorable state (see Fig. 1). All other spins reside in bulk regions where they can maintain the same state as their neighbors. In a spin glass, on the other hand, couplings can be both ferromagnetic and anti-ferromagnetic. Spins everywhere have to compromise according to conflicting conditions imposed by their neighbors; frustration is local rather than global.

### II.3 Basic scaling arguments

If we neglect the fact that the structure of these sparse graphs is that of percolation clusters, we can obtain some elementary insights into the expected scaling behavior of the optimal cutsize with increasing size $`N`$, $`mN^{1/\nu }`$. For graphs without geometric structure (random graph ensemble and trivalent graph ensemble), one can expect that the cutsize should grow linearly in $`N`$, i.e., $`\nu =1`$. Indeed, this argument can be made rigorous for arbitrary connectivity $`\alpha `$. Extremal optimization performs very well on these graphs, and previous numerical studies using EO all give $`\nu 1`$ EOperc .

For graphs with geometric structure (ferromagnetic graph ensemble and geometric graph ensemble), the value of $`\nu `$ is less clear. We can approximate a graph with a $`d`$-dimensional geometric structure as a hyper-cubic lattice of length $`L=N^{1/d}`$, where the lattice sites are the vertices of the graph and the nearest-neighbor bonds are the edges, of which only a finite fraction are occupied. There are thus about $`EN`$ edges in the graph. To partition the graph, we are roughly looking for a $`(d1)`$-dimensional hyper-plane cutting the graph into two equal-sized sets of vertices. Such an interface between the partitions would cut $`L^{d1}`$ bonds, and thus $`N^{11/d}`$ edges. Following this argument, the 3-d ferromagnetic graphs should have a cutsize scaling with $`N^{2/3}`$ and the 2-d geometric graphs should have a cutsize scaling with $`N^{1/2}`$.

However, while this may the case for a typical partition of the graph, it may not be the case for an optimal partition. The interface for an optimal cut of a sparse graph could well be much rougher than our argument suggests, taking advantage of large voids between clusters of connected vertices. The number of cut edges would then be much below the estimate based on assuming a flat interface, making $`1/\nu <11/d`$. In our previous studies using EO, we found $`1/\nu 0.75\pm 0.05`$ for ferromagnetic graphs and $`1/\nu 0.6\pm 0.1`$ for geometric graphs EOperc , i.e., above the upper bound, and our newer results do not improve on these (seen later in Fig. 6). This could indicate that the actual values are close to the upper bound, but also that for graphs with geometric structure EO fails to find the optima on instances of increasing size.

Similar behavior has been observed with other local search methods JohnsonGBP , reflecting the fact that sparse geometric graphs generally pose a much greater challenge than do sparse random graphs. In contrast, a heuristic such as METIS METIS , a hierarchical decomposition scheme for partitioning problems, works better for geometric graphs than for random graphs unpublished . METIS performs particularly well for sparse geometric graphs, and typically produces better results than EO for $`\alpha =6`$. Furthermore, if speed is the dominant requirement, METIS is superior to any local search method by at least a factor of $`N`$. But for random graphs at $`\alpha =2`$ or the trivalent graphs, METIS’ results are poor compared to EO’s, and for all type of graphs METIS’ performance deteriorates with increasing connectivity.

## III Extremal Optimization Algorithm

### III.1 Motivation

The extremal optimization method originates from insights into the dynamics of non-equilibrium critical phenomena. In particular, it is modeled after the Bak-Sneppen mechanism BS , which was introduced to describe the dynamics of co-evolving species.

Species in the Bak-Sneppen model are located on the sites of a lattice, and each one has a “fitness” represented by a value between 0 and 1. At each update step, the smallest value (representing the most poorly adapted species) is discarded and replaced by a new value drawn randomly from a flat distribution on $`[0,1]`$. Without any interactions, all the fitnesses in the system would eventually approach 1. But obvious interdependencies between species provide constraints for balancing the system’s overall condition with that of its members: the change in fitness of one species impacts the fitness of an interrelated species. Therefore, at each update step, the Bak-Sneppen model replaces the fitness values on the sites neighboring the smallest value with new random numbers as well. No explicit definition is provided for the mechanism by which these neighboring species are related. Yet after a certain number of updates, the system organizes itself into a highly correlated state known as self-organized criticality (SOC) BTW . In that state, almost all species have reached a fitness above a certain threshold. But these species merely possess what is called punctuated equilibrium G+E : since only one’s weakened neighbor can undermine one’s own fitness, long periods of “stasis”, with a fitness above the threshold, are inevitably punctuated by bursts of activity. This co-evolutionary activity cascades in a chain reaction (“avalanche”) through the system. These fluctuations can involve any number of species, up to the system size, making any possible configuration accessible. Due to the extremal nature of the update, however, the system as a whole will always return to states in which practically all species are above threshold.

In the Bak-Sneppen model, the high degree of adaptation of most species is obtained by the elimination of poorly adapted ones rather than by a particular “engineering” of better ones. While such dynamics might not lead to as optimal a solution as could be engineered under specific circumstances, it provides near-optimal solutions with a high degree of latency for a rapid adaptation response to changes in the resources that drive the system. A similar mechanism, based on the Bak-Sneppen model, has recently been proposed to describe adaptive learning in the brain C+B .

### III.2 Algorithm description

Inspired by the Bak-Sneppen mechanism, we have devised the EO algorithm with the goal of accessing near-optimal configurations for hard optimization problems using a minimum of external control. Previously, we have demonstrated that the EO algorithm is applicable to a wide variety of problems EO\_PRL ; PPSN\_CISE . Here, we focus on its implementation for the GBP.

In the GBP, EO BoPe1  considers each vertex of a graph as an individual variable with its own fitness parameter. It assigns to each vertex $`i`$ a “fitness”

$`\lambda _i=g_i/(g_i+b_i),`$ (1)
where $`g_i`$ is the number of “good” edges connecting $`i`$ to other vertices within its same set, and $`b_i`$ is the number of and “bad” edges connecting $`i`$ to vertices across the partition. (For unconnected vertices we fix $`\lambda _i=1`$.) Note that vertex $`i`$ has an individual connectivity of $`\alpha _i=g_i+b_i`$, while the overall mean connectivity of a graph is given by $`\alpha =_i\alpha _i/N`$ and the cutsize of a configuration is given by $`m=_ib_i/2`$.

At all times an ordered list is maintained, in the form of a permutation $`\mathrm{\Pi }`$ of the vertex labels $`i`$ such that

$`\lambda _{\mathrm{\Pi }(1)}\lambda _{\mathrm{\Pi }(2)}\mathrm{}\lambda _{\mathrm{\Pi }(N)},`$ (2)
and $`i=\mathrm{\Pi }(k)`$ is the label of the $`k`$th ranked vertex in the list.

Feasible configurations have $`N/2`$ vertices in one set and $`N/2`$ in the other. To define a local search of the configuration space, we must define a “neighborhood” for each configuration within this space Reeves . The simplest such neighborhood for the GBP is given by an exchange of (any) two spins between the sets. With this exchange at each update we can search the configuration space by moving from the current configuration to a neighboring one. In close analogy with the Bak-Sneppen mechanism, our original parameter-free implementation of EO merely swapped the vertex with the worst fitness, $`\mathrm{\Pi }(1)`$, with a random vertex from the opposite set BoPe1 . Over the course of a run with $`t_{\mathrm{max}}`$ update steps, the cutsize of the configurations explored varies widely, since each update can result in better or worse fitnesses. Proceeding as with the gap-equation in the Bak-Sneppen model PMB , we can define a function $`m(t)`$ to be to be the cutsize of the best configuration seen during this run up to time $`t`$. By construction $`m(t)`$ is monotonically decreasing, and $`m(t_{\mathrm{max}})`$ is the output of a single run of the EO-algorithm.

We find that somewhat improved results are obtained with the following one-parameter implementation of EO. Draw two integers, $`1k_1,k_2N`$, from a probability distribution

$`P(k)k^\tau ,(1kN),`$ (3)
on each update, for some $`\tau `$. Then pick the vertices $`i_1=\mathrm{\Pi }(k_1)`$ and $`i_2=\mathrm{\Pi }(k_2)`$ from the rank-ordered list of fitnesses in Eq. (2). (We repeatedly draw $`k_2`$ until we obtain a vertex in the opposite set from $`k_1`$.) Let vertices $`i_1`$ and $`i_2`$ exchange sets no matter what the resulting new cutsize may be. Then, reevaluate the fitnesses $`\lambda `$ for $`i_1`$, $`i_2`$, and all vertices they are connected to ($`2\alpha `$ on average). Finally, reorder the ranked list of $`\lambda `$’s according to Eq. (2), and start the process over again. Repeat this procedure for a number of update steps per run that is linear in system size, $`t_{\mathrm{max}}=AN`$, and store the best result generated along the way. Note that no scales to limit fluctuations are introduced into the process, since the selection follows the scale-free power-law distribution $`P(k)`$ in Eq. (3) and since — unlike in heat bath methods — all moves are accepted. Instead of a global cost function, the rank-ordered list of fitnesses provides the information about optimal configurations. This information emerges in a self-organized manner merely by selecting with a bias against badly adapted vertices, rather than ever “breeding” better ones.

### III.3 Discussion

#### III.3.1 Definition of fitness

We now discuss some of the finer details of the algorithm. First of all, we stress that we use the term “fitness” in the sense of the Bak-Sneppen model, in marked contrast to its meaning in genetic algorithms. Genetic algorithms consider a population of configurations and assign a fitness value to an entire configuration. EO works with only a single configuration and makes local updates to individual variables within that configuration. Thus, it is important to reiterate that EO assigns a fitness $`\lambda _i`$ to each of the system’s $`N`$ variables, rather than to the system as a whole.

While the definition of fitness in Eq. (1) for the graph partitioning problem seems natural, it is by no means unique. In fact, in general the sum of the fitnesses does not even represent the cost function we set out to optimize, because each fitness is locally normalized by the total number of edges touching that vertex. It may seem more appropriate to define fitness instead as $`\lambda _i=g_i`$, the number of “good” connections at a vertex, or else as $`\lambda _i=b_i`$, which amounts to penalizing a vertex for its number of “bad” connections. In both cases, the sum of all the fitnesses is indeed linearly related to the actual cost function. The first of these choices leads to terrible results, since almost all vertices in near-optimal configurations have only good edges, and so in most cases $`g_i`$ is simply equal to the connectivity of the vertex. The second choice does lead to a viable optimization procedure and one that is easily generalizable to other problems, as we have shown elsewhere PPSN\_CISE . But for the GBP, we find that the results from that fitness definition are of poorer quality than those we present in this paper. It appears productive to consider all vertices in the GBP on an equal footing by normalizing their fitnesses by their connectivity as in Eq. (1), so that $`\lambda _i[0,1]`$. The fact that each vertex’s pursuit towards a better fitness simultaneously minimizes its own contribution to the total cost function ensures that EO always returns sufficiently close to actual minima of the cost function.

Note that ambiguities similar to that of the fitness definition also occur for other optimization methods. In general, there is usually a large variety of different neighborhoods to choose from. Furthermore, to facilitate a local neighborhood search, cost functions often have to be amended to contain penalty terms. It has long been known JohnsonGBP  that simulated annealing for the GBP only becomes effective when one allows the balanced partition constraint to be violated, using an extra term in the cost function to represent unbalanced partitions in the cost function. Controlling this penalty term requires an additional parameter and additional tuning, which EO avoids.

#### III.3.2 The parameter $`\tau `$

Indeed, there is only one parameter, the exponent $`\tau `$ in the probability distribution in Eq. (3), governing the update process and consequently the performance of EO. It is intuitive that a value of $`\tau `$ should exist that optimizes EO’s average-case performance. If $`\tau `$ is too small, vertices would be picked purely at random with no gradient towards any good partitions. If $`\tau `$ is too large, only a small number of vertices with particularly bad fitness would be chosen over and over again, confining the system to a poor local optimum. Fortunately, we can derive an asymptotic relation that estimates a suitable value for $`\tau `$ as a function of the allowed runtime and the system size $`N`$. The argument is actually independent of the optimization problem under consideration, and is based merely on the probability distribution in Eq. (3) and the ergodicity properties that arise from it.

We have observed numerically that the choice of an optimal $`\tau `$ coincides with the transition of the EO algorithm from ergodic to non-ergodic behavior. But what do we mean by “ergodic” behavior, when we are not in an equilibrium situation? Consider the rank-ordered list of fitnesses in Eq. (2), from which we choose the individual variables to be updated. If $`\tau =0`$, we choose variables at random and can reach every possible configuration of the system with equal probability. EO’s behavior is then perfectly ergodic. Conversely, if $`\tau `$ is very large, there will be at least a few variables that may never be touched in a finite runtime $`t`$, because they are already sufficiently fit and high in rank $`k`$. Hence, if there are configurations of the system that can only be reached by altering these variables first, EO will never explore them and accordingly is non-ergodic. Of course, for any finite $`\tau `$, different configurations will be explored by EO with different probabilities. But we argue that phenomenologically, we may describe EO’s behavior as ergodic provided every variable, and hence every rank on the list, gets selected at least once during a single run. There will be a value of $`\tau `$ at which certain ranks, and therefore certain variables, will no longer be selected with finite probability during a given runtime. We find that this value of $`\tau `$ at the transition to non-ergodic behavior corresponds roughly with the value at which EO displays its best performance. Clearly, this makes the choice of $`\tau `$ dependent on the runtime and on the system size $`N`$.

Assuming that this coincidence indicates a causal relation between the ergodic transition and optimal performance, we can estimate the optimal $`\tau `$ in terms of runtime $`t`$ and size $`N`$. EO uses a runtime $`t_{\mathrm{max}}=AN`$, where $`A`$ is a constant, probably much larger than 1 but much smaller than $`N`$. (For a justification of the runtime scaling linearly in $`N`$, see Sec. IV.3.2.) We argue that we are at the “edge of ergodicity” when during $`AN`$ update steps we have a chance of selecting even the highest rank in EO’s fitness list, $`k=N`$, about once:

$`P(k=N)AN1.`$ (4)
With the choice of the power-law distribution for $`P(k)`$ in Eq. (3), we obtain

$`(\tau 1)N^\tau AN1,(N\mathrm{}),`$ (5)
where the factor of $`\tau 1`$ arises from the norm of $`P(k)`$. Asymptotically, we find

$`\tau 1+{\displaystyle \frac{\mathrm{log}\left(A/\mathrm{log}N\right)}{\mathrm{log}N}}(N\mathrm{},1AN).`$ (6)
Of course, large higher-order corrections may exist, and there may well be deviations in the optimal $`\tau `$ among different classes of graphs since this argument does not take into account graph structure or even the problem at hand. Nevertheless, Eq. (6) gives a qualitative understanding of how to choose $`\tau `$, indicating for instance that it varies very slowly with $`N`$ and $`A`$ but will most likely be significantly larger than its asymptotic value of unity. Not surprisingly, with the numerical values $`A10^2`$ and $`N10^4`$ used in previous studies, we typically have observed optimal performance for $`\tau 1.31.6`$ (see also Ref. Dall ). Our numerical study of $`\tau `$ is discussed in Sec. IV.2 below. (We note that in this study we often use runtimes with $`A>N`$ to probe the extreme long-time convergence behavior of EO. In that case, Eq. (6) can not be expected to apply. Yet, the optimal value of $`\tau `$ still increases with $`A`$, as will be seen in the numerical results in Sec. IV.2 and Fig. 3a.)

#### III.3.3 Efficient ranking of the fitness values

Strictly speaking, the EO-algorithm as we have described it has a cost proportional to $`2\alpha N^2\mathrm{log}N`$ per run. One factor of $`N`$ arises simply from the fact that the runtime, i.e., the number of update steps per run, is taken to scale linearly with the system size. The remaining factor of $`2\alpha N\mathrm{log}N`$ arises from the necessity to maintain the ordered list of fitnesses in Eq. (2): during each update, on average $`2\alpha `$ vertices change their fitnesses and need to be reordered, since the two vertices chosen to swap partitions are each connected on average to $`\alpha `$ other vertices. The cost of sequentially ordering fitness values is in principle $`N\mathrm{log}N`$. However, to save a factor of $`N`$, we have instead resorted to an imperfect heap ordering of the fitness values, as already described in Ref. BoPe1 . Ordering a list of $`N`$ numbers in a binary tree or “heap” ensures that the smallest fitness will be at the root of the tree, but does not provide a perfect ordering between all of the other members of the list as a sequential ordering would. Yet, with high probability smaller fitnesses still reside in levels of the tree closer to the root, while larger fitnesses reside closer to the end-nodes of the tree. To maintain such a tree only requires the $`O(\mathrm{log}N)`$ moves needed to replace changing fitness values.

Specifically, consider a list of $`N`$ fitness values. This list will fill a binary tree with at most $`l_{\mathrm{max}}+1`$ levels, where $`l_{\mathrm{max}}=[\mathrm{log}_2(N)]`$ ($`[x]`$ denotes the integer part of $`x`$) and $`l=0,1,\mathrm{},l_{\mathrm{max}}`$, where $`l=0`$ is the level consisting solely of the root, $`l=1`$ is the level consisting of the two elements extending from the root, etc. In general, the $`l`$th level contains up to $`2^l`$ elements, and all level are completely filled except for the end-node-level $`l_{\mathrm{max}}`$, which will only be partially filled in case that $`N<2^{l_{\mathrm{max}}+1}1`$. Clearly, by definition, every fitness on the $`l`$th level is worse than its two descendents on the $`(l+1)`$th level, but there could nevertheless be fitnesses on the $`l`$th level that are better than some of the other fitnesses on the $`(l+1)`$th (or even greater) level. On average, though, the fitnesses on the $`l`$th level are always worse than those on the $`(l+1)`$th level, and better than those on the $`(l1)`$th level.

Thus, instead of applying the probability distribution in Eq. (3) directly to a sequentially ordered list, we save an entire factor of $`N`$ in the computational cost by using an analogous (exponential) probability distribution on the (logarithmic) number of levels $`l`$ in our binary tree,

$`Q(l)2^{(\tau 1)l},(0l[\mathrm{log}_2(N)]+1).`$ (7)
From that level $`l`$ we then choose one of the $`2^l`$ fitnesses at random and update the vertex associated with that fitness value. Despite the differences in the implementations, our studies show that heap ordering and sequential ordering produce quite similar results. In particular, the optimal value of $`\tau `$ found for both methods is virtually indistinguishable. But with the update procedure using the heap, EO algorithm runs at a cost of merely $`O(2\alpha N\mathrm{log}N)`$.

Under some circumstances, it may be possible to maintain a partially or even perfectly ordered list at constant cost, by using a hash table. For instance, for trivalent graphs or more generally for $`\alpha `$-valent graphs, each vertex $`i`$ can be in only one of $`\alpha +1`$ attainable states, $`b_i=0,1,\mathrm{},\alpha `$ and $`\lambda _i=b_i/\alpha `$. Thus, instead of time consuming comparisons between $`\lambda `$’s, fitness values can be hashed into and retrieved from “buckets”, each containing all vertices with a given $`b_i`$. For an update, we then obtain ranks according to Eq. (3), determine which bucket that rank points to, and retrieve one vertex at random from that bucket.

Even in cases where the fitness values do not fall neatly into a discrete set of states, such a hash table may be an effective approximation. But great care must be taken with respect to the distribution of the $`\lambda `$’s. This distribution could look dramatically different in an average configuration and in a near-optimal configuration, because in the latter case fitness values may be densely clustered about 1.

#### III.3.4 Startup routines

The results obtained during a run of a local search algorithm can often be refined using an appropriate startup routine. This is an issue of practical importance for any optimization method Reeves . For instance, Ref. JohnsonGBP  has explored improvements for the partitioning of geometric graphs by initially dividing the vertices of the graph into two geometrically defined regions (for instance, drawing a line through the unit square). This significantly boosted the performance of the Kernighan-Lin algorithm on the graphs. Such methods are not guaranteed to help, however: simulated annealing shows little improvement using a startup JohnsonGBP . Happily, the performance of the EO algorithm typically is improved considerably with a clever startup routine.

Previously, we have explored a startup routine using a simple clustering algorithm BoPe1 , which accomplishes the separation of the graph into domains not only for geometric but also for random graphs. The routine picks a random vertex on the graph as a seed for a growing cluster, and recursively incorporates the boundary vertices of the cluster until $`N/2`$ vertices are covered, or until no boundary vertices exist anymore (signaling a disconnected cluster in the graph). The procedure then continues with a new seed among the remaining vertices. Such a routine can substantially enhance EO’s convergence especially for geometrically defined graphs (see Sec. IV.3.3). In this paper, though, we did not use any startup procedure because we prefer to focus on the intrinsic features of the EO algorithm itself. Instead, all the results presented here refer to runs starting from random initial partitions, except for a small comparison in Sec. IV.3.3.

## IV Numerical Results

### IV.1 Description of EO runs

In our numerical simulations, we considered the four classes of graphs introduced in Sec. II. For each class, we have studied the performance of EO as a function of the size of the graph $`N`$, the runtime $`t`$, and the parameter $`\tau `$. To obtain a statistically meaningful test of the performance of EO, large values of $`N`$ were chosen; EO performed too well on smaller graphs. The maximum value of $`N`$ varied with each kind of graph, mostly due to the fact that some types required averaging over many more instances, thus limiting the attainable sizes.

The precise instance sizes were: $`N=1022`$, 2046, 4094 and 8190 for both random and trivalent graphs; $`N=13^3(=2197)`$, $`16^3(=4096)`$ and $`20^3(=8000)`$ for ferromagnetic graphs; and $`N=510`$, 1022, and 2046 for geometric graphs. For each class of graphs, we generated a sizable number of instances at each value of $`N`$: 32 for random and trivalent graphs, 16 for ferromagnetic graphs, and 64 for geometric graphs. For each instance, we conducted a certain number of EO runs: 8 for random and trivalent graphs, 16 for ferromagnetic graphs, and 64 for geometric graphs. Finally, the runtime (number of update steps) used for each run was $`t_{\mathrm{max}}=AN`$, with $`A=512`$ for random graphs, $`A=4096`$ for trivalent graphs, $`A=1000`$ for ferromagnetic graphs and $`A=2048`$ for geometric graphs.

### IV.2 Choosing $`\tau `$

In previous studies, we had chosen $`\tau =1.4`$ as the optimal value for all graphs. In light of our discussion in Sec. III.3.2 on how to estimate $`\tau `$, here we have performed repeated runs over a range of values of $`\tau `$ on the instances above, using identical initial conditions. The goal is to investigate numerically the optimal value for $`\tau `$, and the dependence of EO’s results on the value chosen. In Figs. 2a-d we show how the average cutsize depends on $`\tau `$, given fixed runtime. There is a remarkable similarity in the qualitative performance of EO as a function of $`\tau `$ for all types and sizes of graphs. Despite statistical fluctuations, it is clear that there is a distinct minimum for each class, and that as expected, the results get increasingly worse in all cases for smaller as well as larger values of $`\tau `$.

While the optimal values for $`\tau `$ are similar for all types of graphs, there is a definite drift towards smaller values of $`\tau `$ for increasing $`N`$. Studies on spin glasses EO\_PRL  have led to similar observations, supporting the argument for the scaling of $`\tau `$ that we have given in Sec. III.3.2. Our data here do not cover a large enough range in $`N`$ to analyze in detail the dependence of $`\tau `$ on $`\mathrm{log}N`$. However, we can at least demonstrate that the results for trivalent graphs, where statistical errors are relatively small, are consistent with Eq. (6) above. For fixed $`N`$ but increasing values of $`A=t/N`$, we see in Fig. 3a that the optimal value of $`\tau `$ appears to increase linearly as a function of $`\mathrm{log}A`$ in the regime $`1AN`$. At the same time, fixing $`A`$ and increasing $`N`$, we see in Fig. 3b that the optimal value of $`\tau `$ appears to decrease linearly as a function of $`1/\mathrm{log}N`$, towards a value near $`\tau =1`$. Thus, for $`1AN`$, $`\tau `$ seems to be converging very slowly towards 1, with a finite $`N`$ correction of $`\mathrm{log}A/\mathrm{log}N`$. This is in accordance with our estimate, Eq. (6), discussed earlier in Sec. III.3.2. (Note that at $`A500`$ in Figs. 2a-b, the optimal values for random and trivalent graphs are close to $`\tau 1.3`$, consistent with Eq. (6). In contrast, in our long-time studies below, $`AN`$ and a value of $`\tau =1.45`$ seems preferable, consistent with Fig. 3a.)

The foregoing data, including the results plotted in Figs. 2a-d, arise from averages $`\overline{m(t)}`$ over all runs (denoted by $`\mathrm{}`$) and all instances (denoted by an overbar). But it is important to note that the conclusions drawn with respect to the optimal value of $`\tau `$ from these plots are valid only if there is little difference between the average run $`m(t)`$ and the best run $`m_{\mathrm{best}}`$ for a particular instance. While this is the case for the random and trivalent graphs, there is a significant difference between $`m(t)`$ and $`m_{\mathrm{best}}`$ for instances of ferromagnetic and geometric graphs, as is discussed later in Sec. IV.3.3. In fact, for geometric graphs (Fig. 6 below), average and best cutsizes often differ by a factor of 2 or 3! Fig. 2d indicates that the optimal value of $`\tau `$ for the average performance on geometric graphs of size $`N=2046`$ is below $`\tau =1.2`$. If we instead plot the fraction of runs that have come, say, within 20% of the best value $`m_{\mathrm{best}}`$ found by EO (which most likely is still not optimal) for each instance, the optimal choice for $`\tau `$ shifts to larger values, $`\tau 1.3`$ (see Fig. 4).

We may interpret this discrepancy as follows. At lower values of $`\tau `$, EO is more likely to explore the basin of many local minima but also has a smaller chance of descending to the “bottom” of any basin. At larger values of $`\tau `$, all but a few runs get stuck in the basin of a poor local minimum (biasing the average) but the lucky ones have a greater chance of finding the better states. For geometric graphs, the basins seem particularly hard to escape from, except at the very low values of $`\tau `$ where EO is unlikely to move toward the basin’s minimum. Thus, in such cases we find that we get better average performance $`m(t)`$ at a lower value of $`\tau `$, but the best result $`m_{\mathrm{best}}`$ of multiple runs is obtained at a higher value of $`\tau `$.

Clearly, in order to obtain optimal performance of EO within a given runtime and for a given class of graphs, further study of the best choice of $`\tau `$ would be justified. But for an analysis of the scaling properties of EO with runtime and $`N`$, the specific details of how the optimal $`\tau `$ varies are not significant. Therefore, to simply the following scaling discussion, we will simply fix $`\tau `$ to a near-optimal value on each type of graph.

### IV.3 Scaling behavior

#### IV.3.1 General results

As explained in Sec. III, the cutsize of the current configuration will fluctuate wildly at all times during an EO run and will not in itself converge. Instead, we have to keep track of the best configuration obtained so far during a run. Thus, even for times $`t<t_{\mathrm{max}}`$ during an EO run, we refer to the cutsize $`m(t)`$ of the current best configuration as the “result” of that run at time $`t`$. Examples of the stepwise manner in which $`m(t)`$ converges towards the optimal cutsize, for a particular instance of each type of graph, are given in Fig. 5. Up until times $`tN`$, $`m(t)`$ drops rapidly because each update rectifies poor arrangements created by the random initial conditions. For times $`tN`$, it takes collective rearrangements involving many vertices to (slowly) obtain further improvements.

While during each run $`m(t)`$ decreases discontinuously, for the random and trivalent graphs the jumps deviate relatively little from that of the mean behavior obtained by averaging over many runs ($`\mathrm{}`$). Fluctuations, shown by the error bars in Figs. 5a-b, thus are small and will be neglected henceforth. For the ferromagnetic and geometric graphs, these fluctuations can be enormous. In Fig. 6 we compare the average performance $`\overline{m}`$ with the best performance $`\overline{m_{\mathrm{best}}}`$ for each type of graph, at the maximal runtime $`t_{\mathrm{max}}`$ and averaged over all instances at each $`N`$. The results demonstrate that for random and trivalent graphs the average and best results are very close, whereas for ferromagnetic and geometric graphs they are far apart (with even the scaling becoming increasingly different for the geometric case). Therefore, in the following we will consider scaling of the average results for the first two classes of graphs, but properties of the best results for the latter two.

#### IV.3.2 Random and trivalent graphs

Averaging $`m(t)`$ for any $`t`$ over all runs ($`\mathrm{}`$) and over all instances (overbar), we obtain the averaged cutsize

$`\overline{m}=m(N,t,\tau )`$ (8)
as a function of size $`N`$, runtime $`t`$, and parameter $`\tau `$. In Fig. 7 we plot $`m(N,t,\tau )`$ for random and trivalent graphs as a function of $`t`$, for each $`N`$ and at a fixed value $`\tau =1.45`$ that is near the optimal value for the maximal runtimes $`t_{\mathrm{max}}`$ (see Sec. IV.2). The error bars shown here are due only to instance-to-instance fluctuations, and are consistent with a normal distribution around the mean. (Note that the error bars are distorted due to the logarithmic abscissa.) The fact that the relative errors decreases with $`N`$ demonstrate that self-averaging holds and that we need only focus on the mean to obtain information about the typical scaling behavior of an EO run.

We wish to study the scaling properties of the function $`m`$ in Eq. (8). First of all, we find that generally

$`m(N,t,\tau )N^{1/\nu }\stackrel{~}{m}(t/N,\tau )(tN1),`$ (9)
reflecting the fact that for EO, as well as for most other graph partitioning heuristics that are based on local search, runtimes scale linearly with $`N`$. (This is justified by the fact that each of the $`N`$ variables only has 2 states to explore. In, say, the traveling salesperson problem, by contrast, each of $`N`$ cities can be reconnected to $`O(N)`$ other cities, and so runtimes typically scale at least with $`N^2`$ JohnsonTSP .) In Fig. 8 we plot $`m(N,t,\tau )/N`$ for fixed $`\tau =1.45`$ as a function $`t/N`$. We find indeed that the data points from Fig. 7 collapse onto a single scaling curve $`\stackrel{~}{m}(t/N,\tau )`$, justifying the scaling ansatz in Eq. (9) for $`\nu =1`$. The scaling collapse is a strong indication that EO converges in $`O(N)`$ updates towards the optimal result, and also that the optimal cutsize itself scales linearly in $`N`$.

The scaling function $`\stackrel{~}{m}`$ appears to converge at large times to the average optimal result $`\stackrel{~}{m}_{\mathrm{opt}}=m_{\mathrm{opt}}/N`$ according to a power law:

$`\stackrel{~}{m}(t/N,\tau )\stackrel{~}{m}_{\mathrm{opt}}+C\left({\displaystyle \frac{t}{N}}\right)^\gamma (tN1).`$ (10)
Fitting the data in Fig. 8 to Eq. (10) for $`t/N>1`$, we obtain for each type of graph a sequence of values for $`\stackrel{~}{m}_{\mathrm{opt}}`$ and $`\gamma `$ for increasing $`N`$, given in Tab. 1. In both cases we find values for $`\stackrel{~}{m}_{\mathrm{opt}}/N`$ that are quite stable, while the values for $`\gamma `$ slowly decrease with $`N`$. The variation in $`\gamma `$ as a function of $`N`$ may be related to the fact that for a fixed $`\tau `$, EO’s performance at fixed $`A=t/N`$ deteriorates logarithmically with $`N`$, as seen in Sec. IV.2. Even with this variation, however, the values of $`\gamma `$ for both types of graph are remarkably similar: $`\gamma 0.4`$. This implies that in general, on graphs without geometric structure, we can halve the approximation error of EO by increasing runtime by a factor of 5–6. This power-law convergence of EO is a marked improvement over the mere logarithmic convergence conjectured for simulated annealing Science  on NP-hard problems Grest .

Finally, the asymptotic value of $`\stackrel{~}{m}_{\mathrm{opt}}`$ obtained for the trivalent graphs can be compared with previous simulations Banavar ; EOperc . There, the “energy” $`=1+4\stackrel{~}{m}_{\mathrm{opt}}/3`$ was calculated using the best results obtained for a set of trivalent graphs. Ref. Banavar  using simulated annealing obtained $`=0.840`$, while in a previous study with EO EOperc  we obtained $`=0.844(1)`$. Our current, somewhat more careful extrapolation yields $`\stackrel{~}{m}_{\mathrm{opt}}=0.1158N`$ or $`=0.845(1)`$. Even though this extrapolation is based on the average data rather than only the best of all runs, the very low fluctuations between runs (see Figs. 5b and 6) indicate that the result for $``$ would not change significantly. Thus, the replica symmetric solution proposed in Refs. M+P ; W+S  for this version of the GBP, which gives a value of $`=2\times 0.7378/\sqrt{3}=0.852`$, seems to be excluded.

#### IV.3.3 Ferromagnetic and geometric graphs

Unlike on the preceding graphs, EO gives significantly different results for an average run and for the best run on geometrically structured graphs (see Figs. 5 and 6). In Fig. 6, at least the results from the best run (averaged over all instances) comes close to the scaling behavior expected from the considerations in Sec. II.3: a fit gives $`\nu 1.3`$ for ferromagnetic, and $`\nu 2`$ for geometric graphs, while the theory predicts $`\nu =3/2`$ and $`\nu =2`$ respectively. But even these best cutsizes themselves vary significantly from one instance to another. Thus, it is certainly not useful to study the “average” run. Instead, we will consider the result of each run at the maximal runtime $`t_{\mathrm{max}}`$, extract the best out of $`k`$ runs, and study these results as a function of increasing $`k`$.

Fig. 9 shows the difficulty of finding good runs with near-optimal results for increasing size $`N`$. While for ferromagnetic graphs it is possible that acceptable results may be obtained without increasing $`k`$ dramatically, for geometric graphs an ever larger number of runs seems to be needed at large $`N`$. It does not appear possible to obtain consistent good near-optimal results at a fixed $`k`$ for increasing $`N`$.

We saw in Sec. IV.3.2 that for random graphs, computational time is well spent on a few, long EO runs per instance. We can not address in detail the question of whether, for geometrically defined graphs, computational time is better spent on $`k`$ independent EO-runs with $`t_{\mathrm{max}}`$ update steps or, say, on a single EO-run with $`k\times t_{\mathrm{max}}`$ update steps. While experience with our data would indicate the former to be favorable, an answer to this question depends significantly on $`N`$ and, of course, on the choice of $`\tau `$ (see Sec. IV.2). Here we consider this question merely for a single value, $`\tau =1.3`$, for which we have run EO on the same 64 geometric graphs up to 16 times longer than $`t_{\mathrm{max}}`$, but using only $`k=4`$ restarts. In each of these 4 runs on an instance we recorded the best result seen at multiples $`n\times t_{\mathrm{max}}`$ with $`n=1,2,4,8`$, and 16. For example, the best-of-4 runs at $`n=1`$ of this runtime corresponds to the best-of-$`k`$ results in Fig. 9 for $`k=4`$, while $`n=16`$ would correspond to the same amount of running time as $`k=64`$. Fig. 10 shows that fewer but longer runs are slightly more successful for larger $`N`$.

Finally, we have also used the clustering algorithm described in Sec. III.3.4 and Ref. BoPe1  on this set of 64 graphs with $`\tau =1.3`$. For comparison, we again use the best-of-4 runs with averages taken at times $`n\times t_{\mathrm{max}}`$, $`n=1,2,`$ and 4. Results at short runtimes improve by a huge amount with such a procedure, but its advantage is eventually lost at longer runtimes. While this procedure is cheap, easy, and apparently always successful for geometric graphs, our experiments indicate that its effect may be less significant for random graphs and may actually result in diminished performance when used for trivalent graphs in place of random initial conditions. Clearly, clustering is tailored more toward geometric graphs satisfying a triangular inequality.

## V Conclusions

Using the classic combinatorial optimization problem of bipartitioning graphs as an application, we have demonstrated a variety of properties of the extremal optimization algorithm. We have shown that for random graphs, EO efficiently approximates the optimal solution even at large size $`N`$, with an average approximation error decreasing over runtime $`t`$ as $`t^{0.4}`$. For sparse, geometrically defined graphs, finding the ideal (sub-dimensional) interface partitioning the graph becomes ever more difficult as size $`N`$ increases. EO, like other local search methods JohnsonGBP , gets stuck ever more often in poor local minima. However, when we consider the best out of multiple runs with the EO algorithm, we recover results close to those predicted by theoretical arguments.

We believe that many of our findings here, notably with regard to EO’s fitness definition and the update procedure using the parameter $`\tau `$, are generic for the algorithm. Our results for optimizing 3-coloring and spin glasses appear to bear out such generalizations EO\_PRL . In view of this observation, a firmer theoretical understanding of our numerical findings would be greatly desirable. The nature of EO’s performance derives from its large fluctuations; the price we pay for this is the loss of detailed balance, which is the theoretical basis for other physically-inspired heuristics, such as simulated annealing Science . On the other hand, unlike in simulated annealing, we have the advantage of dealing with a Markov chain that is independent of time Aarts . This suggests that our method may indeed be amenable to theoretical analysis. We believe that the results EO delivers, as a simple and novel approach to optimization, justify the need for further analysis.

## VI Acknowledgements

We would like to thank the participants of the Telluride Summer workshop on complex landscapes, in particular Paolo Sibani, for fruitful discussions, and Jesper Dall for confirming many of our results in his master thesis at Odense University. This work was supported by the University Research Committee at Emory University, and by an LDRD grant from Los Alamos National Laboratory.


format: text

text:
# References

Testing the AMSB Model via $`e^+e^{}\gamma \stackrel{~}{\chi }^+\stackrel{~}{\chi }^{}`$
Amitava Datta111adatta@juphys.ernet.in 222On leave of absence from Jadavpur University

Department of Physics, Visva-Bharati, Santiniketan - 731 235, India.
Shyamapada Maity333shyama@juphys.ernet.in

Department of Physics, Tamralipta Mahavidyalaya,
Tamluk - 721636, West Bengal, India.

ABSTRACT

The possibility of detecting the signature of a nearly invisible charged wino ($`\stackrel{~}{\chi }^\pm `$) decaying into a soft pion and the LSP($`\stackrel{~}{\chi }_1^0`$), predicted by the Anomaly Mediated Symmetry Breaking model, via the process $`e^+e^{}\gamma \stackrel{~}{\chi }^+\stackrel{~}{\chi }^{}`$ at the Next Linear Collider has been explored. Using the recently, proposed bounds on slepton and wino masses derived from the condition of stability of the electroweak symmetry breaking vacuum and employing some standared kinematical cuts to supress the background, we find that almost the whole of the allowed parameter space with the slepton mass less than 1 TeV, can be probed at $`\sqrt{s}`$ = 500 GeV. Determination of the slepton and the chargino masses from this signal is a distinct possiblity. Any violation of the above mass bound will suggest that the standard vacuum is unstable and we are living in a false vacuum.

Supersymmetry (SUSY) has now been widely accepted as an elegant alternative to the standard model(SM). The current experimental limits on the masses of the superpartners show that , even if they exist, they must be significantly heavier than the corresponding SM particles. Thus SUSY must be broken. The mechanism of this breaking is still unknown although several interesting models have been proposed. Without such a specific SUSY breaking mechanism, the most general minimal supersymmetric extension of the standard model ( MSSM) contains a large number of soft breaking (SB) terms. The resulting model with a large number of unknown parameters is, however, not very predictive. Thus one attempts to construct a constrained MSSM with additional theoretical assumptions on SUSY breaking.

In the minimal supergravity (mSUGRA) type models  one assumes that all the SM particles and their superpartners belong to the observable sector (OS). SUSY breaking takes place in hidden sector (HS), whose fields are all singlets under the SM gauge group and are very heavy. A contact interaction between the HS and the OS fields is introuced in the K$`\ddot{a}`$hler potential by gravitational interactions which is suppressed by the Planck mass squared. This tree-level interaction induces SUSY breaking in the OS; in such models the gravitino mass is of the order of 1 TeV. These models with the additional constraint of radiative electroweak symmetry breaking  have only five more free parameters compared to the SM.

Recently, it has been pointed out that if the OS and the HS fields belong to two distinct 3-branes separated by a finite distance along a fifth compactified dimension, the above mechanism for transmitting SUSY breaking from the HS to the OS fails. However, a superconformal anomaly may induce the SUSY breaking in the OS. Such soft breaking terms are also present in SUGRA type models , but they are suppressed in comparison to the usual soft-breaking terms. To generate the weak scale masses of the sparticles, the gravitino mass must be of the order of tens of TeV. Such models are generically known as anomaly-mediated SUSY breaking (AMSB) models .

AMSB, alongwith the radiative electroweak symmetry breaking condition, fixes the sparticle spectrum completely in terms of three parameters: $`m_{3/2}`$ ( the gravitino mass ), $`\mathrm{tan}\beta `$ (the ratio of the vacuum expectation values (VEV) of the two Higgs fields), and $`sign(\mu )`$. The gaugino masses $`M_1`$, $`M_2`$ and $`M_3`$, and the trilinear couplings (generically denoted by $`A`$) can be obtained from the relevant renormalization group (RG) $`\beta `$-functions and anomalous dimensions. The sfermion masses, as well as the Higgs mass parameters, are also determined by $`m_{3/2}`$. Unfortunately, for sfermions that do not couple to asymptotically free gauge groups (i.e., the left and right sleptons, $`\stackrel{~}{l_L}`$, $`\stackrel{~}{l_R}`$, $`l`$= e, $`\mu `$, $`\tau `$), the masses come out to be tachyonic. The remedy is sought by putting a positive definite mass squared term $`m_0^2`$ in the GUT scale boundary conditions. Such terms can be justified by appealing to the presence of extra field(s) in the bulk. These models with a universal $`m_0`$ for all scalars are called the minimal AMSB (mAMSB) models . The phenomenology of such models has been at the focus of attention of many recent studies , and our discussions will be restricted within the frame work of mAMSB models.

One can determine the complete particle spectrum in terms of the above free parameters. A crucial prediction very relevant for this paper is as follows : the lighter chargino($`\stackrel{~}{\chi }^\pm `$) is almost degenerate with the lightest neutralino($`\stackrel{~}{\chi }_1^0`$), which we assume to be the lightest supersymmetric particle (LSP). Both of them are heavily dominated by the wino component.

The near degeneracy leads to the most striking experimental signature of AMSB models, based on the “nearly invisible” decay of the relatively long lived $`\stackrel{~}{\chi }^\pm `$ to the LSP and a soft charged pion: $`\stackrel{~}{\chi }^\pm \stackrel{~}{\chi }_1^0\pi ^\pm `$ . If $`M_2`$80GeV , then $`\mathrm{\Delta }m=m_{\stackrel{~}{\chi }^\pm }m_{\stackrel{~}{\chi }_{1}^{}{}_{}{}^{0}}>m_{\pi ^\pm }`$. Consequently the decay mode $`\stackrel{~}{\chi }^\pm \stackrel{~}{\chi }_1^0\pi ^\pm `$ dominates over a large region of the allowed parameter space(APS), where the $`\pi ^\pm `$ is rather soft for relatively small $`\mathrm{\Delta }m`$. Thus the chargino decays almost invisibly and the conventional search strategies involving acoplanar leptons and/or jets + missing energy may not be applicable.

Due to the small $`\mathrm{\Delta }m`$, however, the chargino has other distinguishing characterestics which may be exploited in detecting them. For example, they may have macroscopic decay lengths. This may lead to heavily ionising tracks in the vertex detector without corresponding activities in the calorimeter or in the muon chamber. Moreover the tracks end in soft pions which may be observable, if the impact parameters are clearly non zero and $`p_T^\pi `$ is sufficiently large. These features may be utilised to identify $`\stackrel{~}{\chi }^\pm `$ production in the off-line analysis if the event can be suitably triggered on.

There is a lower limit on $`m_{3/2}`$ coming from the lower bound $`m_{\stackrel{~}{\chi }^\pm }^{min}=86`$ GeV  on charginos decaying through the soft pion mode from direct searches at LEP. This limit is roughly $`m_{3/2}`$ 28-32 TeV. The detection of these charginos are of crucial importance since they may happen to be the only sparticle( apart from the LSP ) within the striking range of an early version of the Next Linear Collider (NLC) at $`\sqrt{s}`$ = 500 GeV.

The search strategies for nearly invisible charginos were first studied by Chen et. al.  in the context of other models with such charginos. It was noted that for $`m_{\pi ^\pm }<\mathrm{\Delta }m<`$230 MeV, the charginos may pass through several layers of a typical vertex detector leaving behind a heavily ionising track which by itself is a distinctive feature. However, for $`\mathrm{\Delta }m`$ in the upper half of the above range, they may only pass through one or two inner layers of the vertex detector which may be difficult to distinguish from ,e.g, random hits due to detector noise. However, such charginos often end up in a soft pion with an impact parameter(b) significantly larger than the impact parameter resolution($`b_{res}`$) which is typically $`10^1`$cm . If $`\mathrm{\Delta }m>`$230 MeV the chargino tracks in the vertex detector could be too short for proper identification. However, the soft pions are usually more energetic in this case which may correspond to a better impact parameter resolution. Consequently the impact parameter of the pion may be appreciably larger than $`b_{res}`$ inspite of the small chargino decay length.

Any of the above features may suffice to identify nearly invisible charginos in the off line analysis. However, triggering based on activities in the vertex dector alone may be problematic. Hence the process $`e^+e^{}\gamma \stackrel{~}{\chi }^+\stackrel{~}{\chi }^{}`$ was recommended, where the hard $`\gamma `$ and missing energy in the final state can be easily triggered on. The activities in the vertex detector and/or soft pions may dramatically reduce the background from processes like $`e^+e^{}\gamma \nu \overline{\nu }`$

The purpose of this note is to study the viability of this channel at NLC with $`\sqrt{s}`$ = 500 GeV within the framework of mAMSB models. We wish to emphasize that so far as this process is concerned the mAMSB model is much more predictive and interesting than other models involving invisible charginos and radiative EW symmetry breaking.

The signal cross section is given by i) four $`t`$ channel sneutrino exchange diagrams. ii) four $`s`$ channel Z-exchange diagrams iii) four $`s`$ channel $`\gamma `$ exchange diagrams . In the most general case the production cross section depends on the parameters $`\mu `$, tan$`\beta `$ and $`M_2`$ through the chargino mass and mixing angles. These three parameters in addition to the sneutrino mass controls the size of the cross section. In the mAMSB model the lighter chargino is a wino to a very good approximation. Thus the mixing angles ($`1`$) mildly depend on SUSY parameters. As a result the cross sections is effectively a function of two parameters only $`m_{\stackrel{~}{\chi }^\pm }`$ and $`m_{\stackrel{~}{\nu }}`$. As was shown by Chen et. al. (to be reviewed below), $`m_{\stackrel{~}{\chi }^\pm }`$ can be determined from the kinematics alone. Thus the size of the cross section may suffice to determine $`m_{\stackrel{~}{\nu }}`$, although this mass could be well outside the kinematic reach of the collider, which is quite possible for NLC at $`\sqrt{s}`$ = 500 GeV.

The cross section for the process $`e^+e^{}\gamma \stackrel{~}{\chi }^+\stackrel{~}{\chi }^{}`$ was first computed for models with $`m_{\stackrel{~}{\nu }}`$1 TeV or larger . In this case the $`t`$ \- channel $`\stackrel{~}{\nu }`$ exchange diagrams were justifiably neglected. However, for lower $`m_{\stackrel{~}{\nu }}`$ the cross section may be significantly smaller . This happens due to destructive interferences between s-channel($`\gamma `$, $`Z`$ exchange) and t- channel diagrams. The full cross section valid for all $`m_{\stackrel{~}{\nu }}`$ is given in .

In the AMSB models the sleptons and sneutrinos may indeed be rather light depending on the choice of the common scalar mass $`m_0`$. This leaves open the possiblity that the cross section could be significantly smaller than that obtained in the large $`m_0`$ limit(see below for details). Fortunately as has been pointed out recently, there is a lower bound on $`m_0`$ resulting in a corresponding bound on $`m_{\stackrel{~}{l_L}}`$ and $`m_{\stackrel{~}{\nu }}`$ ($`m_{\stackrel{~}{l_L}}>`$330 GeV most conservatively) . This lower bound excludes the possiblity of direct slepton pair production at NLC with $`\sqrt{s}`$ = 500 GeV. Thus $`\stackrel{~}{\chi }^\pm `$ and $`\stackrel{~}{\chi }_1^0`$ are the only sparticles accessible to this accelerator.

The above bound arises by requiring that E-W symmetry breaking minimum of the scalar potential be deeper than all possible charge/colour breaking minima . Moreover, thanks to the same constraints, there is an upper bound on the lighter chargino mass for a given $`m_0`$(or slepton mass)(see table). The numbers in this table are slightly different from the corresponding numbers in Table II of . This is due to the fact that we have taken into account loop induced electroweak radiative correction  to the chargino mass. The possible effects of this correction were commented upon in  but they were not included in the numerical results.

From the table it is clear that the lighter chargino mass is predicted to be within the stricking range of NLC at $`\sqrt{s}`$ = 500 GeV for a wide range of slepton masses. Thus the signal of nearly invisible charginos is quite likely to be seen. The absence of this signal on the other hand would rule out a large part of the interesting parameter space of this model.

The above lower bound on the sparticles masses may be evaded by requiring that the present SU(2)$`\times `$U(1) symmetry breaking minimum is a metastable false vacuuam which in principle can decay into much deeper true vacuum breaking charge and colour symmetry. However, the decay time is larger than the age of the universe . In view of this interesting suggestion the measurment of the slepton and the chargino mass as sketched above acquires special significance. If the mass indeed turn out to violate the bounds of  then that would strongly indicate that we are living in a false vacuum.

In the mSUGRA models the violation of certain bounds on the $`A`$ parameter  indicate the existence of a charge colour breaking vacuum. Since this parameter is not directly related to any mass, this experimental test is not straight forward. In contrast testing the bounds on $`m_{\stackrel{~}{\chi }^\pm }`$ or $`m_{\stackrel{~}{l}_L}`$ is rather unambiguous from the experimental point of view.

In Fig.1 we present the cross section at $`\sqrt{s}`$ = 500 GeV in the mAMSB model as a function $`m_{\stackrel{~}{\nu }}`$ for $`m_{\stackrel{~}{\chi }^\pm }`$ = 100, 150, 200 GeV. From the figure it is seen that the cross section first decreases and then increases with increasing of $`m_{\stackrel{~}{\nu }}`$. For small $`m_{\stackrel{~}{\nu }}`$ the $`t`$-channel diagrams dominate and the effect of interference is relatively weak. For larger $`m_{\stackrel{~}{\nu }}`$ interference effect is very prominent. This interference being destructive in nature, with the increasing of $`m_{\stackrel{~}{\nu }}`$ the cross section increases. It is clear from the figure that once $`m_{\stackrel{~}{\chi }^\pm }`$ is measured from the kinematics(see below) $`m_{\stackrel{~}{l_L}}`$, or $`m_{\stackrel{~}{\nu }}`$ may be obtained from the size of the cross section.

The kinematical cuts used in computing the cross section are $`p_T^\gamma `$10 GeV, $`10^o\theta _\gamma 170^o`$. These cuts are required to remove the radiative Bhabha and other backgrounds . To ensure the observability of the soft pions , we further require that only one of the two soft pions satisfy $`p_T^\pi `$200 MeV, $`\eta _\pi `$2.5 .

In the table we present the cross section with above kinematical cuts on the $`\gamma `$ and the soft pion(see below). From the table it is clear that the entire allowed range of $`m_{\stackrel{~}{\chi }^\pm }`$ except for $`m_0`$1 TeV, leads to hundreds of background free events at NLC with $`\sqrt{s}`$ = 500 GeV and $``$ = 50 $`fb^1`$.

We next analyse the track length of the $`m_{\stackrel{~}{\chi }^\pm }`$ and the inpact parameter of the soft pion to check whether these characterestics are adequate to make the signal background free.

Although $`\sigma `$ is largely insensitive to tan$`\beta `$ and sign$`\mu `$, the track length ($`l`$) of the chargino depends sensitively on these parameters, where $`l`$=$`\beta \tau _{lab}`$. This is due to the fact that $`\mathrm{\Delta }m`$ and, hence, the $`\stackrel{~}{\chi }^\pm `$ life time in its rest frame($`\tau `$) depends quite a bit on these parameters. We have studied the distributions of these two observables for the entie parameter space allowed by the bounds of .

We find that at $`\sqrt{s}`$ = 500 GeV, $`l<`$4 cm. This is due to the fact that at low $`M_2`$ (i.e. small $`m_{\stackrel{~}{\chi }^\pm }`$), $`\mathrm{\Delta }m`$ is large . This lead to a small $`\tau `$ and consequently a short track. On the other hand for large $`M_2`$ although $`\mathrm{\Delta }m`$ is favourable, $`\beta `$ at $`\sqrt{s}`$ = 500 GeV is not enough to give a long track.

In  the characteristics of a typical Silicon Vertex Detector(SVD) has been quoted from a CDF report . From the analysis of  it is clearer that for $`l<`$ 4 cm. a chargino is, not likely to traverse more than a few inner layers of the vertex detector and this characteristic may not be sufficiently distinctive for suppressing the background. However, the estimates of  are based on the CDF-II detector. It is quite possible that the vertex detector at NLC will have layers closer to the beam pipe. The fact that the beam at NLC will be narrower than that at Tevatron strengthens this expectation. If that is the case then even $`l<`$ 4 cm. may help to reduce the background. The impact parameter of the pion is, however, large enough for the bulk of the APS and helps to reduce the background even if $`l`$ is small. Assuming an impact parameter resolution $`b_{res}`$0.1 cm , we have required $`b>`$0.5 cm as the criterian for the detectability of the pion. In fact $`b_{res}`$ could be significantly smaller  depending on the pion energy. Our assumption is, therefore, quite conservative.

For all $`m_0`$ in the table, except for $`m_0`$= 1 TeV, the number of events with at least one detectable soft pion exceeds 10 as long as $`m_{\stackrel{~}{\chi }^\pm }`$ is below the upper bound $`(m_{\stackrel{~}{\chi }^\pm })_{max}`$. For $`m_0`$ = 1000 GeV and tan$`\beta `$ = 5 a $`\stackrel{~}{\chi }^\pm `$ with mass close to the upper limit lies outside the kinematic reach of NLC with $`\sqrt{s}`$ = 500 GeV(see table). The search limit in this case is found to be $`m_{\stackrel{~}{\chi }^\pm }`$= 219 GeV. The corresponding $`b`$ distributions of the pion is shown in fig-2. Requiring $`b>`$0.5 cm, fig-2 corresponds to 10 events.

It is quite possible that at higher $`\sqrt{s}`$ the chargino track length will be significantly larger. This is illustrated in Fig-3. We have taken $`m_{\stackrel{~}{\chi }^\pm }`$=262 which corresponds to the upper bound on $`m_{\stackrel{~}{\chi }^\pm }`$ for $`m_0`$= 1 TeV. and $`\sqrt{s}`$ = 1 TeV. According to  for $`\beta \tau _{lab}>`$7 cm, the charginos will pass through at least four layers of the SVD. Thus for entire allowed range of the chargino masses corresponding to $`m_0`$=1 TeV, glimpses of heavily ionising chargino tracks can be seen in the SVD at $`\sqrt{s}`$= 1 TeV.

We next discuss the determination of \[$`m_{\stackrel{~}{\chi }^\pm }`$\] from the observable $`m_Z^{}([p^{e^+}+p^e^{}p^\gamma ]^{1/2})/2`$ . It follows that $`m_Z^{}>m_{\stackrel{~}{\chi }^\pm }`$ for the signal. The results for $`\sqrt{s}`$ = 500 GeV are shown in fig-4 for $`m_{\stackrel{~}{\chi }^\pm }`$= 100, 150, 200. Although the kinematical cuts distort the lower edge of the distribution to some extent, $`m_{\stackrel{~}{\chi }^\pm }`$ can be measured with an accuracy of a few percent except for $`m_{\stackrel{~}{\chi }^\pm }>`$ 200 GeV.

Once $`m_{\stackrel{~}{\chi }^\pm }`$ is determined $`m_{\stackrel{~}{\nu }}`$ can be measured to a good approximation from the size of the cross section. Even if $`m_{\stackrel{~}{\nu }}`$ is determined approximately, this information, with some luck, may be utilised in distinguishing the mAMSB model from other competing models with small $`\mathrm{\Delta }m`$. For example in the string motivated model of  the slepton mass is necessarily large ($``$ 1 TeV) and as discussed above the cross section for the same $`m_{\stackrel{~}{\chi }^\pm }`$ is expected to be larger.

This illustrates the advantage of this signal over a similar discovery channel, $`p\overline{p}\stackrel{~}{\chi }^+\stackrel{~}{\chi }^{}g`$, at hadron colliders (J. Feng et. al. in ). In the later case neither $`m_{\stackrel{~}{\chi }^\pm }`$ nor the slepton mass can be reliably measured from the observed signal. Thus the underlying model may not be identified.

The model underlying the nearly invisible charginos may be unearthed by exploiting the advent of polarised electron beams. For example, with a right polarised beam for which the $`t`$ \- channel diagrams decouple, the cross section will be significantly larger than the unpolarised cross section if the slepton masses happen to be small. In contrast in the string motivated model with heavy sleptons cross sections are not likely to show any drastic change. The computation of the signal for polarised beams is under progress.

In conclusion we reiterate that the signal $`e^+e^{}\gamma \stackrel{~}{\chi }^+\stackrel{~}{\chi }^{}`$ looks very promising in the mAMSB model. Most interestingly there is i) a lower bound on the slepton mass ($`m_{\stackrel{~}{l}_L}`$ 330 GeV) and ii) an upper bound on chargino mass(see table) for a given slepton mass  which makes this model very predictive. In view of these bounds $`\stackrel{~}{\chi }^\pm `$ and $`\stackrel{~}{\chi }_1^0`$ are the only sparticles within the striking range of NLC at $`\sqrt{s}`$ = 500 GeV.

For a wide range of common scalar mass ($`m_0<`$1 TeV) the signal can be detected by exploiting the soft pions from $`\stackrel{~}{\chi }^\pm `$ decay for the entire allowed range of $`m_{\stackrel{~}{\chi }^\pm }`$. For $`m_0`$ = 1 TeV, $`m_{\stackrel{~}{\chi }^\pm }`$219 can be detected at $`\sqrt{s}`$= 500 GeV. Assuming the charcteristics of typical SVD  it appears that the chargino tracks in the SVD may not be long enough to be observable at $`\sqrt{s}`$ = 500 GeV. However, for $`\sqrt{s}`$ = 1 TeV chargino tracks with sufficient length which end in a soft pion can be probed in SVD.

The measurment of $`m_{\stackrel{~}{\chi }^\pm }`$ and $`m_{\stackrel{~}{\nu }}`$ from the $`m_Z^{}`$ distribution and from the total cross section has been discussed. This measurments would be of crucial importance because if the bounds of  are violated, that would strongly indicated that we are living in a false vacuum . Further this mass determination, with some luck, may reveal the model underlying these invisible charginos.

The muon anomalous magnetic moment has recently been measured by E821 Collaboration at Brookhaven  with an unprecedented precission. Apparently there is a 2.6 $`\sigma `$ discrepancy between the experimental result and the SM prediction( for discussions and references to earlier works see, e.g., ). However, this statement is based on the assumption that the computation of the hadronic corrections to the muon anomalous momnent , which is the largest source of uncertainty in the SM prediction, is under control. There is already a claim that if these corrections are computed in a way different from that in , which  quote, then there may be agreement between the SM and the data . Thus ruling out the SM or some specific extension of it on the basis of the alleged discrepancy requires a cautious approach.

If, however, the SM prediction is accepted at its face value, then one of the recent analyses indicates that the mAMSB model is disfavoured by the data . On the contrary it has been shown in  that while this model with low tan$`\beta `$ is indeed disfavoured, the one with large tan$`\beta `$ is allowed. A critical reexamination of these claims are beyond the scope of this paper.

It may be noted that the bounds of  are quite restrictive for large tan$`\beta `$ and the signal cross section is observable for large as well as small values of this parameter ( see the table). At the moment, therefore, the model and a large part of the APS scanned in this paper has no obvious conflict with the data on muon anomalous magnetic moment.

Fig. 1: The variation of $`\sigma _{\stackrel{~}{\chi }^+\stackrel{~}{\chi }^{}\gamma }`$ with $`m_{\stackrel{~}{\nu }}`$ for three values of $`m_{\stackrel{~}{\chi }^\pm }`$ at $`\sqrt{s}`$ = 500 GeV.

Fig. 2: Impact Parameter distribution for $`m_{\stackrel{~}{\chi }^\pm }`$ = 219 GeV at = $`\sqrt{s}`$ 500 GeV.

Fig. 3: Decay Length distribution for $`m_{\stackrel{~}{\chi }^\pm }`$ = 263 GeV at $`\sqrt{s}`$ = 1000 GeV

Fig. 4: $`m_Z^{}`$ distribution for three values of $`m_{\stackrel{~}{\chi }^\pm }`$ at $`\sqrt{s}`$ = 500 GeV

Acknowledgements:
The work of AD was supported by DST, India(Project No. SP/S2/K01/97) and BRNS, India (Project No. 37/4/97 - R & D II/474).


text:
# 1 Introduction

## 1 Introduction

Three-dimensional Einstein gravity has recently developed into an area of active research. In this framework it was showed that, although the presence of mass can not induce curvature (locally curvature vanishes everywhere except at the sources), it does affect the space around the particle . The geometry around a point particle is locally flat, but conical in form, with a deficit angle proportional to the particle’s mass. Thus, a system of gravitating point particle sources only affects geometry globally rather than locally and, as a consequence, local dynamics is replaced by global effects. Quantities such as the total energy-momentum and angular momentum for a system of point particles are defined by global geometric properties of the space-time surrounding the sources. In other words, curvature is created by sources, but only locally at their positions; elsewhere space-time remains flat and for this reason there can exist no interaction between sources. As there are no effects of gravity outside matter, light emitted from the surface of a star will always scape to infinity, and therefore, black holes do not exist in three-dimensional Einstein gravity. Moreover gravity does not propagate outside matter: test particles placed in vacuum do not experience any acceleration. On the other hand, Newton’s gravity theory in this dimension predicts a logarithmic gravitational potential outside matter. As a consequence, a test particle placed in vacuum always accelerates in Newton’s theory. For this reason Einstein’s theory in $`(2+1)`$-dimensional space-time cannot reduce to Newton’s theory by means of linearization.

In order to overcome the problem concerning the non-existence of Newtonian limit in this dimension some ideas have been presented, such as the construction of a teleparallel theory or weakening Einstein equations in the same way as did Jackiw in his formulation of gravity in $`(1+1)`$-dimensions. In two dimensions, Einstein’s theory does not exist because in this case the Einstein tensor $`G_{\mu \nu }=R_{\mu \nu }\frac{1}{2}g_{\mu \nu }R`$ vanishes identically and the Einstein-Hilbert action $`d^2x\sqrt{g}R`$ is a surface term - it is the Euler topological invariant and does not lead to equations of motion.

In the middle of eighties, Jackiw and Teitelboim suggested that a way to obtain a non-trivial dynamics in $`(1+1)`$-dimensions is to introduce an additional gravitational variable $`\eta `$ (scalar Lagrange multiplier) and construct the following non-trivial action

$$d^2x\sqrt{g}\eta (R\mathrm{\Lambda }),$$
(1)
where $`R`$ is the Ricci scalar and $`\mathrm{\Lambda }`$ is the cosmological constant.In this way we can obtain a non-trivial theory of gravity in two dimensions with field equations

$$R\mathrm{\Lambda }=T,$$
(2)
where $`T`$ is the trace of the matter stress-energy tensor.

## 2  Extending Jackiw’s scalar theory

As assumed by Romero and Dahia, we will consider that the eq.(2) with $`\mathrm{\Lambda }=0`$ describes gravity in $`(2+1)`$-dimensions. Thus for source free regions we have

$$R=0.$$
(3)
Now, let us consider the problem of finding the motion of a test particle under the influence of a static, circularly symmetrical matter distribution.

Differently from Romero and Dahia, who considered a conformally flat metric that solves eq.(3), let us choose the static, circularly symmetrical line element given by

$$ds^2=A(r)dt^2+B(r)dr^2+r^2d\theta ^2,$$
(4)
with $`A`$ and $`B`$ being functions of $`r`$ only. Of course, if $`A`$ and $`B`$ are independent, then they cannot be determined by eq.(3) alone. To overcome this difficulty let us reduce the number of degrees of freedom of the geometry by choosing a metric tensor with only one degree of freedom. This can be done if we take $`B=A^1`$. In this case, the line element (4) becomes

$$ds^2=Adt^2+\left(A\right)^1dr^2+r^2d\theta ^2.$$
(5)
Putting eq.(5) into (3), leads to

$$\frac{d^2A}{dr^2}+\frac{2}{r}\frac{dA}{dr}=0,$$
(6)
We can imediately write down the solution of eq.(6), which is given by

$$A=a+\frac{b}{r},$$
(7)
where $`a`$ and $`b`$ are constants.

Therefore, by requiring asymptotical flatness the line element in the present case can be written as

$$ds^2=\left(1\frac{2\beta }{r}\right)dt^2+\left(1\frac{2\beta }{r}\right)^1dr^2+r^2d\theta ^2,$$
(8)
where we have chosen $`a=1`$ and $`b=2\beta .`$

Surely, (8) represents the $`(2+1)`$-dimensional analogue of the Schwarzschild space-time. A simple look at the light cones structure reveals that the surface $`r=2\beta `$ acts as an event horizon. At the value $`r=2\beta `$ we have a removable coordinate singularity. On the other hand $`r=0`$ represents an essential singularity, as can be seen directly from the Riemann tensor scalar invariant $`R_{\mu \nu \lambda \rho }R^{\mu \nu \lambda \rho }=\frac{24\beta ^2}{r^6}`$.

Therefore, the extension of Jackiw’s scalar theory to $`(2+1)`$-dimensions allows the existence of black hole solutions, which are not predicted by three-dimensional Einstein gravity, except for the case of non-vanishing cosmological constant.

For the metric (8), the geodesic equations of motion are

$$\frac{d}{d\lambda }\left[\left(1+\frac{2\beta }{r}\right)\frac{dt}{d\lambda }\right]=0,$$
(9)
$$\frac{d}{d\lambda }\left[r^2\frac{d\theta }{d\lambda }\right]=0$$
(10)
and

$$\left(1\frac{2\beta }{r}\right)\left(\frac{dt}{d\lambda }\right)^2+\left(1\frac{2\beta }{r}\right)^1\left(\frac{dr}{d\lambda }\right)^2+r^2\left(\frac{d\theta }{d\lambda }\right)^2=\epsilon .$$
(11)
where $`\epsilon `$ is a constant that takes the values $`1,0,1`$, for space-like, null and time-like curves, respectively.

Integrating (9) and (10) yields

$$\left(1\frac{2\beta }{r}\right)\frac{dt}{d\lambda }=E$$
(12)
and

$$r^2\frac{d\theta }{d\lambda }=L,$$
(13)
where $`E`$ and $`L`$ are integration constants.

For $`\epsilon =1`$ and $`\lambda =\tau `$ ($`\tau `$ being the proper time as measured by a particle following geodesic motion) it follows from eqs.(11), (12) and (13) that

$$\frac{1}{2}\left(\frac{dr}{d\lambda }\right)^2+V\left(r\right)=\frac{E^2}{2}.$$
(14)
The above equation might be loosely interpreted as the equivalent of energy conservation in Newtonian gravity with $`V\left(r\right)`$ playing the role of an ”effective potential” given by

$$V\left(r\right)=\frac{\epsilon }{2}\frac{\beta \epsilon }{r}+\frac{L^2}{2r^2}\frac{\beta L^2}{r^3}.$$
(15)
By the same token $`L`$ would be looked upon as the angular momentum of the particle per unit mass.

The critical points of the ”effective potential” (15) can be obtained by solving

$$\frac{\beta \epsilon }{r^2}\frac{L^2}{r^3}+\frac{3\beta L^2}{r^4}=0.$$
(16)
For null geodesics ($`\epsilon =0`$) it is easily seen from (14) and (16) that photons can follow the circular orbits $`r=3\beta `$ provided that $`E^2=\frac{L^2}{27\beta ^2}`$. These orbits are highly unstable as $`r=3\beta `$ is an isolated maximum for $`V(r)`$. If $`E^2>\frac{L^2}{27\beta ^2}`$, then either the photon will fall towards the singularity ($`r<3\beta `$) or it will receed into infinity($`r>3\beta `$).

For massive particles ($`\epsilon =1`$) one or two circular orbits with radii $`r_\pm =\frac{L^2\pm \left(L^412\beta ^2L^2\right)^{\frac{1}{2}}}{2\beta }`$ are possible according to $`L^2=12\beta ^2,`$ or $`L^2>12\beta ^2,`$ respectively. If $`L^2<12\beta ^2,`$ then it is not hard to see that the particle is forced to move towards the singularity at $`r=0`$.

## 3  Newtonian limit of Jackiw’s scalar theory

Given that Einstein’s $`(2+1)`$-dimensional gravity exhibits such a drastic departure from the corresponding Newtonian gravity, one would wonder whether or not the present extension of Jackiw’s scalar gravity does have a Newtonian limit. This question is better examined if one considers Galilean coordinates, the ones in which

$$g_{\mu \nu }=\eta _{\mu \nu }+h_{\mu \nu },$$
(17)
with $`\eta _{\mu \nu }=diag(1,1,1,1)`$ and $`|h_{\mu \nu }|<<1`$. It is a well-known fact that for any metric theory of gravity small departures from Minkowski flat space-time lead to geodesic equation which, for a non-relativistic particle, perfectly mimic Newton’s equation of motion in a classical gravitational field, as long as the metric tensor is time- independent. On the other hand one expects that with the same kind of approximation the field equations should reduce to Poisson’s equation for the classical field. When these two conditions are consistently fulfilled, then one would say that the theory has a Newtonian limit.

Let us first briefly recall how the effect of a gravitational field of force can be obtained by using the geodesic equations of motions under the circumstances described above. Thus, consider the line element of a nearly Minkowskian metric tensor given by

$$ds^2=\left(dx^0\right)^2+\left(dx^1\right)^2+\left(dx^2\right)^2+h_{\mu \nu }dx^\mu dx^\nu ,$$
(18)
with $`x^0=ct`$, $`\mu ,\nu =0,1,2`$. If the geodesic curve is parametrized by the coordinate time $`t`$, then we have

$$\left(\frac{ds}{dt}\right)^2=c^2\left(1\beta ^2\frac{h_{\mu \nu }}{c^2}\frac{dx^\mu }{dt}\frac{dx^\nu }{dt}\right),$$
(19)
where $`\beta =\frac{v}{c}`$ and $`v`$ denotes the velocity of the particle along the geodesic. For non-relativistic motion $`\beta `$ is small and, in our approximation, only first-order terms in $`\beta `$ and $`h_{\mu \nu }`$ will be retained. Thus, to first order in $`h_{\mu \nu }`$ and $`\beta `$, (19) becomes

$$\left(\frac{ds}{dt}\right)^2c^2\left(h_{00}1\right).$$
(20)
Now, let us consider the geodesic equations

$$\frac{d^2x^\mu }{ds^2}+\mathrm{\Gamma }_{\alpha \beta }^\mu \frac{dx^\alpha }{ds}\frac{dx^\beta }{ds}=0.$$
(21)
Again, keeping only first-order terms in $`h_{\mu \nu }`$ and $`\beta `$, it can be easily verified that (21) becomes

$$\frac{d^2x^\mu }{ds^2}+\mathrm{\Gamma }_{00}^\mu \left(\frac{dx^0}{ds}\right)^2=0.$$
(22)
On the other hand, in this approximation, we have

$$\mathrm{\Gamma }_{00}^i=\frac{1}{2}\frac{h_{00}}{x^i},$$
(23)
for $`i=1,2`$. From (22) and (23) one gets

$$\frac{d^2x^i}{dt^2}=\frac{}{x_i}\left(\frac{h_{00}}{c^2}\right),$$
(24)
which looks like Newton’s equation of motion for a particle in a classical gravitational field provided that we identify the scalar gravitational field as being

$$\varphi =\frac{c^2}{2}h_{00},$$
(25)
and requiring that $`h_{00}`$ and $`\varphi `$ vanish at infinity. At this point let us linearize the field equation of Jackiw’s gravity theory by assuming the weak-field approximation (17). If matter is present Jackiw’s field equation is given by

$$R=kT,$$
(26)
where $`T=T_{}^{\mu }{}_{\mu }{}^{}`$ denotes the trace of the energy-momentum $`T_{\mu \nu }`$ and $`k`$ is constant. In the non-relativistic regime $`\frac{|T_{ij}|}{T_{00}}<<1`$, i.e., all stress are small compared to the density of energy $`T_{00}=\rho `$. Thus, we have $`T\rho `$. It remains to find the expression for the linearized $`R`$. This can be done simply by noting that to first order in $`h_{\mu \nu }`$ we have

$$R_{\mu \nu }=\frac{1}{2}\left(\mathrm{}^2h_{\mu \nu }\frac{^2}{x^\lambda x^\mu }h_{}^{\lambda }{}_{\nu }{}^{}\frac{^2}{x^\lambda x^\nu }h_{}^{\lambda }{}_{\mu }{}^{}+\frac{^2}{x^\mu x^\nu }h\right),$$
(27)
where $`h=h_{}^{\mu }{}_{\mu }{}^{}`$. Recalling that in this approximation indices are lowered and raised with the Minkowski metric tensor, from (9) one readily obtains

$$R=\mathrm{}^2h+\frac{^2}{x^\lambda x^\nu }h^{\lambda \nu }.$$
(28)
This equation can be simplified if we choose to work in the so-called harmonic coordinate system, that is, the one for which $`\frac{h_\nu ^\lambda }{x^\lambda }=\frac{1}{2}\frac{h}{x^\nu }`$.

Finally, if one assumes that the metric is not time-dependent, Jackiw field equation (26) turns into

$$^2\varphi =kc^2\rho \frac{c^2}{2}^2(h_{11}+h_{22}),$$
(29)
where use has been made of the equation (25). Given that the second term of the right-hand side of equation above does not vanish in general, (29) is not identical to Poisson’s equation for the classical gravitational field. It is worth mentioning, however, that in the static conformally flat case $`h_{\mu \nu }=ϵ\eta _{\mu \nu }`$, hence

$$R=\frac{3}{2}^2h_{00},$$
(30)
and a Newtonian limit can be defined, a result which was previously obtained by Cornish and Frenkel. Therefore, we conclude that the extension of Jackiw’s scalar theory to (2+1)-dimensional gravity does not lead to a theory with proper Newtonian limit, except for a few special metric configurations.

Acknowledgment
This work was partially supported by CNPq and CAPES. We are indebted to F. Dahia for enlightening discussions.