Ragavendran Gopalakrishnan

Jason R Marden

Adam Wierman

Characterizing distribution rules for cost sharing games

We consider the problem of designing the distribution rule used to share "welfare" (cost or revenue) among individually strategic agents. There are many distribution rules known to guarantee the existence of a (pure Nash) equilibrium in this setting, e.g., the Shapley value and its weighted variants; however a characterization of the space of distribution rules that yield the existence of a Nash equilibrium is unknown. Our work provides a step towards such a characterization. We prove that when the welfare function is strictly submodular, a budgetbalanced distribution rule guarantees equilibrium existence for all games (i.e., all possible sets of resources, agent action sets, etc.) if and only if it is a weighted Shapley value.

I. INTRODUCTION

How should the cost incurred (revenue generated) by a set of self-interested agents be shared among them? This fundamental question has led to a large literature in economics over the last decades [START_REF] Shapley | A value for n-person games[END_REF], [START_REF] Moulin | Serial cost sharing[END_REF], [START_REF] Young | Equity: In theory and practice[END_REF], [START_REF] Moulin | Strategyproof sharing of submodular costs: Budget balance versus efficiency[END_REF], [START_REF] Moulin | Axiomatic cost and surplus sharing[END_REF], and more recently in computer science [START_REF] Feigenbaum | Sharing the cost of multicast transmissions[END_REF], [START_REF] Anshelevich | The price of stability for network design with fair cost allocation[END_REF], [START_REF] Charikar | Online multicast with egalitarian cost sharing[END_REF], [START_REF] Chen | Designing network protocols for good equilibria[END_REF], [START_REF] Marden | Distributed welfare games[END_REF]. A classic framework within which to study this question is that of cost sharing games, in which there is a set of "agents" making strategic choices of which "resources" to utilize. Each resource generates a "welfare" (cost or revenue) depending on the set of agents that choose the resource. The focus is on finding budgetbalanced distribution rules that provide "stable" and/or "fair" allocations, which is traditionally formalized by the concept of the core -the set of feasible distribution rules that guarantee a stable grand coalition.

Recently, there is an emerging focus on weaker notions of "stability" and, in particular, a (pure Nash) equilibrium for the agents, which is our focus in this work. This focus is driven by applications such as network-cost sharing [START_REF] Anshelevich | The price of stability for network design with fair cost allocation[END_REF], [START_REF] Chen | Designing network protocols for good equilibria[END_REF] where individually strategic behavior is commonly assumed. Additionally, the notion of an equilibrium is natural if cost sharing distribution rules are used to design utilities for distributed agents in the context of a game-theoretic approach to distributed control [START_REF] Marden | Distributed welfare games[END_REF], [START_REF] Gopalakrishnan | An architectural view of game theoretic control[END_REF].

Existing literature on cost sharing games provides several distribution rules that guarantee equilibrium existence [START_REF] Shapley | A value for n-person games[END_REF], [START_REF] Shapley | Additive and non-additive set functions[END_REF], [START_REF] Wolpert | An introduction to collective intelligence[END_REF], [START_REF] Ui | Shapley value representation of potential games[END_REF]. Perhaps, the most famous such distribution rule is the Shapley value [START_REF] Shapley | A value for n-person games[END_REF], which guarantees the existence of a Nash equilibrium in any game, and for certain classes of games such as convex games, is always in the core. A generalization of the Shapley value which exhibits the same properties is the weighted Shapley value [START_REF] Shapley | Additive and non-additive set functions[END_REF].

Although (weighted) Shapley value distribution rules guarantee equilibrium existence, this is only one of many desirable properties. Perhaps the next most important property is that these equilibria should be "efficient" in the sense of maximizing the social welfare. In order to provide the tools necessary to optimize efficiency (and other properties) while still always ensuring equilibrium existence, researchers have recently sought to provide characterizations of the class of distribution rules that guarantee equilibrium existence. Providing such a characterization is the goal of this paper.

The first step toward this goal is the work of Chen, Roughgarden, & Valiant [START_REF] Chen | Designing network protocols for good equilibria[END_REF], who prove that the only budget-balanced distribution rules that guarantee equilibrium existence in all cost sharing games are weighted Shapley value distribution rules. Following on [START_REF] Chen | Designing network protocols for good equilibria[END_REF], Marden & Wierman [START_REF] Marden | Limitations of utility design for multiagent systems[END_REF] provide the parallel characterization in the context of revenue sharing games. Though the characterizations in [START_REF] Chen | Designing network protocols for good equilibria[END_REF] and [START_REF] Marden | Limitations of utility design for multiagent systems[END_REF] seem general, they actually provide only a worst-case characterization. In particular, the proofs in [START_REF] Chen | Designing network protocols for good equilibria[END_REF], [START_REF] Marden | Limitations of utility design for multiagent systems[END_REF] consist of exhibiting a specific "worst-case" welfare function which requires that weighted Shapley value distribution rules be used. Thus, the question of characterizing the space of distribution rules for any specific welfare function remains open. In practice, it is exactly this issue that is important: when designing a distribution rule, one knows the specific welfare function for the situation. In such a situation, there may be distribution rules other than weighted Shapley value rules that also guarantee the existence of an equilibrium. In particular, recent work has shown that such settings do exist [START_REF] Marden | Distributed welfare games[END_REF].

In this paper, we seek to provide a more detailed characterization of the space of distribution rules by understanding, for specific welfare functions, what rules guarantee the existence of a (pure Nash) equilibrium. In particular, our focus is on the class of submodular welfare functions. Submodular welfare functions are quite common and are found, for example, in power control and coverage problems in sensor networks [START_REF] Campos-Náñez | A game-theoretic approach to efficient power management in sensor networks[END_REF], [START_REF] Marden | Distributed welfare games[END_REF], wireless access point assignment and frequency selection [START_REF] Kauffmann | Measurement-based self organization of interfering 802.11 wireless access networks[END_REF], and influence maximization [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF].

Our main result (Theorem 2) states that, given any strictly submodular welfare function, only weighted Shapley value distribution rules guarantee equilibrium existence in all games. Thus, we show, perhaps surprisingly, that the result of [START_REF] Chen | Designing network protocols for good equilibria[END_REF] holds much more generally. In particular, we show that it is not the existence of some worst-case welfare function which limits the design of "desirable" distribution rules to weighted Shapley values. In fact, even under practical (submodular) welfare functions, the design of distribution rules is constrained to the weighted Shapley value. This characterization means that in many practical settings, it is possible to optimize other desirable properties (such as the "efficiency" of the equilibrium) within the class of weighted Shapley value distribution rules.

II. MODEL

In this work, we consider a simple, but general, model of a "welfare" (cost or revenue) sharing game, where there is a set of self-interested agents/players N = {1, . . . , n} who each choose from a set R = {r 1 , . . . , r m }, the resources to which to allocate themselves. Each agent i ∈ N is capable of selecting potentially multiple resources in R; therefore, we say that agent i has action set A i ⊆ 2 R . The resulting action profile, or (joint) allocation, is a tuple a = (a 1 , . . . , a n ) ∈ A where the set of all possible allocations is denoted by A = A 1 × . . . × A n . We occasionally denote an allocation a by (a i , a -i ) where a -i denotes the allocation of all agents except agent i.

Each allocation generates a welfare, W(a), which needs to be shared completely among the agents, i.e., the allocation is budget-balanced. In this work, we assume W(a) is (linearly) separable and scalable across resources, i.e., W(a) = r∈R v r W ({a} r ) where {a} r = {i ∈ N : r ∈ a i } is the set of agents that are allocated to resource r in a, v r ∈ R ++ is the local scaling factor of resource r, and W : 2 N → R is the welfare function that is scaled at each resource. These are standard assumptions, e.g., see [START_REF] Chen | Designing network protocols for good equilibria[END_REF], [START_REF] Marden | Distributed welfare games[END_REF], and are quite general. Note that this model incorporates both revenue and cost sharing games, since we allow for the welfare function W to be either positive or negative.

The manner in which the welfare is shared among the agents determines the utility function U i : A → R that agent i seeks to maximize. Because the welfare function is assumed to be separable and scalable, it is natural that the utility functions should follow suit. The motivation for scalability is selfevident. To motivate separability, note that this corresponds to welfare garnered from each resource being distributed among only the agents allocated to that resource, which is most often appropriate, e.g., in profit sharing. This results in

U i (a) = r∈ai v r f (i, {a} r ), where f : N × 2 N → R is the distribution rule, i.e., f (i, S)
is the fraction of the welfare allocated to agent i ∈ S when sharing with S. Recall that we require f to be budget-balanced, which means that for any player set S ⊆ N , i∈S f (i, S) = W (S).

To summarize, we can specify a welfare sharing game G using the tuple G = N, R, {A i } i∈N , {v r } r∈R , f, W , where the design of f is the focus of this paper.

The primary goals when designing f are to guarantee (i) equilibrium existence, and (ii) equilibrium efficiency. Our focus in this work is entirely on (i) and we consider pure Nash equilibria; however it should be noted that other equilibrium concepts are also of interest [START_REF] Su | Conjectural equilibrium in multiuser power control games[END_REF], [START_REF] Adlakha | Oblivious equilibrium: an approximation to large population dynamic games with concave utility[END_REF], [START_REF] Marden | State based potential games[END_REF]. Recall that a (pure Nash) equilibrium is an action profile a * ∈ A such that for each player i, U i (a * i , a * -i ) = max ai∈Ai U i (a i , a * -i ). The Shapley value [START_REF] Shapley | A value for n-person games[END_REF], one of the oldest and most commonly studied distribution rule in the cost sharing literature, is defined as

f SV (i, S) = T ⊆S\{i} (|T |)!(|S| -|T | -1)! |S|! (W (S ∪ {i}) -W (S)).
The importance of the Shapley value is that it is budgetbalanced and guarantees equilibrium existence in any game, regardless of its parameters. Further, it has many other desirable properties, e.g., it results in the game being a so-called "potential game" [START_REF] Ui | Shapley value representation of potential games[END_REF]. However, it has one key drawbackcomputing it is often intractable since it requires the calculation of exponentially many marginal contributions [START_REF] Conitzer | Computing shapley values, manipulating value division schemes, and checking core membership in multi-issue domains[END_REF].

There are generalizations of the Shapley value that maintain its properties. In particular, the weighted Shapley value [START_REF] Shapley | Additive and non-additive set functions[END_REF], which is defined as (ω is the vector of the player-specific weights)

f W SV (i, S; ω) = T ⊆S:i∈T ωi j∈T ωj   R⊆T (-1) |T |-|R| W (R)   ,
also guarantees equilibrium existence in any game.

III. RESULTS AND DISCUSSION

In the previous section, we discussed examples of budgetbalanced distribution rules that guarantee equilibrium existence in "welfare" (cost or revenue) sharing games. The goal of this paper is to characterize the space of all such distribution rules.

Towards this end, this paper builds on the recent work of Chen, Roughgarden, & Valiant [START_REF] Chen | Designing network protocols for good equilibria[END_REF] and Marden & Wierman [START_REF] Marden | Limitations of utility design for multiagent systems[END_REF], which takes the first steps toward providing such a characterization. The following result combines the main contributions of [START_REF] Chen | Designing network protocols for good equilibria[END_REF] and [START_REF] Marden | Limitations of utility design for multiagent systems[END_REF] into one statement. Let G(N, f ) denote the class of all games with a fixed player set N and budget-balanced distribution rule f . Note that this is a very general class; in particular, it includes games with arbitrary action sets and an arbitrary welfare function.

Theorem 1 [START_REF] Chen | Designing network protocols for good equilibria[END_REF], [START_REF] Marden | Limitations of utility design for multiagent systems[END_REF] All games in G(N, f ) possess a pure Nash equilibrium if and only if f is a weighted Shapley value.

Less formally, Theorem 1 states that if one wants to use a distribution rule that guarantees equilibrium existence for all possible welfare functions and for all possible action sets, then one is limited to the class of weighted Shapley value distribution rules. Though this result seems quite general, it is shown by exhibiting a specific "worst-case" welfare function for which this limitation holds. In reality, when designing a distribution rule, one knows the specific welfare function for the situation, and Theorem 1 claims nothing in this case. In particular, there may be other distribution rules that guarantee equilibrium existence for all games, and recent work has shown that there are settings where this is the case [START_REF] Marden | Distributed welfare games[END_REF].

Our main result shows that even for a fixed strictly submodular welfare function, the conclusion of Theorem 1 is still valid, i.e., weighted Shapley distribution rules are the only ones which guarantee equilibrium existence.

More specifically, let G(N, f, W ) denote the class of all games with a fixed player set N , budget-balanced base distribution rule f , and welfare function W . Note that G(N, f, W ) G(N, f ) because we have fixed the welfare function W (though arbitrary action sets are still allowed). We focus on welfare functions W that are strictly submodular, i.e., for player sets X, Y ⊆ N , W (X)+W (Y ) > W (X ∪Y )+W (X ∩Y ). A variety of problems such as power control and coverage problems in sensor networks [START_REF] Campos-Náñez | A game-theoretic approach to efficient power management in sensor networks[END_REF], [START_REF] Marden | Distributed welfare games[END_REF], wireless access point assignment and frequency selection [START_REF] Kauffmann | Measurement-based self organization of interfering 802.11 wireless access networks[END_REF], and influence maximization [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] all have submodular welfare functions.

We can now state our main result.

Theorem 2 Let W be a strictly submodular welfare function.

All games in G(N, f, W ) possess a pure Nash equilibrium if and only if f is a weighted Shapley value.

Though Theorem 2 and Theorem 1 are superficially very similar, Theorem 2 is much stronger. The key contrast between Theorems 1 and 2 is that Theorem 1 states that there exists a welfare function for which the distribution rule is required to be a weighted Shapley value in order to guarantee equilibrium existence, while Theorem 2 states that, for any strictly submodular welfare function, the distribution rule must be a weighted Shapley value to guarantee equilibrium existence. To highlight this, consider that the proof of Theorem 1 exhibits a welfare function, and shows the result for that specific case, while the proof of Theorem 2 allows working with an arbitrary strictly submodular welfare function.

One subtle implication of Theorem 2 is that if one hopes to use a distribution rule that always guarantees equilibrium existence in games with a strictly submodular welfare function, then one is limited to working within the class of "potential games", since weighted Shapley value distribution rules result in potential games [START_REF] Ui | Shapley value representation of potential games[END_REF]. This is, perhaps, surprising since a priori potential games are often thought to be a small, special case of games. However, this is useful since there are many well understood learning dynamics which guarantee convergence to equilibria in potential games [START_REF] Blume | The statistical mechanics of strategic interaction[END_REF], [START_REF] Marden | Joint strategy fictitious play with inertia for potential games[END_REF], [START_REF] Marden | Revisiting log-linear learning: Asynchrony, completeness and a payoff-based implementation[END_REF].

Theorem 2 also has some negative implications. First, the limitation to weighted Shapley value distribution rules means that one is forced to use distribution rules which are often intractable [START_REF] Conitzer | Computing shapley values, manipulating value division schemes, and checking core membership in multi-issue domains[END_REF], as discussed earlier. Second, Marden & Wierman [START_REF] Marden | Limitations of utility design for multiagent systems[END_REF] show that there are efficiency limits that hold for any weighted Shapley value distribution rule. In particular, under any weighted Shapley value distribution rule there exists a game where the best equilibrium has welfare that is a multiplicative factor of two worse than the optimal welfare.

We do not have space to provide the complete proof of Theorem 2, so we sketch an outline, highlighting the proof technique and the key steps involved, in the following.

Proof Sketch of Theorem 2:

First, note that we only need to prove one direction since it is well known that a weighted Shapley value distribution rule is budget-balanced and guarantees equilibrium existence in any resource allocation game [START_REF] Rosenthal | A class of games possessing pure-strategy nash equilibria[END_REF], [START_REF] Hart | Potential, value, and consistency[END_REF], [START_REF] Monderer | Potential games[END_REF]. Thus, in the remainder of this section, we discuss the proof technique for the other direction -for budget-balanced distribution rules that are not weighted Shapley values, there exists a game for which no equilibrium exists.

The general outline of the proof is as follows. We establish several necessary conditions for a budget-balanced distribution rule f that guarantees the existence of an equilibrium for all games in G(N, f, W ). Effectively, these necessary conditions eliminate any budget-balanced distribution rule that is not a weighted Shapley value and hence give us our desired result. We establish these conditions by a series of counterexamples which amount to choosing a resource set R, the respective values {v r } r∈R , and the associated action sets {A i } i∈N .

A key technique of the proof is that instead of working with W directly, we define a basis of simple welfare functions, and represent W using this basis, i.e., any W is equivalent to a linear combination of the basis welfare functions. The basis we use is the following class of T -welfare functions. For every player subset T ⊆ N , a T -welfare function is defined as:

W T (S) = 1, T ⊆ S; 0, otherwise. (1)
It can be shown that the set of all T -welfare functions forms a basis for the set of all welfare functions, i.e., given any welfare function W , there exists a set T ⊆ 2 N , and a sequence Q = {q T } T ∈T of non-zero weights indexed by T , such that:

W = T ∈T q T W T
From here on, we denote a welfare function by (T , Q), so the class of games defined in the theorem is denoted as G(N, f, T , Q). It is useful to think of the sets in T as being "coalitions" of players that contribute to the welfare function, and the corresponding coefficients in Q as being their respective contributions. Also, for simplicity, we assume that W (∅) = 0 and therefore, ∅ / ∈ T .

Warmup, a single T-welfare function: To build some intuition, we first present the proof outline for an isolated Twelfare function, i.e., for a W where |T | = 1 above. This step consists of establishing the following necessary conditions for a budget-balanced f for any subset S ⊆ N of players: (a) If the coalition T is not formed in S (T S), then f does not allocate any utility to the players in S. (b) If the coalition T is formed in S (T ⊆ S), then f distributes the resulting welfare only among the contributing players (players in T ). Therefore, players in S -T , if any, get nothing. (c) If the coalition T is formed in S (T ⊆ S), then f distributes the welfare among players in T as if all other players (players in S -T ) were absent. It is easy to see that any budget-balanced f that satisfies the above conditions is completely specified by |T | -1 values, namely the values of f (i, T ) for any |T | -1 players in T . Further, it can be shown that f (i, T )f (j, T ) ≥ 0 for all i, j ∈ T . The proof is complete by observing that such an f is indeed a weighted Shapley value distribution rule, where the weight of player i ∈ T is given by ω i = f (i,T ) q T , and the weights of the other players are arbitrary.

To provide an idea of the proof technique we use to establish the above necessary conditions, in the following we prove (a). Proof of (a): Formally, we need to prove that any budgetbalanced f that guarantees equilibrium existence in any game G ∈ G(N, f, {T }, {q T }) satisfies f (i, S) = 0 for all i ∈ S when T S ⊆ N . We do so by induction on |S|. The base case, where |S| = 1 is trivially true, because from budget balance, we get that for any player i ∈ N ,

f (i, {i}) = q T , T = {i} 0 , otherwise
For the induction hypothesis, let us assume that (∀ S) (∀ i ∈ S) f (i, S) = 0, where T S ⊆ N and |S| = z, for some integer z satisfying 0 < z < |N |. Now, for |S| = z + 1, assume the contrary, that f (i, S) = 0 for some i ∈ S, where T S ⊆ N and |S| = z +1. Since f is budget-balanced, there has to be at least one other player j ∈ S that also satisfies this condition, such that f (i, S)f (j, S) < 0, that is, f (i, S) and f (j, S) have opposite signs. Without loss of generality, assume that f (i, S) < 0 and f (j, S) > 0. From the induction hypothesis, we know that f (i, S -{j}) = f (j, S -{i}) = 0. Players i and j have the same action sets -they can each choose either r 1 or r 2 . All other players in S have a fixed action -they choose both resources. This is essentially a game between players i and j. It is easy to see that none of the four possible action profiles is a Nash equilibrium, which is a contradiction. For example, (r 1 , r 1 ) is not a Nash equilibrium since f (i, S -{j}) > f (i, S), and so player i has an incentive to deviate to r 2 . This completes the inductive argument.

General welfare functions: We are now ready to outline the sequence of necessary conditions that make up the core of the proof for a general welfare function, (T , Q). Before continuing, we need to introduce some more notation. For any subset S ⊆ N , we denote by T (S) the set of all sets in T that are contained in S. That is, T (S) = {T ∈ T | T ⊆ S}. In other words, T (S) is the set of contributing coalitions in S. Also, let I(S) denote the set of players within T (S), that is, I(S) = T (S). In other words, I(S) is the set of contributing players in S.

The first three conditions mirror those stated above for an isolated T -welfare function -for any subset S ⊆ N of players, (a) If no coalition is formed in S (T (S) = ∅), then f does not allocate any utility to the players in S. (b) If any coalition is formed in S (T (S) = ∅), then f distributes the welfare only among players in I(S). (c) If any coalition is formed in S (T (S) = ∅), f distributes the resulting welfare among players in I(S) as if all other players (players in S -I(S)) were absent. It turns out that in the general case, these three conditions are not enough to complete the proof.

We next show that the conditions above imply that f can now be represented as a linear combination of basis weighted Shapley value distribution rules -for every player subset T ⊆ N , define a basis T -distribution rule parameterized by a positive vector ω T = ω T i i∈T as follows:

f T (i, S; ω T ) = ω T i k∈T ω T k , i ∈ T and T ⊆ S 0 , otherwise (2)
It is easy to see that ( 2) is the weighted Shapley distribution rule for its corresponding T -welfare function defined in [START_REF] Adlakha | Oblivious equilibrium: an approximation to large population dynamic games with concave utility[END_REF], where the player weights are given by ω T . Formally, we show that for any budget-balanced distribution rule f that guarantees equilibrium existence in any game G ∈ G(N, f, T , Q), there exists a sequence of weight-vectors Ω = ω T T ∈T such that

f = T ∈T q T f T (3)
where each f T is a weighted Shapley value distribution rule for its corresponding T -welfare function, with weight vector ω T . Therefore, f is completely specified by a sequence of weight vectors Ω. Note that this is not yet enough to guarantee equivalence to a weighted Shapley value distribution rule, since a pair of players can have "inconsistent" weights in different coalitions. Thus, our final steps focus on deriving necessary consistency conditions for the weight vector Ω.

To guarantee consistency of the weights, we first show that if there is a pair of players common to two coalitions, then their weights in those two coalitions must be "consistent", i.e., they should be linearly dependent. More formally, we show that for every pair of subsets T 1 , T 2 ∈ T , every pair of players (i, j) such that {i, j} ⊆ T 1 ∩ T 2 ,

ω T1 i ω T2 i = ω T1 j ω T2 j
Finally, we show that all weight vectors in Ω must be consistent, i.e., there exists a global weight vector ω = (ω k ) k∈N , such that, for every T ∈ T , ω T and ω restricted to T are linearly dependent. Note that we use the fact that the welfare function is strictly submodular only for proving this final step.

From the form (3) for the distribution rule f , and the form (2) for the basis T -distribution rule, it is clear that scaling the local weight vectors by a constant does not affect the distribution rule. Therefore, it follows from our final result that any budget-balanced distribution rule f that guarantees the existence of an equilibrium in any game G ∈ G(N, f, W ), where W is strictly submodular, is completely specified by a global weight vector ω. The proof is complete by observing that, at this stage, f , in the form (3), is exactly the weighted Shapley value distribution rule for the welfare function (T , Q), with weight vector ω.

Fig. 1 .

 1 Fig. 1. Counter-example for (a) Now consider the game illustrated in Fig. 1 with resource set R = {r 1 , r 2 } and local resource coefficients v r1 = v r2 > 0.Players i and j have the same action sets -they can each choose either r 1 or r 2 . All other players in S have a fixed action -they choose both resources. This is essentially a game between players i and j. It is easy to see that none of the four possible action profiles is a Nash equilibrium, which is a contradiction. For example, (r 1 , r 1 ) is not a Nash equilibrium since f (i, S -{j}) > f (i, S), and so player i has an incentive to deviate to r 2 . This completes the inductive argument.


V Dujmović

W Evans

S Lazard

W Lenhart

G Liotta

D Rappaport

S Wismath

On Point-sets that Support Planar Graphs ⋆

A universal point-set supports a crossing-free drawing of any planar graph. For a planar graph with n vertices, if bends on edges of the drawing are permitted, universal point-sets of size n are known, but only if the bend-points are in arbitrary positions. If the locations of the bend-points must also be specified as part of the point-set, we prove that any planar graph with n vertices can be drawn on a universal set S of O(n 2 / log n) points with at most one bend per edge and with the vertices and the bend points in S. If two bends per edge are allowed, we show that O(n log n) points are sufficient, and if three bends per edge are allowed, Θ(n) points are sufficient. When no bends on edges are permitted, no universal point-set of size o(n 2 ) is known for the class of planar graphs. We show that a set of n points in balanced biconvex position supports the class of maximum degree 3 series-parallel lattices.

Introduction

A set of points supports the drawing of a graph G if there is a one-toone mapping f of the vertices of G to the points so that for all pairs of edges (a, b), (c, d) in G (where a, b, c, d are distinct), segments f (a)f (b) and f (c)f (d) do not intersect. A set of points that supports the drawing of all n-vertex graphs in some class is called universal for that class, or simply universal if the class is all planar graphs. The size of any universal point-set for planar graphs requires at least 1.235n points as shown by Kurowski [START_REF] Kurowski | A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs[END_REF] (see also Chrobak and Karloff [START_REF] Chrobak | A lower bound on the size of universal sets for planar graphs[END_REF]). Early graph drawing results, such as the canonical ordering technique of de Frasseix, Pach, Pollack [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF] and Schnyder's embedding [START_REF] Schnyder | Embedding planar graphs on the grid[END_REF] demonstrate that an n × n grid of points is a universal point-set. However, no universal point-set of size o(n 2 ) is known.

Smaller universal point-sets for sub-classes of planar graphs are known. For example, any outerplanar graph can be drawn on any set of n points in general position [START_REF] Gritzmann | Embedding a planar triangulation with vertices at specified points[END_REF]. Indeed, if the point-set is in convex position, then it supports exactly the family of outerplanar graphs. Determining other families of planar graphs for which universal point-sets of size n exist is an interesting problem. We examine a particular type of point-set, of size n, in which points are arranged in biconvex position, and show that it supports the drawing of all maximum degree 3 series-parallel lattices, a class of graphs that contains members that are not outerplanar. These notions are precisely defined in Section 2.

The main contributions in this paper are stated in Theorems 1 and 2, and pertain to universal point-sets for straight-line drawings, and drawings with bends respectively. Theorem 1. For all n, there exist universal point-sets of cardinality n that support the family of maximum degree 3 series-parallel lattices with n vertices.

Suppose we relax the definition of support to allow edges of the graph to map to polylines composed of (at most) k + 1 line segments. In other words, we allow edges that "bend" at most k times. In this case, universal point-sets of size n exist for two bends [START_REF] Kaufmann | Embedding vertices at points: Few bends suffice for planar graphs[END_REF] and even one bend [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF]. However, these results assume that the bend-points can be placed in arbitrary locations and these bend-points are not included as part of the universal point-set. It is natural to ask if there exists a point-set that supports all planar graphs where each vertex and each bend-point occurs at a point in the set. As before, we require all pairs of edges (a, b) and (c, d) (where a, b, c, d are distinct) to map to non-intersecting polylines. Previous to this paper, no such point-set of cardinality o(n 2 ) was known for any value of k. Extending the results of [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] and [START_REF] Kaufmann | Embedding vertices at points: Few bends suffice for planar graphs[END_REF] in a straightforward manner imply point-sets of size O(n 3 ). For k = 3, 2, 1, we present such universal point-sets of cardinality O(n), O(n log n), and O(n 2 / log n) respectively.

Theorem 2. For all n, there exist universal point-sets of cardinality O(n), O(n log n), and O(n 2 / log n) that support the drawing of all n-vertex planar graphs with at most 3, 2, or 1 bend per edge, respectively.

Table 1 summarizes our results in terms of which sets of planar graphs can be supported on point-sets of a given cardinality with a specified number of bends.

Preliminaries

We adopt standard notation from the graph drawing literature and we henceforth assume all graphs have n vertices. Many proofs are omitted for space reasons. Two of our results rely on point-sets that have a specific form; see, for example, Fig. 2. Two non-intersecting non-linear arcs of curves λ 1 and λ 2 are defined to be biconvex if: each of these arcs is simple and convex, the convex hull of their 4 endpoints completely contains the two arcs, and the line segment joining any point a of λ 1 to any point b of λ 2 does not intersect either arc of curve except at a and b; for simplicity, we refer to such arcs of curves as curves. Without loss of generality, we assume the existence of a horizontal line separating the two curves with λ 1 below λ 2 . A point-set all of whose points lie on two curves that are biconvex is in biconvex position. We note that point-sets in such a configuration have been used in other contexts under different names.

Universal Point-sets for Drawing Planar Graphs with Bends

In this section we establish Theorem 2 by constructing universal point-sets for each of the three cases: 3, 2 or 1 bend per edge allowed. A fundamental tool in our constructions for universal point-sets with bends is the following result proving the existence of a book embedding of planar graphs in which the edges are permitted to cross the spine [START_REF] Di Giacomo | Curve-constrained drawings of planar graphs[END_REF]. A monotone topological book embedding of a planar graph G is a planar drawing such that all vertices of G are represented as distinct points on a spine (i.e. the x-axis), and each edge is either represented as an arc in the bottom page (below the x-axis), or as an arc in the top page (above the x-axis), or as the concatenation of two arcs: the first (leftmost) in the bottom page and the second in the top page with their common crossing point between spine points. See Fig. 1.

Theorem 3 ([5]

). Every planar graph has a proper monotone topological book embedding which can be computed in linear time.

A Set of Θ(n) Points for Drawing Planar Graphs with Three Bends per Edge

Lemma 1. There exists a universal set of 10n -18 points that supports the drawing of planar graphs with 3 bends per edge.

Proof. Before introducing the (fixed) universal point-set, we first outline how the graph will be processed. Consider a proper monotone topological book embedding of the input graph (see Fig. 1). For each edge that intersects the spine, introduce a dummy vertex creating an augmented two page book embedding with the vertices of the spine drawn on a horizontal line. There are at most n + m 4n -6 vertices on the spine. Imagine a horizontal line slightly above the spine that intersects all arcs in the top page -call these points of intersection from left to right b 1 , . . . , b 2a where a is the number of arcs. Note that a 3n -6. Consider a point-set that lies on two curves in biconvex position and consists of 6n -12 points on the top curve and 4n -6 points on the bottom curve. Any such point-set is universal and supports the drawing of all planar graphs with at most three bends per edge. Refer to Fig. 2 for an example of the construction. For any specific graph, its augmented two page book embedding defines the drawing and requires at most 10n-18 points. The at most 4n -6 vertices on the spine (including dummy vertices) are assigned, in order, to the first points on the bottom curve. The bend-points b 1 , . . . , b 2a are assigned to the first 2a points of the upper curve in left to right order and then each arc in the top page is drawn using the associated bend-points. These polylines do not intersect since the upper curve is convex and any segment joining the two curves does not properly intersect these curves. The arcs in the bottom page can be drawn with no bends -they are cords of the bottom curve. Each arc in the top page uses two bend-points. Substituting a bend-point for each of the dummy vertices results in a drawing with at most three bends per edge.

Note that a sub-Hamiltonian planar graph corresponds exactly to a graph that has a two page (unaugmented) book embedding [START_REF] Di Giacomo | Curve-constrained drawings of planar graphs[END_REF]. Since such graphs do not require dummy vertices, they can be drawn with at most two bends per edge.

A Set of O(n log n) Points for Drawing Planar Graphs with 2 Bends per Edge

The geometric idea underlying our construction is as follows. Similar to Section 3.1, we draw the spine vertices of an augmented two page book embedding on a set of points that lie on a slightly concave curve close to the x-axis. This implies that all the arcs in the bottom page of the book embedding can be drawn as straight line segments. For arcs in the top page, if the arc is from the ith to the (i + j)th spine vertex, it is drawn to bend at a point at level j. We place approximately n/j bend-points approximately equally spaced in the x-dimension at level j, since only n/j top arcs can have "length" j. The bend-point that lies between the ith and (i + j)th spine vertices is used by this arc. Each level is at a y-coordinate that is large enough that the drawing of an arc that uses a bend-point at a lower level "nests" inside any drawing of an arc from the same vertex using a higher level bend-point. Of course, for each j > n/2, there can be only one arc of "length" j and it uses a single bend-point at level j. The total number of bend-points placed is O(n log n).

Lemma 2. There exists a universal set of O(n log n) points that supports the drawing of planar graphs with 2 bends per edge. Proof. The construction is similar to that in [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF]. We recall briefly this construction, referring to Figures 1 and3. Given a planar graph G with n vertices, we embed the graph on vertices p i = (-2 i , i) for i = 0, . . . , n -1 with at most one bend per edge, as follows. We first compute a proper monotone topological book embedding, Γ of G. We relabel the vertices of that book embedding from right to left, as v 0 , . . . , v n-1 . We then map these vertices to p 0 , . . . , p n-1 , respectively. All the edges below the spine are drawn as straight-line segments. The others are drawn with a bend point as follows. Consider an edge whose rightmost vertex is v i and that intersects the spine on the interval (v u , v u+1 ] (inclusive v u+1 for the case where the leftmost endpoint of the edge is v u+1 ). Such an edge is drawn with a bend point at the same height as v u , and in the vertical strip delimited by v i and v i+1 . A universal set of points for the bend location can easily be determined in this construction. However, this construction requires a set of size Θ(n 3 ) for the bend points since there need to be n bend points on each of n bend lines, and in each of n -1 vertical strips (delimited by v i and v i+1 ).

This construction can be modified to contain only a subquadratic universal set of points for the bends, while preserving a linear size universal set of points for the vertices. We consider as before a proper monotone topological book embedding, Γ of our input graph G. We then add on the spine extra isolated dummy vertices so that there is at most one edge crossing the spine between any two spine vertices. Since the number of edges of a planar graph is at most 3n -6, we add at most that number of isolated vertices and the total number of vertices is less than 4n. Let G ′ be the resulting graph. Note that, if we use the construction of [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] with this augmented graph G ′ , there is at most one bend point on each bend line; this yields that, for every bend line, we need only consider one candidate location for the bend points in each vertical strip, leading to a quadratic universal set of points for the bends.

To obtain a subquadratic size we first construct a set of 4n points p 0 , . . . , p 4n-1 as in [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] that will support the vertices of any augmented graph G ′ . Now on the bend line at height k, we place k/ log k candidate vertices for the bend points of the edges that intersect the spine through the window p k p k+1 . The points on the bend-line at height k are defined as follows. See Fig. 4. The first (rightmost) point q 1 lies infinitesimally to the right of the line p 0 p 1 . Let p u 1 be the rightmost point of p 0 , . . . , p 4n-1 that is to the left of q 1 . The second point q 2 is infinitesimally to the right of the line p u 1 p u 1 +1 (at height k), and so on.

p k Bend-line at height k p ui p ui+1 p ui+1 q ui q ui+1 . . . (2 ui+1 -2 ui )(k -u i ) x y
The addition of dummy points on the spine ensured that there is at most one edge that intersects the spine between two vertices on the spine. Hence, for any given graph, there is at most one bend point used on any bend line. This essentially implies that the construction of [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] works here.

How many bend points are there on a bend-line? It can be shown that there are Θ(k/ log k) candidate bend points on the bend line at height k, and Θ(n 2 / log n) candidate bend points in total.

Biconvex Point-sets and Series-Parallel Graphs

A two terminal series-parallel digraph (also called TTSP-digraph) is a planar digraph recursively defined as follows [START_REF] Di Battista | Graph Drawing[END_REF][START_REF] Valdes | The recognition of series-parallel digraphs[END_REF]: A directed edge joining two vertices forms a TTSP-digraph. Let G ′ and G ′′ be two TTSPdigraphs; the digraph obtained by identifying the sink of G ′ with the source of G ′′ (Series Composition) is also a TTSP-digraph. Let G ′ and G ′′ be two TTSP-digraphs; the digraph obtained by identifying the source of G ′ with the source of G ′′ and the sink of G ′ with the sink of G ′′ (Parallel Composition) is also a TTSP-digraph.

A TTSP-digraph has one source and one sink which are called its poles. Also, a TTSP-digraph is always acyclic and admits a planar embedding with the poles on the same face. A TTSP-digraph is a TTSP lattice if for every edge (u, v), there is no directed path from u to v that does not contain (u, v). Note that a TTSP lattice cannot have multiple edges.

The undirected underlying graph of a TTSP-digraph (resp. lattice) is called a TTSP-graph (resp. TTSP-lattice). We further shorten these terms and refer to them as series-parallel (SP).

Any point-set in general position supports the class of outerplanar graphs [START_REF] Gritzmann | Embedding a planar triangulation with vertices at specified points[END_REF]. Indeed a point-set in convex position supports exactly the class of outerplanar graphs, and no other planar graphs. Motivated by this insight we now consider the class of planar graphs that are supported by a point-set in which n/2 points are on one convex curve and the remainder are on another convex curve -in biconvex position. Clearly outerplanar graphs can be supported by this point-set and efficient algorithms such as that developed by Bose [START_REF] Bose | On embedding an outer-planar graph on a point set[END_REF] exist. We show that any (n/2, n/2) biconvex point-set is universal for a subclass of the series-parallel graphs. Since our purpose is to exhibit universal point-sets for classes of planar graphs, the balancing condition is critical and since the number of vertices could be odd, the balancing must allow for one vertex to be placed arbitrarily.

A planar graph G is biconvex if there exists a crossing-free straightline drawing Γ of G with all vertices located on the curves λ 1 and λ 2 . A planar graph G is balanced biconvex if it is biconvex with a drawing Γ in which the numbers of vertices on the two curves differ by at most one; more formally if: for n even, n/2 vertices are on λ 1 and n/2 vertices on λ 2 (called uniform and denoted as Γ = ), and for n odd, either:

-n-1
2 vertices are on λ 1 and n+1 2 vertices are on λ 2 (called top-heavy and denoted as Γ + ) or -n+1

2 vertices are on λ 1 and n-1 2 vertices are on λ 2 (called bottom-heavy and denoted as Γ + )

Our construction is recursive and attempts to contain the drawing of the SP lattice in a box spanning the biconvex curves with a balanced number of vertices on each curve and with s and t forming a diagonal of the box. Unfortunately, such a strong invariant cannot be maintained and slightly weaker conditions must be carefully considered.

A series-parallel digraph with poles s and t is bottom-cornered if it is balanced biconvex with a drawing Γ (n even) or Γ + (n odd) such that:

1. there exists a box (i.e. a convex quadrilateral) B(s, t) with s on λ 1 and t on λ 2 , st forms one diagonal of B, and the other diagonal has one corner on λ 1 and one on λ 2 , and 2. the entire drawing lies inside B.

Similarly, a series-parallel digraph with poles s and t is top-cornered if it is balanced biconvex with a drawing Γ (n even), or Γ + (n odd) such that conditions 1 and 2 hold. If a series-parallel graph is both top-cornered and bottom-cornered, it is called double-corneredi.e. if n is odd, there exist two drawings Γ + and Γ + both of which satisfy conditions 1 and 2.

In some situations, only weaker conditions on the drawings can be maintained, in which one of t or s is contained strictly inside a box rather than on the diagonal forming the box: 1 ′ . there exists a box B(s, x) with s on λ 1 and x on λ 2 , sx forms one diagonal of B(s, x), and the other diagonal has one corner on λ 1 and one on λ 2 and t is on λ 2 inside B(s, x). 1 ′′ . there exists a box B(x, t) with x on λ 1 and t on λ 2 , xt forms one diagonal of B(x, t), and the other diagonal has one corner on λ 1 and one on λ 2 and s is on λ 1 inside B(x, t).

A series-parallel graph with source s and sink t is bottom half-cornered if it is balanced biconvex and conditions 1' and 2 hold; similarly, if conditions 1" and 2 hold, then the graph is top half-cornered.

In the lemmas that follow, we demonstrate only the existence of biconvex drawings for the graphs that we consider. The following lemma indicates that this is sufficient to claim a universal biconvex point-set of suitable size. A series-parallel graph in which every vertex is of maximum degree 3 is denoted as 3SP. We distinguish between two critical cases. If both the source and sink of a 3SP lattice have degree 2 then the graph is called thin and otherwise (i.e. if either pole has degree 3) it is called thick. It is the class of 3SP lattices that we show to be balanced biconvex. There are several cases to consider depending on whether the graph is biconnected or not, and whether the graph is thin or thick. Our proof is recursive in nature -interior components are replaced by appropriate balanced boxes. Lemmas 5 -14 distinguish and organize these cases and Fig. 5 provides a simple example of each case, the type of drawing obtained, and the prerequisite lemmas used in the proof. Lemma 5. A simple path consisting of n 2 vertices from s to t is double-cornered.

First we present the lemmas used for subcases that are thin: biconnected and then not biconnected. Lemma 6. Let G be a biconnected thin 3SP lattice. Then G is doublecornered.

Lemma 7. Let G be a thin 3SP lattice with source s and sink t. The next sequence of lemmas pertains to the cases when the global poles have degree 3. The drawings obtained rely on the previous lemmas and are balanced biconvex, but may not be double-cornered. In the final case, G is not biconnected and at least one of the global poles has degree 3. Lemma 14. Let G be a thick 3SP lattice with source s and sink t. If deg(s) = 3 or deg(t) = 3 then G is balanced biconvex.

If either deg(s) = deg(t) = 1 or deg(s) = deg(t) = 2 then G is double-cornered.
Biconvex point-sets are the only known point-sets of size n that universally support some class of planar graphs other than the outerplanar graphs.

Conclusions and Open Problems

Our main contributions in this paper are stated in Theorems 1 and 2: that any balanced biconvex point-set supports the straight-line drawing of any 3SP lattice, and the specification of universal point-sets for drawings of any planar graph with a small number of bends per edge.

Closing the gap between the upper and lower bounds of the cardinality of a universal point-set for planar graphs with no bends allowed remains an open problem. When k bends per edge are permitted, universal pointsets of smaller asymptotic cardinality may be determined for k = 1, 2.

w 5 w 6 w 7 w 0 w 7 w 4 w 5 w 6 w 2 w 3 w 1 Fig. 1 .

 11 Fig. 1. A graph and a monotone topological book embedding of it.

w 0 w 7 w 4 w 5 w 6 w 2 w 3 w 1 Fig. 2 .

 12 Fig. 2. Example drawing of the graph of Fig. 1 on a biconvex point-set using three bends per edge. The curvature is exaggerated and only the first 14 of the 36 upper curve points and 11 of the 26 lower curve points in the universal point-set are shown.

3. 3 A

 3 Set of O(n 2 / log n) Points for Drawing Planar Graphs with 1 Bend per Edge Lemma 3. There exists a universal set of O(n 2 / log n) points that supports the drawing of planar graphs with 1 bend per edge.

5 Fig. 3 .

 53 Fig.3. The one-bend drawing of the three top-page edges adjacent to v0 = w1 in the graph of Fig.1following the construction of[START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF]. The points p6 and p7 are not shown since the figure is to scale.

Fig. 4 .

 4 Fig. 4. Placement of bend points on the bend-line at height k. The figure is not to scale.

Lemma 4 .

 4 If a graph G on n vertices has a balanced biconvex drawing, then every balanced biconvex point-set of size n supports G.

Lemma 8 .

 8 Let G be a thin 3SP lattice with source s and sink t. If deg(s) = 1 and deg(t) = 2 then G is bottom-cornered. Lemma 9. Let G be a thin 3SP lattice with source s and sink t. If deg(s) = 2 and deg(t) = 1 then G is top-cornered.

  s

Fig. 5 .

 5 Fig. 5. Roadmap of the various cases

Table 1 .

 1 Summary of results -cardinality of universal point-sets for classes of graphs. The first and last results are well-known. All other results are new.

	Graphs	Number of Points Number of Bends Reference
	outerplanar	n	0	[7]
	3SP lattice	n	0	Thm 1
	planar	O(n)	3	Thm 2
	planar	O(n log n)	2	Thm 2
	planar	O(n 2 / log n)	1	Thm 2
	sub-Hamiltonian	O(n)	2	Lemma 3.1
	sub-Hamiltonian	O(n log n)	1	Lemma 3.2
	planar	O(n 2 )	0	[3],[10]

⋆ This paper was initiated at the 2011 McGill/INRIA/UVictoria Bellairs workshop. Discussion with other participants is gratefully acknowledged. Research supported by NSERC, and by MIUR of Italy under project AlgoDEEP prot. 2008TFBWL4.


Bogumil Jeziorski

O n l y Multireference Coupled Cluster Ansatz

Keywords:

The origin of the multireference coupled cluster Ansatz for the wave function and the wave operator, discovered in Quantum Theory Project in 1981, is presented from the historical perspective. Various methods of obtaining the cluster amplitudes -both state-universal and state-selective are critically reviewed and further prospects of using the multireference coupled cluster Ansatz in electronic structure theory are briefly discussed.

In the late 1970's it has become clear that the coupled cluster (CC) theory, initiated in nuclear physics [1,2] and developed after a while for quantum chemical applications [3][4][5], is a very promising -formally attractive and potentially accurate -computational tool for the electronic structure theory [6,7]. For an enlightening, firsthand account of the origins of the CC theory the reader is referred to Refs. 8-11. In 1978/1979 I was visiting the Department of Physics, University of Utah, and became familiar with the coupled cluster work done in Salt Lake City by Frank Harris [START_REF] Harris | [END_REF] and Henk Monkhorst [13]. I was very impressed by the mathematical beauty and power of the coupled cluster theory, and in particular by the global insight it provided into -at that time -formidably complex structure of the manybody perturbation theory (MBPT). In fact, shortly after I joined Harris's group we used the coupled cluster Ansatz to propose a simple scheme for generating an explicitly connected form of the MBPT expansion in an order-by-order fashion [14,15]. We realized at that time that the success of the CC approach relies heavily on the availability of a single, preferably closed-shell, reference determinant Φ, providing a reasonably good approximation to the exact wave function Ψ. It was therefore clear to us that a development of an appropriate generalization of the CC method to quasidegenerate/multireference situations is important and very timely.

We were not the first to be aware of this challenge. A simple solution of the problem, that suggests itself rather naturally, appears to be possible if the determinant Φ is replaced by a multideterminantal approximation Ψ 0 to Ψ obtained, e.g., from spin-symmetry considerations, or from an MCSCF-type optimization. Thus, in the conventional CC Ansatz Ψ = e T Φ, (1) the single determinant Φ may be substituted by, say, an MCSCF wave function Ψ 0 , as proposed by Banerjee and Simons [16]. The problem with this solution is that the form of the cluster operator T relies strongly on the single-determinant form of Φ and on the classification of orbitals defined by Φ. Specifically, T is a linear combination of single, double, etc. excitation operators replacing a set of orbitals occupied in Φ by a set of virtual orbitals (i.e., orbitals orthogonal to all orbitals occupied in Φ). These excitation operators are usually expressed via the conventional fermion creation (a † r ) and annihilation (a α ) operators, e.g., the two-body part of T takes the form

T 2 = α<β r<s t αβ rs a † r a † s a β a α , (2)
where t αβ rs are cluster amplitudes, but an equivalent first-quantized representation through integral ("ket-bra") operators is also possible [17], e.g.,

T 2 = i<j t2 (ij), (3) t2
= α<β |τ αβ φ α φ β |, (4)
where i and j label electronic coordinates, including spin, φ α , φ β are spinorbitals occupied in Φ, and τ αβ (ij) are pair functions expanded usually (but not always [17]) in terms products of virtual orbitals φ r (i)φ s (j). Using either the first-or the second-quantized representation of T one can easily show that T is uniquely defined by Ψ and that any wave function can be represented in the form of Eq. ( 1). One can also show [16] that any wave function which is orthogonal neither to Φ nor to Ψ 0 can be represented as Ψ = e S Ψ 0 with S uniquely defined by Ψ, but only if the excitation structure of S is the same as that of T , and is defined via equations of the form of Eqs. ( 2) and (3), i.e., relative to a single determinant Φ. It would be desirable, however, to define S in a way that would not be biased towards a single determinant but would treat all determinants in Ψ 0 on equal footing. Unfortunately, it appears that no construction of the Ansatz of the form Ψ = e S Ψ 0 proposed so far: (i) treats all basic determinants in a symmetric way, (ii) leads to cluster amplitudes uniquely defined by Ψ, and (iii) is capable to represent the exact wave function. It should be noted however, that multireference (MR) coupled cluster methods employing the Ansatz Ψ = e S Ψ 0 , and biased towards a single determinant, have been proposed [18][19][20][21] and used with a considerable success in practical applications [22][23][24][25][26].

An entirely different, and a much more general approach was proposed by Offermann, et al [27,28], Mukherjee et al [29]. and by Lindgren [30] (see also an early, insightful attempt by Mukherjee et al [31,32] and subsequent Fock-space formulations [33][34][35][36][37]). In this approach the exponential Ansatz (most often in the so-called normal ordered form) is used to represent not a single wave function, but a wave operator mapping a manifold of simple multideterminantal functions (the model space) onto the exact solutions of the Schrödinger equation. A special feature of this Ansatz is its valence universality [29] (VU), meaning that a single cluster operator applies to systems with different numbers of valence electrons. With a proper choice of the model space this valence-universal Ansatz is exact and the cluster amplitudes are uniquely defined by the FCI wave functions from several layers (sectors) of the Fock space [38]. It also turns out that only in one layer of the Fock space is the normal-ordered valence-universal Ansatz truly exponential, and in this layer it coincides with the conventional Ansatz of Eq. ( 1). In other layers, corresponding to systems with attached or removed electrons, the Ansatz becomes really linear [28,38]. This has the consequence that the cluster amplitudes can be obtained by diagonalization of an appropriate matrix. In fact, the energies of ionized or excess-electron states obtained by applying the VU Ansatz [i.e., using the VU-CC or Fock-space (FS-CC) theory] turned out to be identical [39][40][41][42] with the energies of the IP-EOM-CC [43][44][45] and EA-EOM-CC [46][47][48] theories. For the excitation energies there is no equivalence with the conventional EE-EOM-CC method [49][50][51], but still, in view of the factual linearity of the Ansatz, the excited state wave functions of the VU-CC method can be directly obtained from diagonalization of an intermediate Hamiltonian [42,52], or a suitable matrix representation of the Bloch equation [53]. In conclusion, from the present-day perspective the VU-CC Ansatz is not really a multireference CC Ansatz. Similarly as in the EOM-CC theory, this is a conventional single reference Ansatz for the initial state, and a linear Ansatz for the ionized, excess-electron or excited states. As shown in the next section, a genuine multireference CC Ansatz, capable of correctly describing dissociation of a chemical bond, cannot be based on a single exponential function.

II. FORMULATION OF THE MRCC ANSATZ FOR THE WAVE FUNCTION AND THE WAVE OPERATOR

The fundamental feature of the coupled cluster Ansatz of Eq. ( 1) is the connected nature of the cluster operator T . Physically, this means that that cluster amplitudes, e.g., a twobody one t αβ rs , vanish when the spinorbitals -φ α , φ β , φ r , and φ s in this case -are localized, and one or more of them moves away to infinity and cease to interact with the remaining ones. Equivalently, when the whole system dissociates into two localized subsystems A and B separated by a distance R, the cluster operator T becomes the sum of the cluster operators (5)

Eq. ( 5) may be viewed as a justification of the exponential Ansatz. If this equation did not hold, the exponential Ansatz would not make sense. It is instructive to see the proof of Eq. ( 5). We assume that when R → ∞, our N -electron system separates into an N Aand N B -electron subsystems described by wave functions Ψ A and Ψ B , respectively. Each of these wave functions can be represented with its own exponential Ansatz

Ψ A = e T A Φ A Ψ B = e T B Φ B , (6)
defined in terms of orbitals localized at A and B, respectively. The virtual and occupied orbitals on each subsystem may be assumed to have zero differential overlap in the limit R → ∞. If we also assume that [54,[START_REF] Jeziorski | Molecular Interactions[END_REF] lim

R→∞ Ψ(1, . . . , N ) = A Ψ A (1, . . . , N A ) Ψ B (N A + 1, . . . , N ), ( 7
)
where A is the N -electron antisymmetrizer normalized such that

A 2 = N !/(N A !N B !) A,
. , N ) = e T A (1,...,N )+T B (1,...,N ) A Φ A (1, . . . , N A ) Φ B (N A + 1, . . . , N ), (9)
since now the antisymmetrizer A commutes with the exponential. Noting also that Φ ≡

A Φ A (1, . . . , N A ) Φ B (N A + 1, . . . , N ), we finally obtain lim R→∞ Ψ ≡ lim R→∞ e T Φ = e T A +T B Φ, (10)
where all wave function arguments 1, . . . , N were suppressed for brevity reason. Eq. [START_REF] Paldus | Theory and Applications of Computational Chemistry: The First 40 Years[END_REF] shows that indeed T → T A + T B when R → ∞, i.e., the validity of Eq. (5). The validity of the proof given above depends upon the validity of Eq. ( 7). This equation holds when a closed-shell system dissociates into closed-shell fragments, or in the case of dissociation of high-spin systems when the product Ψ A Ψ B is in a pure spin state. Eq. ( 7)

does not hold, however, when a singlet state dissociates into two doublet states, i.e., in the case of breaking the simplest chemical bond. In such a case Eq. ( 5) is not valid, and the exponential Ansatz is not useful at large R.

In general, when a low-spin system dissociates into high-spin ones, Eq. ( 7) must be modified by inserting a spin-projection operator Π in front of the antisymmetrizer A. In the simplest case, when a singlet dissociates into two doublets one can easily show (by inspecting relevant spin functions) that both at the correlated or independent-particle level the spinprojection can be effected by the projection operator Π = 1 2 (1 + Rπ/2 ), where the operator Rπ/2 rotates the spin functions α and β by 90 o , i.e., performs the operation α → β, β → -α.

Substituting Π A for A in Eq. ( 7), and following the reasoning presented between Eqs. ( 7) and ( 10), we find that now the asymptotic, large-R form of the wave function Ψ is lim

R→∞ Ψ = 1 2 (1 + Rπ/2 ) e T A +T B Φ = 1 2 e T Φ + 1 2 e T Φ , (11)
where Φ = Rπ/2 Φ, T = T A +T B , and T = Rπ/2 T Rπ/2 . It should be noted that the function 2 -1/2 (Φ + Φ ) represents the conventional independent particle approximation to open-shell singlet, and that the operator T is defined in the standard way but relative to the vacuum Φ . Eq. [START_REF] Bartlett | Theory and Applications of Computational Chemistry: The First 40 Years[END_REF] shows that for the dissociation to open-shell fragments a single exponential cannot be adequate, since asymptotically, at large R, the wave function does not factorize in the conventional way, given by Eq. (7). Only if we represent the wave function as a sum of exponentials, we have a chance that at large R the cluster operators will separate as T A + T B , with T A and T B equal or simply related to fragment's cluster operators.

Generalizing Eq. ( 11) to more complicated spin projections, and to even more general situations, when the asymptotics cannot be obtained by projection [START_REF] Klein | [END_REF]57], we can conjecture that a general quasidegenerate/multireference wave function can be written in the form

Ψ = M µ=1 c µ e T µ Φ µ , (12)
where Φ µ , µ = 1, . . . , M are determinants needed to obtain a correct zeroth-order approximation to Ψ, and each of the cluster operators T µ is defined with respect to its own vacuum Φ µ . Eq. ( 12) is just the multireference coupled cluster Ansatz which Henk Monkhorst and myself proposed [58] during my first visit to QTP in 1981.

When Eq. ( 12) is formally applied to a set of quasidegenerate states, one obtains the following exponential Ansatz for the wave operator

U U = M µ=1 e T µ P µ , (13)
where P µ =| Φ µ Φ µ | and the operators T µ are universal for all exact states Ψ ν in the range of U . The wave operator U is usually intermediately normalized such that P U = P and U P = U , where

P = M µ=1 P µ . (14)
With this normalization, U may be viewed an the inverse of P if the domains of U and P are restricted to the manifolds spanned by the set of Ψ ν 's and Φ µ 's, respectively. One can easily

show [58] that U is a non-orthogonal projector, U 2 = U , and that it satisfies the so-called

Bloch equation [59]

HU = U HU, (15)
where H is the Hamiltonian of the system. Because of the universal character of T µ operators, the applications of Eq. ( 13) are usually referred to as the state-universal (SU) CC theories. Using Eq. ( 12), geared specifically to treat a single quantum state, leads to the state-selective (SS) MRCC methods.

The usefulness of Eq. ( 12), or Eq. ( 13), depends on the possibility of providing a proof that the amplitudes of T µ 's are connected and, in the final instance, on the quality of numerical results obtained using the Ansätze of Eqs. ( 12) and (13). The existence of the connectedness proof depends, in turn, on the specific method chosen to define approximate cluster amplitudes and is not guaranteed by Eqs. ( 12) and ( 13) themselves.

Since 1981 there appeared a large number of applications of Eqs. ( 12) and ( 13). The literature presenting these applications, or formal discussion of the Ansätze ( 12) and ( 13) includes now about 500 positions and is still growing. It is impossible to cite this literature here or even to acknowledge most of the significant contributions to the field of MRCC theory based on the Ansätze [START_REF] Harris | [END_REF] or Eq. ( 13). Fortunately, there are two excellent reviews devoted specifically to this subject and the reader is referred to these reviews for bibliographical 12). In the two remaining sections of this perspective article I shall concentrate on the main features of state-universal and state-selective MRCC approaches which rely directly upon the application of Eq. [START_REF] Harris | [END_REF] or Eq. ( 13).

III. STATE-UNIVERSAL CC THEORY

The SU-CC theory is formally simplest if one assumes that the model space M 0 , spanned by all determinants Φ µ , is complete, i.e., invariant under unitary transformations of active orbitals (orbitals occupied in some but not in all Φ µ 's). In such a case the operators T µ do not contain amplitudes with exclusively active labels. One can show that the knowledge of the operator U of the form of Eq. ( 13) is equivalent to the knowledge of all M full configuration interaction (FCI) solutions for the states Ψ µ and that the cluster amplitudes defining T µ operators can be uniquely expressed via the linear coefficients of these FCI solutions and vice versa [38,[START_REF] Paldus | [END_REF]. To obtain equations from which T µ 's can be directly computed, we insert Eq.

(13) into Eq. ( 15), multiply the resulting equations from the right by | Φ µ , premultiply by exp(-T µ ) from the left and project against all excited states from the space M ⊥ 0 orthogonal to M 0 . The resulting SU-CC equation is

δT µ Φ µ | e -T µ H e T µ Φ µ = M ν =µ H eff νµ δT µ Φ µ | e -T µ e T ν Φ ν , (16)
where H eff νµ is the effective Hamiltonian matrix [59]

H eff νµ = Φ ν | e -T µ He T µ Φ µ ( 17
)
and δT µ is an arbitrary variation of T µ , i.e., in practice, an arbitrary excitation operator contributing to T µ . The SU-CC energies are obtained by diagonalizing the (nonsymmetric) matrix H eff νµ . The l.h.s. of Eq. ( 16) has the same form as the single-reference CC equation and is usually referred to as the direct term. The r.h.s. is referred to as the coupling term and is characteristic of the MR theory. Assuming the completeness of the model space M 0 , one can prove [58] that the perturbation expansion of H eff νµ and of the amplitudes of T µ contains only connected diagrams, i.e, that the effective Hamiltonian and the cluster operators are connected objects. It should be noted that to represent the effective Hamiltonian in the explicitly connected form (17) one has to assume that

(T µ ) † Φ ν = 0. ( 18
)
This equation holds only if the model space M 0 is complete.

Kucharski and Bartlett [63,64] proposed another form of the SU-CC equation. For the complete model spaces their equation

δT µ Φ µ | (H -H eff µµ ) e T µ Φ µ = M ν =µ H eff νµ δT µ Φ µ | e T ν Φ ν , (19)
is equivalent to Eq. ( 16). The subtraction of H eff µµ from H on the l.h.s. leads to cancellation of numerous disconnected (and unlinked terms) but some disconnected ones (which, however, are linked) remain in the direct term. The coupling term in Eq. ( 19) is significantly simpler to code than the one in Eq. (16). For this reason the Kucharski-Bartlett form has been often used in practical applications [65][66][67][68][69][70][71][72][73]. Equation ( 19) is manifestly finite, what may not be immediately clear in the case of Eq. ( 16), especially when the Baker-Campbell-Hausdorff formula is used to expand the product of exponentials in terms of commutators.

In practical applications the cluster operators are expanded either in terms of spinorbital excitations, as in Eq. (2), or using the unitary group generators [74,75] to preserve the spin symmetry of reference functions. Among early applications the former approach was adopted, e.g., in Refs. 65-69, 72, 73, 76, while the latter in Refs. 77-84. These early applications, carried out for very small model spaces and usually at the CCSD level of theory, have shown that the SU-CC method is capable of providing very accurate results, as long as no intruder states are present, in particular when reference determinants are degenerate or almost degenerate. As an example one can mention excellent results for the dissociation of the Li 2 molecule [66], for the singlet-triplet splitting in methylene [73,83] or for the lowest singlet-singlet energy gap in methylene [81].

These early calculations have also shown [START_REF] Paldus | Many-Body Methods in Quantum Chemistry[END_REF][START_REF] Paldus | [END_REF]85], however, that the SU-CCSD equations may have unphysical solutions, that the physical solutions are hard to converge, and that a solution, which is physical in the degenerate region, may become unphysical in other regions of nuclear geometries. It appears particularly troublesome that, as the homotopy theory calculations show [86], the number unphysical solutions is very large, by far larger than the number of solutions of the FCI equations or even the Bloch equation [87]. This is of course a consequence of the highly nonlinear form of the SU-CC equations. Some of the unphysical solutions may be related to the intruder states causing divergence of the multireference MBPT expansion but the number of the perturbed level crossings responsible for this divergence is smaller than the number of unphysical solutions [86]. This is certainly not a situation conducive to black-box type applications of the SU-CC theory. There is some hope, however, that the inclusion of higher than doubly-excited clusters will help to reduce the number of multiple solutions [60,87,88] and will alleviate problems with converging the SU-CC equations in physically relevant applications.

Clearly, the problems discussed above will get even more severe when the model space is larger, which will necessarily happen when the number of active orbitals is larger than two and the completeness of the model space is required. It is, thus, desired to relax the completeness requirement. Equation ( 13) is valid for incomplete, general model spaces (GMS) but, unfortunately, the connectedness proof given in Ref. 58 cannot be carried out in this case. In fact, one can show [58] that if the intermediate normalization is assumed (P U = U ) in the GMS case, then the perturbation expansion of the effective Hamiltonian does contain some disconnected contribution, also in the case of a fully degenerate model space (in contradiction to the conjecture [89]

based on diagrammatic arguments).

There are two ways to overcome this difficulty. One is to abandon the intermediate normalization and use the resulting freedom to eliminate disconnected terms. This solution was chosen by Meissner, Kucharski and Bartlett [64,90,91] and employed in practice by Balková et al [67]. Another approach was taken by Li and Paldus [92][93][94][95][96][97]. These authors maintain the intermediate normalization but show, both analytically and numerically [93,94], that with a proper choice of the GMS one can obtain size-consistent (correctly dissociating) solutions of SU-CC equations. To achieve that one has to correctly handle the internal excitations (into the model space M 0 ), which have to be included in the cluster operators to guarantee the convergence of the method to the FCI limit. Specifically, in the case of an GMS the cluster operators T µ in Eq. ( 13) have to be replaced by the operators [58] where W µ excites into M 0 , S µ excites into states from M ⊥ 0 belonging also to the smallest complete model space M c containing M 0 , and T µ excites into determinants from M ⊥ c . Similarly as before, T µ does not contain excitations labeled by active orbitals only. The intermediate normalization P U = P implies that

X µ = W µ + S µ + T µ , (20)
P e X µ Φ µ = Φ µ , (21)
and, consequently,

Φ ν | e W µ +S µ Φ µ = 0 ( 22
)
for ν = µ. After expanding the exponential and inspecting the lowest-order terms, one finds [58] that W µ 1 = 0 and

Φ ν | W µ 2 Φ µ = - 1 2 Φ ν | S µ 1 S µ 1 Φ µ (23) Φ ν | W µ 3 Φ µ = -Φ ν | S µ 1 S µ 2 + S µ 1 W µ 2 + 1 6 S µ 1 S µ 1 S µ 1 Φ µ . (24)
These are the so-called C-conditions derived independently and presented in a different form by Li and Paldus [92]. These conditions show that the amplitudes of internal excitations (contained in W µ ) can be completely expressed via amplitudes of external excitations contained in the S µ operator. It is difficult to say now which approach to incomplete model spaces is better but it appears that the intermediately normalized approach of Li and Paldus is more developed at the moment, e.g., triple excitations can be included [97,98] in a noniterative way. It enables one to handle relatively large model spaces and yields excellent results in practical applications [96,99], also for excited states [100,101].

IV. STATE-SELECTIVE THEORIES

Since in majority of applications one is interested in a single quantum state, it is tempting to neglect other, possibly quasidegenerate states, and to concentrate on the chosen one, using the Ansatz of Eq. ( 12). One then immediately faces the difficulty that the number of free parameters in Eq. ( 12) is much larger than the number of FCI coefficients for a single state (even if we limit ourselves to, say, the CCSD approximation, the number of independent equations is smaller than the number of unknown amplitudes). Three solution of this problem, known as state-selective MRCC theories, have been developed thus far. These are the so-called Brillouin-Wigner (BW) [START_REF] Hubač | New Methods in Quantum Theory[END_REF][START_REF] Mášik | [END_REF][104][105][106] and Mukherjee (Mk) [107][108][109][110][111] and the Hanrath method [112,113]. In this section I shall briefly present the main features of these state-specific theories.

A. Brillouin-Wigner CC theory

The Brillouin-Wigner method is computationally simplest and is the most developed for chemical applications, see. e.g., Ref. 114-117. The original derivation was based on the wave operator theory [START_REF] Hubač | New Methods in Quantum Theory[END_REF][START_REF] Mášik | [END_REF][104]. However, the working BW-CC equation can be very easily derived by simple manipulations directly from Eq. ( 12). Assuming that the wave function Ψ of Eq. ( 12) is exact and satisfies the Schrödinger equation (H -E)Ψ = 0, we can write

M µ=1 c µ (H -E) e T µ Φ µ = 0, ( 25
)
where E is the exact energy. Projecting Eq. ( 25) against model functions Φ ν shows that, if the operators T µ are known, the energy can be obtained by diagonalizing the effective Hamiltonian matrix

H eff νµ = Φ ν | He T µ Φ µ . (26)
This form of H eff νµ , valid also for incomplete model spaces, becomes equivalent to Eq. ( 17) when the model space is complete. If we now project Eq. ( 25) on the excited space M ⊥ 0 with the operator Q = 1 -P , and employ the sufficiency condition [START_REF] Paldus | Recent Progress in Coupled-Cluster Methods: Theory and Applications[END_REF]109], we find that

Q (H -E) e T µ Φ µ = 0. ( 27
)
In other words, the fulfillment of Eq. ( 27), with E being an eigenvalue of the matrix (26), guarantees that Ψ of Eq. ( 12) satisfies the Schrödinger equation (25). It should be stressed that the sufficiency condition cannot be applied directly to Eq. ( 25 somewhat similar to the Kucharski-Bartlett form of the SU-CC equations. The l.h.s. of this equation contains connected and disconnected (but linked) terms. Now these disconnected terms do not cancel against the disconnected ones on the r.h.s. and, consequently, the BW-CC method is not size-consistent. One can also premultiply Eq. ( 27) with exp(-T µ ) and, after some manipulation (involving the substitution of Q with 1 -P ), obtain an apparently more connected form of the BW-CC equation

δT µ Φ µ | (H -H eff µµ ) e T µ Φ µ = (E -H eff µµ ) δT µ Φ µ | e T µ Φ µ , (28)
δT µ Φ µ | e -T µ H e T µ Φ µ = M ν=1 (H eff νµ -E δ µν ) δT µ Φ µ | e -T µ Φ ν . (29)
The l.h.s. is now fully connected but the r.h.s. is disconnected, as it must be since for complete model spaces Eq. ( 29) is equivalent to Eq. ( 28). Approximate a posteriori sizeconsistency corrections to the BW-CC energies have been developed [105,106,118]. Some of these corrections [105] have turned out to give good results in practical applications [114][115][116][117]. The good accuracy achieved in recent applications of the BW-CC method was possible also due to the development of codes accounting for triple excitations [119][120][121]. Analytic gradients for the BW-CC method have also been developed [122].

B. Mukherjee's MkCC theory

Formally more satisfactory but computationally more demanding SS-MRCC theory was proposed by Mukherjee and collaborators [107][108][109][110][111]. The wave function in this method is also given by the MRCC Ansatz of Eq. ( 12) and the energy is obtained by diagonalizing the matrix (26). Also the derivation of equations for the cluster operators is based on Eq. ( 25) and on the sufficiency conditions but before these conditions are applied, one inserts the following resolution of identity in front of the µth term in Eq. ( 25)

1 = e T µ P e -T µ + e T µ Q e -T µ . (30)
After expanding P as the sum of one-dimensional projectors

| Φ ν Φ ν |, one obtains M µ=1 c µ e T µ Q e -T µ (H -E) e T µ Φ µ + M µ=1 M ν=1 c µ (H eff νµ -E δ µν ) e T µ Φ ν = 0, (31)
where H eff νµ is now given by Eq. ( 17), i.e., is in the explicitly connected form, even for incomplete model spaces. To apply the sufficiency conditions to Eq. ( 31

c µ e T µ Q e -T µ (H -E) e T µ Φ µ + M ν=1 c ν (H eff µν -E δ µν ) e T ν Φ µ = 0. (32)
Premultiplication with exp(-T µ ) and projections against excited states δT µ Φ µ leads to the conventional from of the amplitude equation in the Mukherjee's theory:

c µ δT µ Φ µ | e -T µ H e T µ Φ µ + M ν =µ c ν H eff µν δT µ Φ µ | e -T µ e T ν Φ µ = 0. (33)
Equation ( 33) bears some similarity to the SU-CC equation ( 16) but there are essential formal differences. Firstly, Eq. ( 33) involves the combining coefficients c µ for the state of interest, so that the process of solving it is not independent of the stage of diagonalization the effective Hamiltonian, which must be done in each iteration. Secondly, the structure of the coupling term is significantly simpler [123] because the bra and ket vectors are expressed with respect of the same vacuum. Mukherjee et al proved [107][108][109] that their method is size-extensive and size-consistent, when localized active orbitals are used. It is also resistant to intruder states as long as the target energy E is well separated from the energies of states evolving from M ⊥ 0 . A number of applications of Mukherjee's theory have been already reported in the literature [99,[123][124][125][126][127][128][129][130][131], most of them carried out by Evangelista and collaborators [123,125,126,128,131], who introduced the abbreviation MkCC for this version of the MRCC theory. These applications, accounting also for triple excitations, showed that the MkCC method performs very well and usually gives better results than the SU-CC and BW-CC approaches. On should add that also the analytical gradient of the MkCC energies was also developed [129]. Very recently a study of the MkCC method, based on a new string-based [132,133] implementation, has been presented [134]. This very informative study discusses also convergence problems which hamper the transformation of the MkCC method into an efficient black-box procedure.

One should also mention that a linked (not explicitly connected) formulation of the MkCC method is possible and has been recently presented [135]. In this formulation Eq. ( 32) is not premultiplied with e -T µ but is directly projected against δT µ Φ µ . The resulting "linked" form of the MkCC equation [START_REF] Paldus | Recent Progress in Coupled-Cluster Methods: Theory and Applications[END_REF]135], is equivalent to Eq. ( 33) if the model space is complete. In such a case we can use Eq. ( 18) to substitute 1-| Φ µ Φ µ | for Q in Eq. ( 32) and obtain the first term in Eq. ( 34).

c µ δT µ Φ µ | (H -H eff µµ ) e T µ Φ µ + M ν=1 c ν H eff µν δT µ Φ µ | e T ν Φ µ = 0, (34)
This term is identical with the l.h.s. of the Kucharski-Bartlett form of the BW-CC equation (28). The advantage of using Eq. ( 34) stems from the fact that the coupling term involves a single exponential and is easier to code. By employing Eq. ( 34), the MkCC codes can be obtained by a modification of the BW-CC codes.

C. Hanrath's MRexpT theory

A very original solution to the problem of the redundant amplitudes in a state-specific application of Ansatz [START_REF] Harris | [END_REF] has been proposed by Hanrath [112,113]. Generally speaking the idea of the Hanrath method, referred to by him as the MRexpT method, is to parametrize all T µ operators with a single set of amplitudes, uniquely assigned to excited determinants rather than to excitation operators. Let us consider, for example, the case of single and double excitations out of the model space M 0 . The linear span of all determinants from M ⊥ 0 , which can be obtained by replacing a single spinorbital in one of Φ µ functions, will be denoted by M 1 . The subspace of double excitations M 2 is defined similarly as the subspace of M ⊥ 0 M 1 spanned by the determinants that can be obtained by double substitutions from determinants in M 0 . The orthogonal sum M 1 ⊕ M 2 is just the MRCISD excitation space.

Hanrath employs Eq. ( 12) for the wave function and assumes that the cluster operators have the form

T µ = e -i arg(cµ) I µ t I Ĝµ I , (35)
where the superscript µ at the summation sign indicates that the sum runs over those determinants Φ I from M 1 ⊕ M 2 which are singly or doubly excited relative to Φ µ . For each I and µ, the excitation operator Ĝµ I is uniquely defined by

Φ I = Ĝµ I Φ µ . (36)
Thus, each T µ is a sum of all single and double excitation operators but the single set of amplitudes t I is used to parametrize all T µ 's. The phase factor e -i arg(cµ) in Eq. ( 35) was introduced to guarantee the potential completeness of the proposed wave-function Ansatz [112,113]. The total number of coefficients c µ and the amplitudes t I is the same as the number of MRCI coefficients, so the redundancy problem is resolved.

c µ Φ I | (H -E) e T µ Φ µ = 0, (37)
where Φ I are determinants spanning M 1 ⊕M 2 . Hanrath has shown that the energy obtained by solving these equations is size consistent [112] and core but not "valence" [136,137] extensive. Hanrath argues [138] that the set of active, i.e. "valence" orbitals is typically not large, so this limitation should not be too restrictive. Several applications of the Hanrath method, performed thus far small model systems [112,[139][140][141][142], indicate that the MRexpT method has a potential to be very accurate. A theoretical rationalization of a more satisfactory performance of this method, as compared to other state-selective MRCC approaches, has been given recently by Kong [143]. A drawback of the MRexpT method is that, due to the determinantal indexing, the resulting amplitude equations are extraordinarily complex and cannot be derived and solved using standard techniques developed during the last decades by the coupled cluster community. A new, efficient implementation of the general (arbitrary excitation order) coupled cluster code [144] can be expected to help to circumvent this difficulty.

V. CONCLUDING REMARKS

Despite the enormous progress made in the understanding and implementation of the MRCC Ansatz of Eq. ( 12), none of the proposed methods is close to routine black-box type applications. Such applications would require, e.g., an availability of analytical gradients and very little has been done in this area, both in the state-universal [122,[145][146][147][148] and state-specific [122,129] subfields.

There are two major sources of difficulties which still need to be seriously addressed. The first one is the excessively large number of amplitudes, especially when the full extensivity of the theory is required, and the second, is the difficulty in converging the MRCC equations, resulting from their highly nonlinear structure. The MRexpT method of Hanrath [112,[139][140][141][142] and the C-conditions method of Li and Paldus [92][93][94][95][96][97] seem to offer a promising solution of the first problem. On should also point out that the incomplete model spaces and the C-conditions can also be used in the state-selective framework -in the BW-CC [119] and MkCC [149,150] approaches. Another possibility was chosen by Kowalski and Piecuch [60,151], who approximated the core-virtual bi-excited amplitudes by perturbation theory and obtained very good results with a greatly reduced number of variables in the nonlinear CC equations. In fact, this core-virtual bi-excited amplitudes are, through the first order of perturbation theory, independent of µ and one may contemplate to determine them nonperturbatively from MRCC equation assuming that they are the same for all µ's through all orders [START_REF] Das | Recent Progress in Coupled-Cluster Methods: Theory and Applications[END_REF]. One should also mention that the number of amplitudes per considered quantum state is usually much smaller in the SU-CC applications, as compared to the applications of the SS-MRCC theories. From this perspective, the results of applying the SU-CC Ansatz in such a way that each T µ includes excitation to all determinants from the MRCISD space M 1 ⊕ M 2 would be very informative.

The difficulties to converge the solutions of MRCC equations may be overcome by using better convergence acceleration or equation regularization techniques [134], or by including higher excitations in T µ , which should reduce the number of unphysical solutions [60,86] hampering convergence to the physical ones. A promising way of solving these convergence difficulty, successfully applied in the context of the Fock space CC theory [42], is to use the intermediate-Hamiltonian approach to reformulate the SU-CC equations [START_REF] Eliav | [END_REF].

Another difficulty of the MRCC approaches relying on the Ansatz [START_REF] Harris | [END_REF], is the lack of invariance to rotations of active orbitals [134,154,155] (this Ansatz and the resulting SU-CC, BW-CC, MkCC, and MRexpT approaches are, however, fully invariant to separate rotations of core and virtual orbitals). This lack of invariance is less severe if the M 1 ⊕ M 2 space is chosen as the range of all T µ operators [131], but it is to be determined how significant this lack of invariance is in practice (probably is not very significant in applications of the general model space method of Li and Paldus [92][93][94][95][96][97]).

One should also mention that is it possible to improve the results of SU-CCSD calculations by approximately accounting for higher than double excitations. This has been done using appropriate generalization [156,157] of the method of moments [START_REF] Piecuch | Computational Chemistry: Reviews of current Trends[END_REF] or by merging the SU-CC method [START_REF] Li | [END_REF] with the reduced multireference (RMR) coupled cluster approach of Li and Paldus [160,161].

In conclusion, during the last decade we have witnessed a remarkable progress in the development of MRCC methods relying on the Ansatz [START_REF] Harris | [END_REF]

T

  A and T B of the fragments: lim R→∞ T = T A + T B .

8 )R→∞Ψ( 1 ,

 81 and use Eq. (6), then we can write lim R→∞ Ψ(1, . . . , N ) = A e T A (1,...,N A )+T B (N A +1,...,N ) Φ A (1, . . . , N A ) Φ B (N A + 1, . . . , N ). (Since the orbitals used to define T A and Φ B are mutually orthogonal we can replace T A (1, . . . , N A ) in Eq. (8) by T A (1, . . . , N ), where T A (1, . . . , N ) is the natural extension of T A (1, . . . , N A ) to the whole N -electron Hilbert space, defined by second quantization, or by equations of the form of Eq. (3). Extending T B (N A + 1, . . . , N ) in a similar way one can write lim . .

  ) (before projection with Q), because the resulting equation would not have a solution if the intermediate normalization Φ ν | e T µ Φ µ = δ νµ is enforced or would be trivially equivalent to the Schrödinger equation otherwise. Equation (27) is just the basic equation of the BW-CC theory. Further projection with the set of individual excited determinants brings this equation to the more familiar form,

  summation order in the second term and relabeled the summation indexes µ ↔ ν. The resulting equations, sufficient for the fulfillment of Eq. (25), are

  approaches and contains very competent presentation of theoretical developments until 2001, as well as an extensive, almost complete presentation of applications published until the same time. The very recent review by Paldus, Pittner and Čársky [61] has a broader scope. It can be recommended especially for the extensive and insightful discussion of state-selective MRCC approaches, sometimes only indirectly related to Eq. (

	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

information. The 2002 review by Piecuch and Kowalski

[60]

is devoted to state-universal

  The c µ coefficients and the energy are obtained by diagonalizing the effective Hamiltonian (17) and the t I coefficients by solving the MRexpT equations of the form

	M
	µ=1
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

  . It is very impressive how much ingenuity and insight has been invested in this development. Although a black-box MRCC method is not in sight, I believe that these developments have brought us much closer to the situation when the MRCC methods will be routinely used in the hands of competent theoretical chemists to solve well defined classes of multireference problems of experimental interest.

	F o r F o r F o r F o r F o r F o r F o r
	P P P P P P P
	e e e e e e e
	e r e r e r e r e r e r e r
	R R R R R R R
	e e e e e e e
	v i e v i e v i e v i e v i e v i e v i e
	w w w w w w w
	O n l O n l O n l O n l O n l O n l O n l
	y y y y y y y

Acknowledgments

On this occasion I would like to thank Henk Monkhorst for my five enjoyable visits to QTP and for the pleasure of collaborating with him on several projects throughout the decade of 1980s. I also thank Michael Hanrath, Debashis Mukherjee, Josef Paldus, Piotr Piecuch, and Jiří Pittner for valuable comments on the manuscript.