text:
# A Decomposition Theorem for Maximum Weight Bipartite MatchingsA preliminary version appeared in the Proceedings of the 7th Annual European Symposium on Algorithms, 1999, pp. 439–449.

## 1 Introduction

Let $`G=(X,Y,E)`$ be a bipartite graph with positive integer weights on the edges. A matching of $`G`$ is a subset of node-disjoint edges of $`G`$. Let $`\mathrm{mwm}(G)`$ (respectively, $`\mathrm{mm}(G)`$) denote the maximum weight (respectively, cardinality) of any matching of $`G`$. A maximum weight matching is one whose weight is $`\mathrm{mwm}(G)`$. Let $`N`$ be the largest weight of any edge. Let $`W`$ be the total weight of $`G`$. Let $`n`$ and $`m`$ be the numbers of nodes and edges of $`G`$; to avoid triviality, we maintain $`m=\mathrm{\Omega }(n)`$ throughout the paper.

The problem of finding a maximum weight matching of a given $`G`$ has a rich history. The first known polynomial-time algorithm is the $`O(n^3)`$-time Hungarian method . Fredman and Tarjan  used Fibonacci heaps to improve the time to $`O(n(m+n\mathrm{log}n))`$. Gabow  introduced scaling to solve the problem in $`O(n^{3/4}m\mathrm{log}N)`$ time by taking advantage of the integrality of edge weights. Gabow and Tarjan  improved the scaling method to further reduce the time to $`O(\sqrt{n}m\mathrm{log}(nN))`$. For the case where the edges all have weight 1, i.e., $`N=1`$ (and $`W=m`$), Hopcroft and Karp  gave an $`O(\sqrt{n}W)`$-time algorithm, and Feder and Motwani  improved the time complexity to $`O(\sqrt{n}W/k(n,m))`$, where $`k(x,y)=\mathrm{log}x/\mathrm{log}(x^2/y)`$. It has remained open whether the gap between the running times of the Gabow-Tarjan algorithm and the latter two algorithms can be closed for the case where $`W=o(m\mathrm{log}(nN))`$.

We resolve this open problem in the affirmative by giving an $`O(\sqrt{n}W/k(n,W/N))`$-time algorithm for general $`W`$. Note that $`W/N=m`$ when all the edges have the same weight. The algorithm does not use scaling but instead employs a novel decomposition theorem for weighted bipartite matchings (Theorem 2). We also use the theorem to solve the all-cavity maximum weight matching problem which, given $`G`$ and a maximum weight matching of $`G`$, asks for $`\mathrm{mwm}(G\{u\})`$ for all nodes $`u`$ in $`G`$. This problem has applications to tree comparisons . The case where $`N=1`$ has been studied by Chung . Recently, Kao, Lam, Sung, and Ting  gave an $`O(\sqrt{n}m\mathrm{log}N)`$-time algorithm for general $`N`$. This paper presents a new algorithm that runs in $`O(W)`$ time.

Section 2 presents the decomposition theorem and uses it to compute the weight of a maximum weight matching. Section 3 gives an algorithm to construct a maximum weight matching. Section 4 solves the all-cavity matching problem.

## 2 The decomposition theorem

In §2.1, we state the decomposition theorem and use the theorem to design an algorithm to compute the weight $`\mathrm{mwm}(G)`$ in $`O(\sqrt{n}W/k(n,W/N))`$ time. In §2.2, we prove the decomposition theorem. In §3, we further construct a maximum weight matching itself within the same time bound.

### 2.1 An algorithm for computing mwm($`𝑮`$)

Let $`V(G)`$ be the node set of $`G`$, i.e., $`XY`$. Let $`w(u,v)`$ denote the weight of an edge $`uvG`$; if $`u`$ is not adjacent to $`v`$, let $`w(u,v)=0`$. A cover of $`G`$ is a function $`C:XY\{0,1,2,\mathrm{}\}`$ such that $`C(x)+C(y)w(x,y)`$ for all $`xX`$ and $`yY`$. Let $`w(C)=_{zXY}C(z)`$ be the weight of $`C`$. $`C`$ is a minimum weight cover if $`w(C)`$ is the smallest possible. Let $`\mathrm{mwc}(G)`$ denote the weight of a minimum weight cover of $`G`$. A minimum weight cover is a dual of a maximum weight matching as stated in the next fact.

###### Fact 1 (see ).

Let $`C`$ be a cover and $`M`$ be a matching of $`G`$. The following statements are equivalent.

1. $`C`$ is a minimum weight cover and $`M`$ is a maximum weight matching of $`G`$.
2. $`_{uvM}w(u,v)=_{uXY}C(u)`$.
3. Every node in $`\{uC(u)>0\}`$ is matched by some edge in $`M`$, and $`C(u)+C(v)=w(u,v)`$ for all $`uvM`$.

For an integer $`h[1,N]`$, we divide $`G`$ into two lighter bipartite graphs $`G_h`$ and $`G_h^\mathrm{\Delta }`$ as follows:

* $`G_h`$ is formed by the edges $`uv`$ of $`G`$ with $`w(u,v)[Nh+1,N]`$. Each edge $`uv`$ in $`G_h`$ has weight $`w(u,v)(Nh)`$. For example, $`G_1`$ is formed by the heaviest edges of $`G`$, and the weight of each edge is exactly one.
* Let $`C_h`$ be a minimum weight cover of $`G_h`$. $`G_h^\mathrm{\Delta }`$ is formed by the edges $`uv`$ of $`G`$ with $`w(u,v)C_h(u)C_h(v)>0`$. The weight of $`uv`$ is $`w(u,v)C_h(u)C_h(v)`$.

An example is depicted in Figure 1. Note that the total weight of $`G_h`$ and $`G_h^\mathrm{\Delta }`$ is at most $`W`$.

The next theorem is the decomposition theorem.

###### Theorem 2.

$`\mathrm{mwm}(G)=\mathrm{mwm}(G_h)+\mathrm{mwm}(G_h^\mathrm{\Delta })`$; in particular, $`\mathrm{mwm}(G)=\mathrm{mm}(G_1)+\mathrm{mwm}(G_1^\mathrm{\Delta })`$.

###### Proof.

See §2.2. ∎

Theorem 2 suggests the following recursive algorithm to compute $`\mathrm{mwm}(G)`$.

Procedure Compute-MWM$`(G)`$

1. Construct $`G_1`$ from $`G`$.
2. Compute $`\mathrm{mm}(G_1)`$ and find a minimum weight cover $`C_1`$ of $`G_1`$.
3. Construct $`G_1^\mathrm{\Delta }`$ from $`G`$ and $`C_1`$.
4. If $`G_1^\mathrm{\Delta }`$ is empty, then return $`\mathrm{mm}(G_1)`$; otherwise, return $`\mathrm{mm}(G_1)+`$Compute-MWM$`(G_1^\mathrm{\Delta })`$.

###### Theorem 3.

Compute-MWM$`(G)`$ finds $`\mathrm{mwm}(G)`$ in $`O(\sqrt{n}W/k(n,W/N))`$ time.

###### Proof.

The correctness of Compute-MWM follows from Theorem 2. Below, we analyze the running time. We initialize a maximum heap  in $`O(m)`$ time to store the edges of $`G`$ according to their weights. Let $`T(n,W,N)`$ be the running time of Compute-MWM excluding this initialization. Let $`L`$ be the set of the heaviest edges in $`G`$. Then Step 1 takes $`O(|L|\mathrm{log}m)`$ time. In Step 2, we can compute $`\mathrm{mm}(G_1)`$ in $`O(\sqrt{n}|L|/k(n,|L|))`$ time . From this matching, $`C_1`$ can be found in $`O(|L|)`$ time . Let $`L_1`$ be the set of the edges of $`G`$ adjacent to some node $`u`$ with $`C_1(u)>0`$; i.e., $`L_1`$ consists of the edges of $`G`$ whose weights are reduced in $`G_1^\mathrm{\Delta }`$. Let $`\mathrm{}_1=|L_1|`$. Step 3 updates every edge of $`L_1`$ in the heap in $`O(\mathrm{}_1\mathrm{log}m)`$ time. As $`LL_1`$, Steps 1 to 3 altogether use $`O(\sqrt{n}\mathrm{}_1/k(n,\mathrm{}_1))`$ time. Since the total weight of $`G_1^\mathrm{\Delta }`$ is at most $`W\mathrm{}_1`$, Step 4 uses at most $`T(n,W\mathrm{}_1,N^{})`$ time, where $`N^{}<N`$ is the maximum edge weight of $`G_1^\mathrm{\Delta }`$. In summary, for some positive integer $`\mathrm{}_1W`$,

$$T(n,W,N)=O(\sqrt{n}\mathrm{}_1/k(n,\mathrm{}_1))+T(n,W\mathrm{}_1,N^{}),$$

where $`T(n,0,N^{})=0`$. By recursion, for some positive integers $`\mathrm{}_1,\mathrm{}_2,\mathrm{},\mathrm{}_p`$ with $`pN`$ and $`_{1ip}\mathrm{}_i=W`$,

$`T(n,W,N)`$ $`=`$ $`O\left(\sqrt{n}\left({\displaystyle \frac{\mathrm{}_1}{k(n,\mathrm{}_1)}}+{\displaystyle \frac{\mathrm{}_2}{k(n,\mathrm{}_2)}}+\mathrm{}+{\displaystyle \frac{\mathrm{}_p}{k(n,\mathrm{}_p)}}\right)\right)`$
$`=`$ $`O\left({\displaystyle \frac{\sqrt{n}}{\mathrm{log}n}}\left(\left({\displaystyle \underset{1ip}{}}\mathrm{}_i\right)\mathrm{log}n^2{\displaystyle \underset{1ip}{}}\mathrm{}_i\mathrm{log}\mathrm{}_i\right)\right).`$
Since $`x\mathrm{log}x`$ is convex, by Jensen’s Inequality ,

$$\underset{1ip}{}\mathrm{}_i\mathrm{log}\mathrm{}_i\left(\underset{1ip}{}\mathrm{}_i\right)\mathrm{log}\frac{_{1ip}\mathrm{}_i}{p}W\mathrm{log}\frac{W}{N}.$$

Therefore,

$`T(n,W,N)`$ $`=`$ $`O\left({\displaystyle \frac{\sqrt{n}}{\mathrm{log}n}}\left(W\mathrm{log}n^2W\mathrm{log}{\displaystyle \frac{W}{N}}\right)\right)`$
$`=`$ $`O\left({\displaystyle \frac{\sqrt{n}W}{\mathrm{log}n/\mathrm{log}(n^2/\frac{W}{N})}}\right)=O\left(\sqrt{n}W/k(n,W/N)\right).`$
### 2.2 Proof of Theorem 2

This section proves the statement that $`\mathrm{mwm}(G)=\mathrm{mwm}(G_h)+\mathrm{mwm}(G_h^\mathrm{\Delta })`$, where $`G_h^\mathrm{\Delta }`$ is defined according to an arbitrary minimum weight cover $`C_h`$ of $`G_h`$. By Fact 1, it suffices to prove $`\mathrm{mwc}(G)=w(C_h)+\mathrm{mwc}(G_h^\mathrm{\Delta })`$.

To show the direction $`\mathrm{mwc}(G)w(C_h)+\mathrm{mwc}(G_h^\mathrm{\Delta })`$, note that any cover $`D`$ of $`G_h^\mathrm{\Delta }`$ augmented with $`C_h`$ gives a cover $`C`$ of $`G`$, where $`C(u)=C_h(u)+D(u)`$ for each node $`u`$ of $`G`$. Then $`C(u)+C(v)w(u,v)`$ for all edges $`uv`$ of $`G`$. Thus, $`\mathrm{mwc}(G)w(C_h)+\mathrm{mwc}(G_h^\mathrm{\Delta })`$.

To show the direction $`w(C_h)+\mathrm{mwc}(G_h^\mathrm{\Delta })\mathrm{mwc}(C)`$, let $`C`$ be a minimum weight cover of $`G`$. A node $`u`$ of $`G`$ is called bad if $`C(u)<C_h(u)`$. Lemma 4 below shows that $`G`$ must have a minimum weight cover $`C`$ allowing no bad node. Then we can construct a cover $`D`$ of $`G_h^\mathrm{\Delta }`$ as follows. For each node $`u`$ of $`G`$, define $`D(u)=C(u)C_h(u)`$, which must be at least $`0`$. $`D`$ is a cover of $`G_h^\mathrm{\Delta }`$ because for any edge $`uv`$ of $`G_h^\mathrm{\Delta }`$, $`D(u)+D(v)=C(u)+C(v)C_h(u)C_h(v)w(u,v)C_h(u)C_h(v)`$. Note that $`w(D)=w(C)w(C_h)`$. Thus, $`\mathrm{mwc}(G_h^\mathrm{\Delta })w(C)w(C_h)`$, or equivalently, $`\mathrm{mwc}(G_h^\mathrm{\Delta })+w(C_h)\mathrm{mwc}(G)`$.

The next lemma concludes the proof of Theorem 2.

###### Lemma 4.

There exists a minimum weight cover of $`G`$ such that no node of $`G`$ is bad.

###### Proof.

Suppose, for the sake of contradiction, that every minimum weight cover allows some bad node. Then we can obtain a contradiction by constructing another minimum weight cover with no bad node.

Let $`C`$ be a minimum weight cover of $`G`$ with $`u`$ as a bad node, i.e., $`C(u)<C_h(u)`$. Recall that $`C_h`$ is a minimum weight cover of $`G_h`$. Consider a maximum weight matching $`M`$ of $`G_h`$. By Fact 1, since $`C_h(u)>C(u)0`$, $`u`$ is matched by an edge in $`M`$, say, to a node $`v`$, and $`C_h(u)+C_h(v)=w(u,v)(Nh)`$. We call $`v`$ the mate of $`u`$. Note that $`v`$ cannot be a bad node; otherwise, $`C(u)+C(v)<w(u,v)(Nh)w(u,v)`$ and a contradiction occurs.

Since $`C`$ is a cover of $`G`$, $`C(u)+C(v)w(u,v)`$. Thus, $`C(v)w(u,v)C(u)Nh+C_h(u)+C_h(v)C(u)`$. Define another cover $`C^{}`$ of $`G`$ as follows. For each bad node defined by $`C`$, let $`v`$ be the mate of $`u`$, define $`C^{}(u)=C_h(u)`$ and $`C^{}(v)=C(v)(C_h(u)C(v))`$. Note that $`u`$ is not a bad node with respect to $`C^{}`$, and neither is $`v`$ since $`C^{}(v)Nh+C_h(v)C_h(v)`$. For all other nodes $`x`$, $`C^{}(x)`$ is the same as $`C(x)`$. Therefore, if $`C^{}`$ is a cover of $`G`$, $`C^{}`$ allows no bad node. Also, $`w(C^{})=w(C)`$.

It remains to prove that $`C^{}`$ is a cover of $`G`$. By the definition of $`C^{}`$, $`C^{}(v)<C(v)`$ if and only if $`v`$ is the mate of a bad node with respect to $`C`$. Suppose $`C^{}`$ is not a cover of $`G`$. Then there exists an edge $`vt`$ such that $`C^{}(v)+C^{}(t)w(v,t)`$ and $`v`$ is the mate of a bad node. Recall that the latter implies that $`C^{}(v)Nh+C_h(v)`$. In other words,

$$C^{}(t)<w(v,t)C^{}(v)w(v,t)(Nh)C_h(v).$$

We can derive a contradiction as follows.

Case 1: $`w(v,t)Nh`$. Then $`C^{}(t)<C_h(v)0`$, which contradicts that $`C^{}(t)C_h(t)0`$.

Case 2: $`w(v,t)>Nh`$. Then $`G_h`$ contains the edge $`vt`$ and $`C_h(v)+C_h(t)w(v,t)(Nh)`$. Thus, $`C^{}(t)<w(v,t)(Nh)C_h(v)C_h(t)`$, which contradicts the fact that $`C^{}`$ allows no bad node.

In conclusion, $`C^{}`$ is a cover of $`G`$. Together with the fact that $`w(C)=w(C^{})`$, we obtain the desired contradiction that $`C^{}`$ is a minimum weight cover of $`G`$ with no bad node. Lemma 4 follows. ∎

## 3 Construct a maximum weight matching

The algorithm in §2.1 only computes the value of $`\mathrm{mwm}(G)`$. To report the edges involved, we show below how to first construct a minimum weight cover of $`G`$ in $`O(\sqrt{n}W/k(n,W/N))`$ time and then use this cover to construct a maximum weight matching in $`O(\sqrt{n}m/k(n,m))`$ time. Thus, the time required to construct a maximum weight matching is $`O(\sqrt{n}W/k(n,W/N))`$.

###### Lemma 5.

Assume that $`h,G_h,C_h`$, and $`G_h^\mathrm{\Delta }`$ are defined as in §2. Let $`C_h^\mathrm{\Delta }`$ be any minimum weight cover of $`G_h^\mathrm{\Delta }`$. If $`D`$ is a function on $`V(G)`$ such that for every $`uV(G)`$, $`D(u)=C_h(u)+C_h^\mathrm{\Delta }(u)`$, then $`D`$ is a minimum weight cover of $`G`$.

###### Proof.

Consider any edge $`uv`$ of $`G`$. If $`uv`$ is not in $`G_h^\mathrm{\Delta }`$, then $`w(u,v)C_h(u)+C_h(v)D(u)+D(v)`$. Assume that $`uv`$ is in $`G_h^\mathrm{\Delta }`$. Note that its weight in $`G_h^\mathrm{\Delta }`$ is $`w(u,v)C_h(u)C_h(v)`$. Since $`C_h^\mathrm{\Delta }`$ is a cover, $`C_h^\mathrm{\Delta }(u)+C_h^\mathrm{\Delta }(v)w(u,v)C_h(u)C_h(v)`$. Thus, $`D(u)+D(v)=C_h(u)+C_h^\mathrm{\Delta }(u)+C_h(v)+C_h^\mathrm{\Delta }(v)w(u,v)`$. It follows that $`D`$ is a cover of $`G`$. To show that $`D`$ is a minimum weight one, we observe that

$$\begin{array}{cccc}_{uV(G)}D(u)\hfill & =\hfill & _{uV(G)}C_h(u)+C_h^\mathrm{\Delta }(u)\hfill & \\ & =\hfill & _{uV(G)}C_h(u)+_{uV(G)}C_h^\mathrm{\Delta }(u)\hfill & \\ & =\hfill & \mathrm{mwm}(G_h)+\mathrm{mwm}(G_h^\mathrm{\Delta })\hfill & \text{by Fact }\text{1}\hfill \\ & =\hfill & \mathrm{mwm}(G).\hfill & \text{by Theorem }\text{2}\hfill \end{array}$$

By Fact 1, $`D`$ is minimum. ∎

By Lemma 5, a minimum weight cover of $`G`$ can be computed using a recursive procedure similar to Compute-MWM as follows.

Procedure Compute-Min-Cover$`(G)`$

1. Construct $`G_1`$ from $`G`$.
2. Find a minimum weight cover $`C_1`$ of $`G_1`$.
3. Construct $`G_1^\mathrm{\Delta }`$ from $`G`$ and $`C_1`$.
4. If $`G_1^\mathrm{\Delta }`$ is empty, then return $`C_1`$; otherwise, let $`C_1^\mathrm{\Delta }`$ = Compute-Min-Cover$`(G_1^\mathrm{\Delta })`$ and return $`D`$ where for all nodes $`u`$ in $`G`$, $`D(u)=C_1(u)+C_1^\mathrm{\Delta }(u)`$.

###### Theorem 6.

Compute-Min-Cover$`(G)`$ correctly computes a minimum weight cover of $`G`$ in $`O(\sqrt{n}W/k(n,W/N))`$ time.

###### Proof.

The correctness of Compute-Min-Cover$`(G)`$ follows from Lemma 5. For the time complexity, the analysis is similar to that of Theorem 3. ∎

Now, we show how to recover a maximum weight matching of $`G`$ from a minimum weight cover $`D`$ of $`G`$.

Procedure Recover-Max-Matching$`(G,D)`$

1. Let $`H`$ be the subgraph of $`G`$ that contains all edges $`uv`$ with $`w(u,v)=D(u)+D(v)`$.
2. Make two copies of $`H`$. Call them $`H^a`$ and $`H^b`$. For each node $`u`$ of $`H`$, let $`u^a`$ and $`u^b`$ denote the corresponding nodes in $`H^a`$ and $`H^b`$, respectively.
3. Union $`H^a`$ and $`H^b`$ to form $`H^{ab}`$, and add to $`H^{ab}`$ the set of edges $`\{u^au^buV(H),D(u)=0\}`$.
4. Find a maximum cardinality matching $`K`$ of $`H^{ab}`$ and return the matching $`K^a=\{uvu^av^aK\}`$.

###### Theorem 7.

Recover-Max-Matching$`(G,D)`$ correctly computes a maximum weight matching of $`G`$ in $`O(\sqrt{n}m/k(n,m))`$ time.

###### Proof.

The running time of Recover-Max-Matching$`(G,D)`$ is dominated by the construction of $`K`$. Since $`H^{ab}`$ has at most $`2n`$ nodes and at most $`3m`$ edges, $`K`$ can be constructed in $`O(\sqrt{n}m/k(n,m))`$ time using Feder-Motwani algorithm .

It remains to show that $`K^a`$ is a maximum weight matching of $`G`$. First, we argue that $`H^{ab}`$ has a perfect matching. Let $`M`$ be a maximum weight matching of $`G`$. By Fact 1, $`D(u)+D(v)=w(u,v)`$ for every edge $`uvM`$. Therefore, $`M`$ is also a matching of $`H`$. Let $`U`$ be the set of nodes in $`H`$ unmatched by $`M`$. By Fact 1, $`D(u)=0`$ for all $`uU`$. Let $`Q`$ be $`\{u^au^buU\}`$. Let $`M^a=\{u^av^auvM\}`$ and $`M^b=\{u^bv^buvM\}`$. Note that $`QM^aM^b`$ forms a matching in $`H^{ab}`$ and every node in $`H^{ab}`$ is matched by either $`Q`$, $`M^a`$ or $`M^b`$. Thus, $`H^{ab}`$ has a perfect matching.

Since $`K`$ is a maximum cardinality matching of $`H^{ab}`$, $`K`$ must be a perfect matching. For every node $`u`$ with $`D(u)>0`$, $`u^a`$ must be matched by $`K`$. Since there is no edge between $`u^a`$ and any $`x^b`$ in $`H^{ab}`$, there exists some $`v^a`$ with $`u^av^aK`$. Thus, every node $`u`$ with $`D(u)>0`$ must be matched by some edge in $`K^a`$. Therefore, $`_{uvK^a}w(u,v)=_{uXY,D(u)>0}D(u)=_{uXY}D(u)=\mathrm{mwm}(G)`$, and $`K^a`$ is a maximum weight matching of $`G`$. ∎

## 4 All-cavity maximum weight matchings

In §4.1, we introduce the notion of an unfolded graph. In §4.2, we use this notion to design an algorithm which, given a weighted bipartite graph $`G`$ and a maximum weight matching of $`G`$, computes $`\mathrm{mwm}(G\{u\})`$ for all nodes $`u`$ in $`G`$ using $`O(W)`$ time.

### 4.1 Unfolded graphs

The unfolded graph $`\varphi (G)`$ of $`G`$ is defined as follows.

* For each node $`u`$ of $`G`$, $`\varphi (G)`$ has $`\alpha `$ copies of $`u`$, denoted as $`u^1,u^2,\mathrm{},u^\alpha `$, where $`\alpha `$ is the weight of the heaviest edge incident to $`u`$.
* For each edge $`uv`$ of $`G`$, $`\varphi (G)`$ has the edges $`u^1v^\beta ,u^2v^{\beta 1},\mathrm{},u^\beta v^1`$, where $`\beta =w(u,v)`$.

See Figure 2(a) for an example. Let $`M`$ be a matching of $`G`$. Consider $`M`$ as a weighted bipartite graph; then, by definition, $`\varphi (M)=_{uvM}\{u^1v^\beta ,\mathrm{},u^\beta v^1\beta =w(u,v)\}`$ is a matching of $`\varphi (G)`$. The number of edges in $`\varphi (M)`$ is equal to the total weight of the edges in $`M`$, i.e., $`|\varphi (M)|=_{uvM}w(u,v)`$. The next lemma relates $`G`$ and $`\varphi (G)`$.

###### Lemma 8.

Assume that $`M`$ is a maximum weight matching of $`G`$.

1. $`\mathrm{mwm}(G)=\mathrm{mm}(\varphi (G))`$.
2. The set $`\varphi (M)`$ is a maximum cardinality matching of $`\varphi (G)`$.

###### Proof.

Statement 2 follows from Statement 1. Statement 1 is proved as follows. Since $`M`$ is a maximum weight matching of $`G`$, $`\mathrm{mwm}(G)=_{uvM}w(u,v)=|\varphi (M)|\mathrm{mm}(\varphi (G))`$. By Fact 1, $`\mathrm{mwm}(G)\mathrm{mm}(\varphi (G))`$ if and only if $`\mathrm{mwc}(G)\mathrm{mwc}(\varphi (G))`$. We prove the latter as follows. Given a minimum weight cover $`C`$ of $`G`$, we can obtain a cover $`C^{}`$ of $`\varphi (G)`$ as follows. For any node $`u`$ of $`G`$, $`C^{}(u^i)=1`$ if $`C(u)>0`$ and $`iC(u)`$; otherwise, $`C^{}(u^i)=0`$. Note that $`w(C^{})=w(C)=\mathrm{mwc}(G)`$. Therefore, $`\mathrm{mwc}(G)\mathrm{mwc}(\varphi (G))`$ and $`\mathrm{mwm}(G)\mathrm{mm}(\varphi (G))`$. ∎

### 4.2 An algorithm for all-cavity maximum weight matchings

Let $`M`$ be a given maximum weight matching of $`G`$.

By Lemma 8(2), $`\varphi (M)`$ is a maximum cardinality matching of $`\varphi (G)`$. In light of this maximality, we say that a path in $`\varphi (G)`$ is alternating for $`\varphi (M)`$ if (1) its edges alternate between being in $`\varphi (M)`$ and being not in $`\varphi (M)`$ and (2) in the case the first (respectively, last) node is matched by $`\varphi (M)`$, the path contains the matched edge of $`u`$ as the first (respectively, last) edge. The length of an alternating path is its number of edges. An alternating path may have zero length; in this case, the path contains exactly one unmatched node. An alternating path $`P`$ can modify $`\varphi (M)`$ to another matching, i.e., $`(\varphi (M)P)(\varphi (M)P)`$. If $`P`$ is of even length, the resulting matching has the same size as $`\varphi (M)`$. If $`P`$ is of odd length, $`P`$ modifies $`M`$ to a strictly smaller or bigger matching; yet the latter is impossible because $`\varphi (M)`$ is maximum. Intuitively, we would like to maximize the size of the resultant matching and even-length alternating paths are preferred.

Our new algorithm for computing $`\mathrm{mwm}(G\{u\})`$ is based on the observation that $`\mathrm{mwm}(G\{u\})`$ can be determined by detecting the smallest $`i`$ such that $`u^i`$ has an even-length alternating path for $`\varphi (M)`$. Details are as follows.

Definition. For each $`u^i`$ in $`\varphi (G)`$, let $`\rho (u^i)=0`$ if there is an even-length alternating path for $`\varphi (M)`$ starting from $`u^i`$; otherwise, let $`\rho (u^i)=1`$.

The following lemma states a monotone property of $`\rho (u^i)`$ over different $`i`$’s.

###### Lemma 9.

Consider any node $`u`$ in $`G`$. Let $`u^1,u^2,\mathrm{},u^\beta `$ be its corresponding nodes in $`\varphi (G)`$. If $`\rho (u^i)=0`$, then $`\rho (u^j)=0`$ for all $`j[i,\beta ]`$. Furthermore, there exist $`\beta i+1`$ node-disjoint even-length alternating paths $`P_i,P_{i+1},\mathrm{}P_\beta `$ for $`\varphi (M)`$, where each $`P_j`$ starts from $`u^j`$.

###### Proof.

As $`\rho (u^i)=0`$, let $`P_i=u_0^{a_0},v_0^{b_0},`$ $`u_1^{a_1},v_1^{b_1},\mathrm{},u_{p1}^{a_{p1}},v_{p1}^{b_{p1}},u_p^{a_p}`$ be a shortest even-length alternating path for $`\varphi (M)`$ where $`u_0^{a_0}=u^i`$.

Based on $`P_i`$, we can construct an even-length alternating path $`P_{i+1}`$ for $`\varphi (M)`$ starting from $`u^{i+1}`$ as follows. If $`u^{i+1}`$ is not matched by $`\varphi (M)`$, $`P_{i+1}`$ is simply a path of zero length. From now on, we assume that $`u^{i+1}`$ is matched by $`\varphi (M)`$. As $`P`$ is of even length, $`u_p^{a_p}`$ is not matched by $`\varphi (M)`$. Then, by the definition of $`\varphi (M)`$, $`u_p^{a_p+1}`$ is also not matched by $`\varphi (M)`$. Let $`h`$ be the smallest integer in $`[1,p]`$ such that $`u_h^{a_h+1}`$ is not matched by $`\varphi (M)`$. Notice that, for all $`\mathrm{}<h`$, $`u_{\mathrm{}}^{a_{\mathrm{}}+1}`$ is matched to $`v_{\mathrm{}}^{b_{\mathrm{}}1}`$; furthermore, $`\varphi (G)`$ contains an edge between $`v_{\mathrm{}}^{b_{\mathrm{}}1}`$ and $`u_{\mathrm{}+1}^{a_{\mathrm{}+1}+1}`$. Thus, $`P_{i+1}=u^{i+1},v_0^{b_01},u_1^{a_1+1},v_1^{b_11},`$ $`\mathrm{},u_h^{a_h+1}`$ is an even-length alternating path for $`\varphi (M)`$. Similarly, for $`j=i+2,\mathrm{},\beta `$, we can use $`P_i`$ to define an even-length alternating path $`P_j`$ for $`\varphi (M)`$ starting from $`u^j`$. By construction, $`P_i,P_{i+1},\mathrm{}P_\beta `$ are node-disjoint. ∎

The next lemma is the basis of our cavity matching algorithm. It shows that given $`\mathrm{mwm}(G)`$ (i.e., the weight of $`M`$), we can compute $`\mathrm{mwm}(G\{u\})`$ from the values $`\rho (u^i)`$, and all the $`\rho (u^i)`$’s can be found in $`O(W)`$ time.

###### Lemma 10.

1. $`_{1i\beta }\rho (u^i)=\mathrm{mwm}(G)\mathrm{mwm}(G\{u\})`$.
2. For all $`u^i\varphi (G)`$, $`\rho (u^i)`$ can be computed in $`O(W)`$ time in total.

###### Proof.

The two statements are proved as follows.

Statement 1. Let $`k`$ be the largest integer such that $`\rho (u^k)=1`$. By Lemma 9, $`\rho (u^i)=1`$ for all $`1ik`$, and $`0`$ otherwise. Note that if $`\rho (u^i)=1`$, $`u^i`$ must be matched by $`\varphi (M)`$. Thus, $`_{1i\beta }\rho (u^i)=k`$. Below, we prove the following two equalities:

* $`\mathrm{mm}(\varphi (G)\{u^1,\mathrm{},u^k\})=\mathrm{mm}(\varphi (G))k`$.
* $`\mathrm{mm}(\varphi (G)\{u^1,\mathrm{},u^\beta \})=\mathrm{mm}(\varphi (G)\{u^1,\mathrm{},u^k\})`$.

Then, by Lemma 8, $`\mathrm{mwm}(G)=\mathrm{mm}(\varphi (G))`$ and $`\mathrm{mwm}(G\{u\})=\mathrm{mm}(\varphi (G)\{u^1,\mathrm{},u^\beta \})`$. Thus, $`\mathrm{mwm}(G)\mathrm{mwm}(G\{u\})=k`$ and Statement 1 follows.

To show Equality (1), let $`H`$ be the set of edges of $`\varphi (M)`$ incident to $`u^i`$ with $`1ik`$. Let $`M^{}=\varphi (M)H`$. Then, $`|M^{}|=|\varphi (M)|k`$. We claim that $`M^{}`$ is a maximum cardinality matching of $`\varphi (G)\{u^1,\mathrm{},u^k\}`$. Hence, $`\mathrm{mwm}(\varphi (G)\{u^1,\mathrm{},u^k\})=|\varphi (M)|k`$, and Equality (1) follows. We prove the claim by contradiction. Suppose $`M^{}`$ is not a maximum cardinality matching of $`\varphi (G)\{u^1,\mathrm{},u^k\}`$. Then, there exists an alternating path $`P`$ that can modify $`M^{}`$ to a larger matching of $`\varphi (G)\{u^1,\mathrm{},u^k\}`$ ; in particular, the length of $`P`$ must be odd and both of its endpoints are not matched by $`M^{}`$. $`P`$ must start from some node $`v^j`$ with $`u^iv^j\varphi (M)`$ and $`i<k`$; otherwise, $`P`$ is alternating for $`\varphi (M)`$ in $`G`$ and $`\varphi (M)`$ cannot be a maximum cardinality matching of $`\varphi (G)`$. Let $`Q`$ be a path formed by joining $`u^iv^j`$ with $`P`$. $`Q`$ is an even-length alternating path for $`\varphi (M)`$ starting from $`u^i`$ in $`\varphi (G)`$. This contradicts the fact that there is no even-length alternating path for $`\varphi (M)`$ starting from $`u^i`$ for $`i<k`$.

To show Equality (2), we first note that $`\mathrm{mm}(\varphi (G)\{u^1,\mathrm{},u^\beta \})\mathrm{mm}(\varphi (G)\{u^1,\mathrm{},u^k\})`$. It remains to prove the other direction. By Lemma 9, we can find $`\beta k`$ node-disjoint even-length alternating paths $`P_{k+1},\mathrm{},P_\beta `$ for $`\varphi (M)`$, which start from $`u^{k+1},\mathrm{},u^\beta `$. $`P_j`$ starts at $`u^j`$. Let $`M^{\prime \prime }=(\varphi (M)(P_{j+1}\mathrm{}P_\beta ))(\varphi (M)(P_{j+1}\mathrm{}P_\beta ))`$. Note that $`|M^{\prime \prime }|=|\varphi (M)|`$ and there are no edges in $`M^{\prime \prime }`$ incident to any of $`u^{k+1},\mathrm{},u^\beta `$. $`M^{\prime \prime }`$ is a matching of $`\varphi (G)\{u^{k+1},\mathrm{},u^\beta \}`$ and $`M^{\prime \prime }H`$ of $`\varphi (G)\{u^1,\mathrm{},u^\beta \}`$. $`|M^{\prime \prime }H||M^{\prime \prime }|k=|\varphi (M)|k`$. Since $`\mathrm{mm}(\varphi (G)\{u^1,\mathrm{},u^k\})=|\varphi (M)|k`$ by Equality (1), it follows that $`\mathrm{mm}(\varphi (G)\{u^1,\mathrm{},u^\beta \})|M^{\prime \prime }H|\mathrm{mm}(\varphi (G)\{u^1,\mathrm{},u^k\})`$. Therefore, Equality (2) holds.

Statement 2. We want to determine whether $`\rho (u^i)=0`$ for all nodes $`u^i\varphi (G)`$ in $`O(W)`$ time. By definition, $`\rho (u^i)=0`$ if and only if there is an even-length alternating path for $`\varphi (M)`$ starting from $`u^i`$. Let us partition the nodes of $`\varphi (G)`$ into two parts: $`\varphi (X)=\{u^i\varphi (G)uX\}`$ and $`\varphi (Y)=\{u^i\varphi (G)uY\}`$. Below, we give the details of computing $`\rho (u^i)`$ for all $`u^i\varphi (X)`$. The case where $`u^i\varphi (Y)`$ is symmetric.

Let $`D`$ be a directed graph over the node set $`\varphi (X)`$. $`D`$ contains an edge $`u^iv^j`$ if there exists a node $`w^k\varphi (Y)`$ such that $`u^iw^k\varphi (G)\varphi (M)`$ and $`w^kv^j\varphi (M)`$. Consider any node $`v^j`$ of $`D`$ that is unmatched by $`\varphi (M)`$. A directed path in $`D`$ from $`v^j`$ to a node $`u^i`$ corresponds to a path in $`\varphi (G)`$, which is indeed an even-length alternating path for $`\varphi (M)`$ starting from $`u^i`$. Therefore, for any $`u^i\varphi (X)`$, $`\rho (u^i)=0`$ if and only if $`u^i`$ is reachable from some node in $`D`$ that is unmatched by $`\varphi (M)`$. We can identify all such $`u^i`$ by using a depth-first search on $`D`$ starting with all the nodes unmatched by $`M`$. The time required is $`O(|D|)`$. As $`|D||\varphi (G)|=W`$, the lemma follows. ∎

The following procedure computes $`\mathrm{mwm}(G\{u\})`$ for all nodes $`u`$ of $`G`$. Let $`M`$ be a maximum weight matching of $`G`$.

Procedure Compute-All-Cavity$`(G,M)`$

1. Construct $`\varphi (G)`$ and $`\varphi (M)`$.
2. For every $`j[0,n/2]`$, determine $`A_j`$ from $`\varphi (M)`$.
3. For every node $`u^i`$ of $`\varphi (G)`$, if $`u^i_jA_j`$ then $`\rho (u^i)=0`$; otherwise $`\rho (u^i)=1`$.
4. For every node $`u`$ of $`G`$, compute $`\mathrm{mwm}(G\{u\})=\mathrm{mwm}(G)_{1i\beta }\rho (u^i)`$ where $`u^1`$, $`u^2`$, $`\mathrm{}`$, $`u^\beta `$ are the nodes corresponding to $`u`$ in $`\varphi (G)`$.

###### Theorem 11.

Compute-All-Cavity$`(G,M)`$ correctly computes $`\mathrm{mwm}(G\{u\})`$ for all $`u`$ of $`G`$ in $`O(W)`$ time.

###### Proof.

Follows from Lemma 10

## Acknowledgments

The authors wish to thank the anonymous referee for extremely helpful comments, which significantly improved the presentation of the paper. In particular, Theorem 2 was originally proved using unfolded graphs (see the conference version of this paper ); the new proof is based on a suggestion by the referee.


format: text

text:
# On the hypothesis of an advection-dominated flow in the core of NGC 1052: new constraints from a BeppoSAX observation

## 1 Introduction

The discovery of supermassive black holes ($`10^6`$$`10^9M_{}`$) in the nuclei of several nearby galaxies (Magorrian et al. 1998) has raised the question of why most of them are not active. A possible solution is provided by the so called Advection Dominated Accretion Flows (ADAF; Rees 1982; Narayan & Yi 1995; Fabian & Rees 1995). In this class of accretion solutions, the accreting gas is so tenuous that it cannot cool efficiently, the viscous energy is stored in the protons as thermal energy and eventually advected onto the nuclear compact object. The ADAFs are therefore characterized by small radiative efficiency and accretion rates ($`\dot{m}\dot{M}/\dot{M}_{\mathrm{Edd}}<10^{1.6}`$; Narayan & Yi 1995; Rees et al. 1982). At low $`\dot{m}`$ the hard X-ray emission is mainly due to bremsstrahlung emission from a population of $``$$`100`$ keV electrons, and is therefore much harder than typically observed in Seyfert galaxies (Nandra et al. 1997; Turner et al. 1997; Matt 2000).

Recently, hard X-ray tails have been discovered in the ASCA spectra of several elliptical galaxies (Allen et al 2000). Photon indices are in the range 0.6–1.5, therefore remarkably consistent with the expectations of the ADAF scenario. Unfortunately, the ASCA energy bandpass is limited to 9–10 keV, and the detection of these hard tails is therefore difficult and somewhat model-dependent.

One of the most intriguing of these ADAF-candidates is the nearby ($`z=0.0049`$) elliptical galaxy NGC 1052. It is a narrow-line LINER (Heckman 1980), with a compact radio core (diameter $``$$`0.14`$ pc) and a radio halo of about 3 kpc diameter. NGC 1052 is the first type 2 LINER where broad lines in spectropolarimetric measurements have been discovered (Barth et al. 1999). The ASCA spectrum (Guainazzi & Antonelli 1999, G99; Weaver et al. 1999) is extremely flat: a formal fit with a simple power law yields a photon index $`\mathrm{\Gamma }0.1`$. This suggests either high photoelectric absorption (column density $`N_\mathrm{H}10^{23}`$ cm-2) or a Compton-reflection dominated spectrum (which, of course, would imply an even more strongly absorbed active nucleus). In the former scenario the intrinsic spectral index is still very flat ($`\mathrm{\Gamma }1.2`$). This is intriguingly consistent with the ADAF scenario.

The ASCA results prompted a BeppoSAX program of observations of narrow-line LINERs with broad spectropolarimetric lines, mainly focused to investigate their hard X-ray spectrum ($`\text{ }>`$10 keV). The results of this experiment on NGC 1052 are reported in this paper.

## 2 Observation and data reduction

BeppoSAX observed NGC 1052 between 2000 January 11 (19:27 UT) and 13 (08:57 UT). The instruments were operating in nominal direct modes. Data reduction and analysis followed standard procedures, as detailed, e.g., in Guainazzi et al. (1999). Scientific products from the imaging instruments (Low Energy Concentrator Spectrometer, LECS; Parmar et al. 1997; Medium Energy Concentrator Spectrometer, MECS; Boella et al. 1997) were extracted from circular regions around the galaxy X-ray centroid of radii 2$`\mathrm{}`$ and 4$`\mathrm{}`$, respectively. Background subtraction was performed using deep blank sky field exposures, accumulated by the BeppoSAX Science Data Center (SDC). The background-subtracted net count rates are $`(1.26\pm 0.09)\times 10^2`$ s-1 and $`(3.71\pm 0.08)\times 10^2`$ s-1, in the LECS (0.1–4 keV) and MECS (1.8–10.5 keV), respectively, corresponding to exposure times of 25.8 and 63.2 ks. Spectral analysis made use of the latest response matrices released by the SDC in January 2000.

In what follows: energies are quoted in the source rest frame, and errors are at 90% confidence level for one interesting parameter ($`\mathrm{\Delta }\chi ^2=2.71`$), unless otherwise specified.

## 3 Results

### 3.1 The PDS spectrum ($`E>10`$ keV)

The 60.0 ks exposure time on NGC 1052 allowed a PDS detection, with a total 13–200 keV count rate of $`0.22\pm 0.04`$ s-1. If we take into account the typical systematic uncertainties associated with the PDS background subtraction algorithm (Guainazzi & Matteuzzi 1997), the detection is at a level higher then 5$`\sigma `$ in the 13–90 keV band (see Fig. 1). No known hard X-ray bright source is present in the (1.3)2 PDS field of view. The number of expected sources with flux equal or higher than NGC 1052 is $`\text{ }<0.06`$ according to the Cagnoni et al. (1998) logN-logS relation.

A simple power-law fit of the PDS spectrum yields a very flat index: $`\mathrm{\Gamma }=1.0\pm _{0.3}^{0.7}`$.

### 3.2 The broadband BeppoSAX Spectrum (0.1–100 keV)

The source did not show any significant X-ray variability during the BeppoSAX observation. The reduced $`\chi ^2`$, when a constant line is fit to the $`\mathrm{\Delta }t=5760`$ s light curve are $`\chi _\nu ^2=0.76`$ and $`\chi _\nu ^2=0.78`$ in the 0.1–2 keV (LECS) and 2–10 keV (MECS) energy bands, respectively. We will therefore focus in this Section on the time-averaged spectra only.

A photoelectrically-absorbed single component model provides an inadequate fit of the broadband (0.1–100 keV) BeppoSAX spectrum (e.g.: $`\chi ^2=185.4/80`$ degrees of freedom, dof, if a power-law model is employed). On the other hand, a very good fit ($`\chi _\nu ^21.02`$$`1.03`$) is obtained with a two-component model, constituted by an absorbed ($`N_\mathrm{H}`$ a few $`10^{23}`$ cm-2) power-law plus a “soft excess” below 2 keV. The limited statistics prevents us from unambiguously characterizing the latter component. In the following we will discuss, as illustrative examples, models where this soft excess is described: either with a power-law (“P” model hereinafter), whose index is held fixed to that of the high-energy absorbed power-law (thus modeling reflection of the nuclear continuum, scattered by an electron plasma - “warm mirror” - along our line of sight; Antonucci & Miller 1985); or with thermal emission from a collisionally ionized, optically thin plasma (mekal model in Xspec; “M” model hereinafter). Model “P” also describes a geometry, in which the absorber only covers a fraction of the line of sight. The best-fit parameters are reported in the upper panel of Tab. 1. As already suggested by the analysis of the PDS spectrum alone, the absorbed power-law component is rather flat ($`\mathrm{\Gamma }1.4`$). If the power-law in model “P” is substituted by a thermal bremsstrahlung ($`\chi ^2=83.6/77`$ dof), its temperature is $`150\pm _{100}^{720}`$ keV.

The addition of a narrow Gaussian emission line is required at the 98.9% confidence level, according to the F-test, in the “P” model ($`\mathrm{\Delta }\chi ^2|_P=10`$ for a decrease of the degrees of freedom by two), whereas only at the 90.9% level in the “M” model ($`\mathrm{\Delta }\chi ^2|_M=5`$). The Gaussian line centroid energy is consistent, within the statistical uncertainties, with Kα fluorescent emission from neutral iron. However, the $`EW`$ of the iron line system is too large to be produced in transmission by the same cold matter, which is responsible for the attenuation of the X-ray continuum (which would imply $`EW`$130 eV for a spherical distribution of matter; Leahy & Creighton 1993). No iron emission line is expected from an ADAF. The slight difference in $`EW`$ between models “P” and “M” (in the latter the iron line profile is partly accounted by the emission of the thermal plasma) may suggest a multi-component structure of the iron line, which is unresolved by the MECS. Ionized iron lines could be also produced by the “warm mirror” (Netzer & Turner 1997). We have therefore repeated the fit in the “P” scenario, assuming that the iron emission actually consists of two components: one neutral ($`E_\mathrm{c}=6.4`$ keV) and one He-like ($`E_\mathrm{c}=6.7`$ keV). The fit is of comparable quality ($`\chi ^2=79.8/77`$ dof), with: $`EW`$(6.4 keV) $`=170\pm _{150}^{170}`$ eV; $`EW`$(6.7 keV) $`=180\pm _{160}^{150}`$ eV. The soft excess continuum flux at 6 keV is about 1/3 of that of the transmitted component. Therefore, the EW of the ionized iron line against its proper continuum would be of the correct order of magnitude if produced in a “warm mirror” (Matt et al. 1996). The neutral component $`EW`$ is now consistent with being produced in transmission by the same matter covering the active nucleus, if its covering factor is large.

A hard X-ray continuum could be in principle due to Compton reprocessing of the nuclear continuum, by either the accretion disc (George & Fabian 1991; Matt et al. 1992) or the molecular torus encompassing the active nucleus (Ghisellini et al. 1994; Krolik et al. 1994). This scenario does not, however, match our data. A fit, where the absorbed high-energy component is a bare face-on Compton-reflection (model pexriv in Xspec; Magdziarz & Zdziarski 1995) is statistically unacceptable ($`\chi ^2=112.6/76`$ dof). The addition of a Compton-reflection component to the “P” model (where only the relative normalization between the reflected and the direct component, $`R`$, and the intrinsic power-law cut-off energy are left free parameters in the fit; an inclination angle of $`30^{}`$ and solar abundances are assumed) does not significantly improve the fit ($`\chi ^2=79.1/75`$ dof). The 90% upper limit for two interesting parameter on R is 0.6 (for $`\mathrm{\Gamma }<1.65`$). These results allow us to rule out one class of models, which adequately fit the ASCA-ROSAT spectra, hence favoring the G99 transmission scenario.

The observed flux in the 0.5–2 keV (2–10 keV) energy band is 0.4 (4.0)$`\times 10^{12}`$ erg cm-2 s-1. This corresponds to a luminosity of 0.4 (4.2)$`\times 10^{41}`$ erg s-1.

### 3.3 Comparison with ROSAT and ASCA data

In the central panel of Tab. 1, the best-fit parameters are reported, when the “M” and “P” models are applied to the ASCA and ROSAT spectra of NGC1052 (see the Tab. 1 in G99). NGC 1052 was comparatively bright during the August 1996 ASCA (2–10 keV flux $``$$`3.5\times 10^{11}`$ erg cm-2 s-1) and the January 2000 BeppoSAX observations. The only spectral parameter showing a significant difference is the absorbing column density, which was about a factor of 2 higher in the later BeppoSAX observation. The spectral indices measured by BeppoSAX tend also to be slightly softer, but still consistent with the ASCA-ROSAT measurements within the statistical uncertainties.

We have performed a simultaneous fit of the ROSAT, ASCA and BeppoSAX spectra, to check whether the improved statistics allows us to distinguish between the “M” and “P” models. In these fits only the column density absorbing the primary nuclear continuum has been allowed to vary independently in the BeppoSAX and ASCA-ROSAT models (ROSAT spectra are basically insensitive to column densities of the order of $`10^{23}`$ cm-2). Normalization constants have been included as free parameters in the models, to account for the different fluxes measured in the three observations. The results are reported in the lower panel of Tab. 1. The two models yield comparably good fits ($`\chi ^2|_P=386.0/445`$ dof; $`\chi ^2|_M=383.0/444`$ dof). Better data quality is needed to resolve this issue. The spectral index is indeed much better constrained than by BeppoSAX data alone, and still very flat (see Fig. 2).

## 4 Discussion

NGC 1052 is the first “type 2” LINER, where broad lines were discovered in spectropolarimetric measurement (Barth et al. 1999). One may therefore expect that its X-ray spectrum resembles that of Seyfert 2 galaxies, where the luminous nuclear emission is photoelectrically absorbed by matter with a substantial column density. The observation performed with BeppoSAX demonstrates that this is indeed the case, thanks to the first measure of the broadband (0.1–100 keV) X-ray spectrum of this object.

Even more intriguing is the nature of the accretion flow in this AGN. The nuclear spectrum is rather flat ($`\mathrm{\Gamma }1.4`$), as the ASCA observation had already suggested (G99; Weaver et al. 1999). The best-fit value is inconsistent at 2$`\sigma `$ level with the distribution of spectral indices observed in Seyfert 1s ($`\mathrm{\Gamma }_{\mathrm{Sy1}}=1.87`$; $`\sigma _{\mathrm{Sy1}}=0.22`$; Nandra et al. 1997; Reynolds 1997) and radio-quiet quasars ($`\mathrm{\Gamma }_{\mathrm{RQQ}}=1.93`$; $`\sigma _{\mathrm{RQQ}}=0.22`$; Reeves & Turner 2000). It is closer to the distribution of spectral indices in radio-loud quasars ($`\mathrm{\Gamma }_{\mathrm{RLQ}}=1.6`$; $`\sigma _{\mathrm{RLQ}}=0.15`$; Reeves & Turner 2000). However, NGC 1052 radio-loudness, according to the Wilkes & Elvis (1987) definition, is 1.1, therefore pointing to a radio-quiet or, at most, a borderline object. There are some Seyfert 2s, whose ASCA spectral indices (Turner et al. 1997) are as flat as those measured in NGC 1052. Recently, Malaguti et al. (1999) pointed out that at least in one case (NGC 2110) this could be due to an incorrect modeling of a complex photoelectric absorber in the ASCA bandpass. To verify this hypothesis, we have extracted from the BeppoSAX archive the PDS spectra of the “flat” Seyfert 2s of the Turner et al. (1997) sample. In Fig. 3

we compare the $`\mathrm{\Gamma }`$ versus 2–10 keV (extrapolated) flux iso-$`\chi ^2`$ contours for NGC 1052 and the “flat” Seyfert 2s (the results for NGC 5252 are not shown, because the PDS detection is too weak). In all cases the intrinsic spectral index as measured by the PDS is significantly steeper than in ASCA. This suggests that the nature of the accretion flow in the nucleus of NGC 1052 is qualitatively different from that normally at work in bright nearby AGN.

The NGC 1052 high-energy spectrum is can be also well approximated by a thermal bremsstrahlung with $`kT150`$ keV, in agreement with the expectations of the ADAF scenario. No estimate of the nuclear black hole mass is available for NGC 1052. If we use the bulge B magnitude (Ho et al. 1997) versus black hole mass relation of Magorrian et al. (1998), we obtain $`M_{\mathrm{BH}}10^{8\pm 1}M_{}`$. The bolometric luminosity of the ADAF component extrapolated from the BeppoSAX measurement is $``$$`5\times 10^{42}`$ erg s-1, suggesting an accretion rate $`\dot{m}10^{4\pm 1}`$. This value is significantly lower than the critical $`\dot{m}`$, below which the onset of the ADAF regime would occur (Narayan & Yi 1995).

Critical diagnostic tools for the existence of an ADAF are the radio-to-X-ray Spectral Energy Distribution (SED) and luminosity ratio (Di Matteo et al. 2000). In Fig. 4 we show the NGC 1052 radio/X-ray SED. The radio

data points are taken from the NED archive. We observe a good qualitative agreement between the shape of the SED in NGC 1052 and in the “candidate-ADAF” elliptical galaxies of the Allen et al. (2000) sample. In Tab. 2 we compare the ratios between the powers at 6 keV and 5 GHz in these galaxies and in NGC 1052. In the latter this ratio is well within the (rather narrow)

range observed in the former objects, confirming the qualitative similarity. For comparison, the value of this ratio is typically $`\text{ }>10^5`$ in radio-quiet quasars (Elvis et al. 1994)

It is also interesting to compare the X-ray with the IR photometry of Becklin et al. (1982). Their 1.2$`\mu `$m flux in the innermost 2$`\mathrm{}`$ ($``$300 pc) - 26 mJy - corresponds to a $`L(1.25\mu m)/L(5keV)`$ ratio of about 15. Such a high value is typical of Seyfert 2 galaxies (Mass-Hesse et al. 1995). The IR emission is therefore likely to be dominated by heated dust, totally masking the ADAF IR intrinsic emission and therefore preventing us from checking the presence of a wind in the ADAF scenario (Di Matteo et al. 2000).

The luminosity of the broad component of Hβ is $``$$`2\times 10^{41}`$ erg s-1 (Ho et al. 1997; Barth et al. 1999). An ADAF cannot provide the corresponding amount of (mainly UV) ionizing photons. This points to a flow with a small sonic radius $`r_\mathrm{s}`$, consistent with models where the viscosity parameter $`\alpha `$ is $`\text{ }<10^2`$ ($`r_\mathrm{s}`$ a few $`R_\mathrm{g}`$; Narayan et al. 1997). Outside this radius the flow would smoothly connect to a standard thin accretion disk.

The BeppoSAX data alone cannot rule out the possibility that a substantial contribution to the hard X-ray emission comes from a nuclear relativistic jet. Chandra will have enough spatial resolution to image X-ray structures on scales as small as $``$100 pc. However, it is to be noted that the ROSAT HRI images of NGC 1052 unveiled only a soft X-ray extended emission on a much wider scale ($``$15 kpc) than that of the radio structures (G99), therefore probably due to the emission of diffuse intergalactic gas. The contribution of this component to the hard X-ray emission is most likely negligible.

###### Acknowledgements.

The BeppoSAX satellite is a joint Italian-Dutch program.This research has made use of the NASA/IPAC Extragalactic Database (NED) which is operated by the Jet Propulsion Laboratory, California Institute of Technology, under contract with the National Aeronautics and Space Administration.


text:
# Nuclear Halo and Molecular States

## Introduction

Clustering within nuclei is a widespread phenomenom which takes on many guises across the nuclear landscape. Until relatively recently cluster studies have been confined to on or near the line of beta stability where the rôle of $`\alpha `$-clustering has long been established Freerreview . As clustering is expected to manifest itself most strongly near thresholds Ikeda , exotic structures might be expected to form in very neutron (or proton) rich systems. Over the last decade the exploration of clustering in nuclei far from stability has become technically feasible as demonstrated most clearly by the discovery and subsequent probing of the nuclear halo Han95 . Whilst an excess of neutrons (or protons) may naïvely be expected to dilute any underlying $`\alpha `$-cluster structures, theoretical Sey81 ; AMD  and experimental work vonO ; Fre99  indicate that molecular type structures such as $`\alpha `$-chains “bound” by valence neutrons may exist.

In the present paper a number of selected topics concerning the study of halo and molecular states in light, neutron-rich nuclei will be reviewed. As they exhibit many of the facets of clustering and structural evolution far from stability the neutron-rich Be isotopes have been chosen as examples. In parallel, the techniques which have been developed to aid in probing the structure of such nuclei far from stability will also be discussed.

## Reaction Spectroscopy

### Single-Nucleon Transfer Reactions

One of the issues of prime importance in the study of nuclei far from stability is the extraction of reliable spectroscopic information. For nuclei on or near stability light-ion (p, d, …) induced single-nucleon transfer reactions have long been one of the tools of choice. The application of such reactions to nuclei far from stability presents a number of experimental challenges Win97 ; Cat00 . Most significantly, whilst the cross sections are moderately high ($``$1-10 mb/sr) the short halflives of the nuclei of interest dictate that beams of these nuclei be used in inverse kinematics reactions. The consequent constraints on the final excitation energy and angular resolution limit the target thickness to the order of 1 mg/cm2 and beams of at least some 104 pps are required in order to obtain angular distributions in a reasonable measurement time.

A recent study For99 ; Win00  of the structure of the single-neutron halo nucleus 11Be via the p(11Be,10Be)d reaction at 35 MeV/nucleon provides a prototypical example of some of the features inherent in such reaction studies. Experimentally a magnetic spectrometer operated in a dispersion matched mode was employed to detect the heavy ejectile (10Be). In order to remove the contamination arising from reactions on the C in the (CH2)n target an array of large area silicon detectors was used to detect the coincident deuterons (figure 1). With a beam intensity of $``$3$`\times `$104 pps angular distributions of reasonable quality were acquired in some 72 hours of running (figure 1).

In addition to the experimental features illustrated by this experiment it should be stressed that the analysis is not model independant. For example, not only did the weakly bound nature of 11Be and the d have to be taken into account but realistic wavefunctions had to be employed – here coupling to the strongly deformed 10Be core needed to be properly accounted for. Indeed, the use of the standard separation energy approach to derive the radial form factors lead to an artifically high core excited state admixture. As detailed in refs For99 ; Win00 , careful analysis indicates that the ground state of 11Be is dominated (85%) by the admixture corresponding to the valence neutron occupying the 2s1/2 orbital together with a modest contribution (15%) from the core excited (2+$`\nu `$1d5/2) configuration.

### Single-Nucleon Removal Reactions

Measurements of one-nucleon removal (or “knockout”) reactions on light targets have recently been proposed as a spectroscopic tool for high-energy radioactive beams Nav98 ; Tos99 . This approach has arisen from the development of reaction calculations for halo nuclei in which the strong absorption limit Huf81  and core excited states are accounted for Tos99 . More specifically, the cross sections for the population of a given state of the core fragment ($`I_c^\pi `$) may be related to spectroscopic factors ($`C^2S(I_c^\pi ,nlj)`$) using an extended version Tos99 ; Tos00  of the spectator-core model Hus85  to calculate the cross section ($`\sigma _{sp}`$) for the removal of the nucleon ($`nlj`$).

$$\sigma (I_c^\pi )=\underset{nlj}{}C^2S(I_c^\pi ,nlj)\sigma _{sp}(nlj,S_n^{eff})$$
(1)
The corresponding momentum distributions are derived within the same eikonal formalism Sau00  or in a simpler fashion using the opaque limit of the Serber model Han96 ; Esb96 . As noted above, the integrated cross sections for the population of the core excited states are directly related to the associated spectroscopic factors. In analogy with transfer reactions, the shape of the core fragment momentum distributions plays the rôle of the angular distributions in specifying the $`l`$ of the removed nucleon. Experimentally the core fragment states are identified by the de-excitation $`\gamma `$-rays emitted in-flight, whilst a high acceptance magnetic spectrograph is used to determine the momenta.

One of the principal virtues offered by high energy nucleon removal is the applicability very far from stability where beam rates are low. This ability to function with intensities as low as 1pps is a consequence of the large cross sections ($``$10-100 mb), coupled with the high beam energies ($``$40 MeV/nucleon) which allow for the use of thick targets ($``$100 mg/cm2).

A particularly clear example111Studies of other near dripline and halo nuclei may be found in ref’s Nav98 ; Aum00 ; Gui00 ; Mad00 . of the application of the technique may be found in the measurement of single-neutron removal from 12Be Nav00 , whereby the only bound core states are the ground (Jπ=1/2+) and 320 keV (1/2-) levels in 11Be. In simple terms, the population of the 11Be ground state provides a measure of the 2$`\mathrm{}\omega `$ admixture present in 12Be. The results of the experiment, which indicate only a $``$30% admixture of the $`p^2`$-configuration in 12Be, provide direct confirmation She99 ; Be12beta2  of the breakdown in the N=8 shell closure.

The potential power of the technique is further illustrated by a recent systematic investigation of a broad range of light, neutron-rich psd-shell nuclei Sau00 . The inclusive longitudinal momentum distributions which were obtained in a single rigidity setting are displayed in figure 2 whereby a number of features are immediately apparent. Most notably, the crossing of the N=8 shell and N=14 sub-shell closures are associated with a marked reduction in the widths of the core momentum distributions (viz, 14,15B, 15,16C, 23O and 24,25F). The former effect arises from the large $`\nu `$2s1/2 admixtures expected in the ground states of the Z=4-6, N=9 isotones Mad00 ; Ren97 ; Alb74 ; AJZ86 , which also persists for N=10, as suggested by recent studies of 14Be Lab00 ; Suz99  (see below). A narrowing of the momentum distributions may also be expected for N=15 and 16, as in a simple shell model picture the valence neutrons occupy the $`\nu `$2s1/2 orbital. Such results demonstrate that coupled with a high acceptance, broad range spectrograph, high energy single-nucleon removal reactions offer a powerful means to survey structural evolution over a wide range of isospin in a single experiment.

Finally, in the context of high energy reactions, it should also be noted, as described by Tostevin and Al-Khalili Tos00 ; AlK96 , that few-body Glauber model analyses of total reaction cross sections can also provide important constraints on the ground state wavefunctions of halo-like nuclei. As presented in the contribution to these proceedings by Suzuki, such analyses are now becoming more widespread in their application.

## Nuclear Molecular Clusters

As alluded to in the introduction, the $`\alpha `$-particle plays an important rôle in the structure of light $`\alpha `$-conjugate (A=4n) nuclei Freerreview . This is a direct consequence of the strongly bound character of the 4He nucleus and the weakness of the $`\alpha `$-$`\alpha `$ interaction, as evidenced by the unbound nature of 8Be. The persistence of cluster structures for systems lying away from the line of beta-stability is well illustrated, as will be discussed here, by the beryllium isotopes, for which the $`\alpha `$-$`\alpha `$ system may be regarded as the basis.

From a theoretical point of view, prescriptions such as the Molecular-Orbital Model (MO) Sey81  or the Two-Centre Shell Model (TCSM) TCSM , in which valence nucleons are added to the single-particle orbits arising from the two-centre potential, provide a successful means to describe the properties of these nuclei. Moreover these orbits may be viewed as the analogues of the $`\sigma `$ and $`\pi `$-orbitals associated with the covalent binding of atomic molecules. The development of fully fledged Antisymmeterised Molecular Dynamics calculations (AMD) AMD  is of particular interest as the N-nucleon system is modelled without any a priori imposition of an underlying cluster structure. Recent calculations, in particular, suggest the existence of two-centred structures in the Be, B and C isotopic chains with valence neutron density distributions exhibiting the features of molecular orbitals AMD .

From an experimental perspective, von Oertzen vonO  has compiled systematic evidence for the existence of dimers in 9-11Be and 9-11B. In the case of 9Be, for example, the presence of a valence neutron results in a bound (Borromean) system, the ground and excited states of which may be understood in terms of a three-body $`\alpha `$:n:$`\alpha `$ molecular structure. In particular, the rotational bands based on the ground and low-lying states exhibit large deformations consistent with the associated molecular configurations.

In the case of 10Be, the experimental evidence for molecular configurations is rather less well documented. Beyond the established 0$`{}_{2}{}^{}{}_{}{}^{+}`$, 2$`{}_{2}{}^{}{}_{}{}^{+}`$ and 1$`{}_{1}{}^{}{}_{}{}^{}`$ – 4$`{}_{1}{}^{}{}_{}{}^{}`$ states, the locations of the J=5 vonO  and 6 members of the of the negative parity band, as well as the J=4 and 6 members of the positive parity band have been postulated following recent studies of the $`\alpha `$-6He breakup of 10Be Soic ; Fre00 . As displayed in figure 3 Fre00 , the spin-energy trajectories for the bands based on the 0$`{}_{2}{}^{}{}_{}{}^{+}`$ and 1$`{}_{1}{}^{}{}_{}{}^{}`$ states at $``$6 MeV are consistent with large deformations as expected for molecular-like $`\alpha `$:2n:$`\alpha `$ structures. Moreover, the location of the bandheads just below the threshold for $`\alpha `$ \+ 6He decay is in accordance with the considerations of Ikeda describing the formation of clusters Ikeda . Further support for the postulated molecular states may be found in the recent AMD calculations of Kanada-En’yo and collaborators AMD , whereby well developed $`\alpha `$:2n:$`\alpha `$ configurations are predicted for the 0$`{}_{2}{}^{}{}_{}{}^{+}`$ and 1$`{}_{1}{}^{}{}_{}{}^{}`$ bands.

Given the existence of such molecular-type structures in 10Be, the question naturally arises as to the existance of similar structures even further from stability. In this context the dripline nucleus 12Be has been investigated. In a recent study222The existence of such structures was hinted at in an earlier study by Korsheninnikov et al. Kor . employing the inelastic excitation of an energetic (35 MeV/nucleon) secondary beam of 12Be, evidence has been found in the breakup into 6He+6He of rotational states (J=4, 6, 8) in the excitation energy range 10-20 MeV Fre99 . As illustrated in figure 4, the inferred momenta of inertia ($`\mathrm{}^2/2\mathrm{}`$=0.15$`\pm `$0.04 MeV) and bandhead energy (10.8$`\pm `$1.8 MeV) of the observed states are consistent with the cluster decay of a molecular structure which may be associated with $`\alpha `$:4n:$`\alpha `$ configurations.

Further experimental support for the molecular nature of these states would be the observation of large spectroscopic factors for the associated clusters. The measurement of partial decay widths represents, however, formidable experimental challenges, though the presence of relatively few decay channels for the states in question may facilitate the measurements. Of additional interest is the search for in-band gamma transitions which should also furnish information on the degree of clustering Gai . Such measurements may be possible in the near future through $`\alpha `$-pickup reactions – such as 12C(6,8He,10,12Be)8Be – carried out in conjunction with high efficiency charged particle and gamma arrays.

## Halo States

Perhaps the most extreme form of clustering is that exhibited by halo nuclei, whereby one or more nucleons reside on average well beyond the core potential Han95 . In the present discussion the two-neutron halo nucleus 14Be will be used as an illustrative example. In particular, the spectroscopy of 13,14Be, continuum excitations of 14Be and the spatial configuration of the halo neutrons will be addressed.

The tool chosen to investigate 14Be in the work described here was a kinematically complete measurement of the fragments (12Be and two neutrons) from the dissociation of a 35 MeV/nucleon beam of 14Be on C and Pb targets. Such a measurement is now a relatively standard technique and allows the two-neutron removal cross sections, neutron angular distributions and invariant mass spectra to be extracted, and the neutron-neutron correlations to be explored.

The details of the experiment will not be repeated here as they have already been described in refs Lab00 ; Mar99 ; Mar00 . It should be stressed, however, that one of the principle problems confronting such measurements is the detection with the highest possible efficiency of two beam velocity neutrons at very forward angles with small relative momenta and minimal cross-talk. As described in refs Mar99 ; Mar00 , the use of a highly granular array arranged in a staggered configuration coupled with off-line cross-talk rejection algorithms (based on kinematic conditions) permit such measurements to be undertaken.

### Structure and Continuum Excitations

The results obtained for the two-neutron removal cross sections, $`\sigma _{2n}`$, the single-neutron angular distributions333The angular distributions were well characterised by a Lorentzian lineshape., $`\mathrm{\Gamma }_n`$, and the associated angle integrated cross sections, $`\sigma _n`$, are displayed in Table 1. The average neutron multiplicities ($`\overline{m}_n=\sigma _n/\sigma _{2n}`$), which have also been deduced, are instructive in terms of the mechanisms leading to dissociation Bar93 . For a light target the reaction is expected to proceed via single-neutron removal (absorption or diffraction) followed by the in-flight decay of 13Be. As approximately equal contributions are expected for absorption and diffraction Bar93  the average neutron multiplicity should be 1.5, in accordance with that measured. This scenario is also supported by the single-neutron angular distribution for the C target which is well reproduced assuming passage via a low-lying resonance in 13Be Lab00 ; Bar96 . In the case of a heavy target, nuclear and Coulomb dissociation occur. Given that Coulomb dissociation results in a multiplicity of 2, the average multiplicity for dissociation on Pb should be between 1.5 and 2, as observed.

The possible existence of a low-lying state in 13Be is of considerable importance in modelling the structure of 14Be Tho96 ; in particular in fixing the 12Be-n interaction. Beyond the single-neutron angular distributions, the relative energy for 12Be + n events may be reconstructed from the measured momenta. The preliminary results of such an analysis Jon00  are displayed in figure 5 together with the results of Monte Carlo simulations (see below) in which levels at 0.5 and 2.0 MeV above threshold are assumed with widths of $`\mathrm{\Gamma }`$=0.5 MeV. The level at 2.0 MeV is that observed in multi-nucleon transfer reaction studies Ost92 ; Bel , whilst the former is consistent with a preliminary result reported by the MSU group Tho95 . Given, as discussed above, the appearance of ground states dominated by a valence $`\nu `$2s1/2 configuration for the neighbouring N=9 isotones 14B and 15C Sau00 ; Gui00 ; Mad00 , together with the predicted continuation of such an inversion for 13Be Ren97 , it appears that the ground state is most probably Jπ=1/2+. Analysis of the 12Be - n angular correlations should shed further light on this conjecture.

The enhanced cross section for dissociation on the Pb target (Table 1) is indicative of a large EMD contribution. Assuming that the nuclear–Coulomb interference is small, the C target data may be scaled to estimate the nuclear contribution to breakup on Pb Lab00 . Given a root-mean-square radius of 3.2 fm for 14Be Suz99 , $`\sigma _{2n}^{nucl}(Pb)`$ = 0.85$`\pm `$0.07 b and, consequently, $`\sigma _{2n}^{EMD}(Pb)`$ = 1.45$`\pm `$0.40 b.

The invariant mass spectra, reconstructed from the measured momenta of the beam and fragments (12Be and two neutrons) from breakup, are displayed in figure 6a and b for the C and Pb targets. The EMD spectrum (figure 6c) has been deduced following subtraction of the estimated nuclear contribution to reactions on Pb and exhibits enhanced strength around 1.5 MeV decay energy ($`E_{decay}`$). Given the complex nature of the response function of the present setup, a detailed Monte Carlo simulation, including the influence of all nonactive materials, was developed based on the GEANT package Lab00 . The results shown in figure 6 were obtained following the descriptions for dissociation on C and Pb outlined above and after filtering through the simulation. In the case of the nuclear induced reactions only the lowest low-lying state in 13Be ($`E_0=0.5`$ MeV, $`\mathrm{\Gamma }_0=0.5`$ MeV) was assumed to be populated following the diffraction of one of the halo neutrons. The EMD was simulated under the assumption that the energy sharing between the 12Be and the two neutrons was governed by 3-body phase space. As shown in figure 6c, the observed EMD decay energy spectrum could be reproduced assuming a Breit-Wigner lineshape with $`E_0=1.8\pm 0.1`$ MeV and $`\mathrm{\Gamma }_0=0.8\pm 0.4`$ MeV. Furthermore, the corresponding simulations of the single-neutron angular distributions were in good agreement with those observed Lab00 .

Thompson and Zhukov have examined 14Be within the framework of a 3-body model in which the 12Be core was treated as inert444An inert core precludes, ab initio, the existence of any simple negative parity resonances. Tho96  and a number of trial wavefunctions developed. Based on the binding energy and matter radius of 14Be, together with the known d-wave resonance at 2.0 MeV in 13Be, two 14Be wavefunctions were favoured (both of which required an s-wave state near threshold in 13Be as suggested above): the so-called D4 wavefunction – 86% $`\nu (2s_{1/2})^2`$ and 10% $`\nu (1d_{5/2})^2`$; and C7 – 29% $`\nu (2s_{1/2})^2`$ and 67% $`\nu (1d_{5/2})^2`$. The EMD decay energy spectra calculated from the corresponding E1 strength functions Tho96  are compared in figure 6 with that of the empirical Breit-Wigner lineshape deduced from the measurements. The corresponding integrated two-neutron removal cross sections are 1.05 b (D4) and 0.395 b (C7) Tho96 , compared to the measured value of 1.45$`\pm `$0.40 b. Although the strength is predicted to be concentrated at a somewhat lower energy than that observed, a large $`\nu (2s_{1/2})^2`$ admixture to the valence neutrons wavefunction is favoured. This conclusion is also supported by the total reaction cross section measurement of Suzuki et al. Suz99  reported in these proceedings.

A microscopic cluster model has also been used to explore 13,14Be Des95 . In the case of 13Be an s-wave state is predicted very close to threshold, whilst the energy of the d-wave resonance is well reproduced. Significantly, a strong E1 transition \[B(E1)$``$1.2e2fm2\] centred at $`E_{decay}=1.5`$ MeV is predicted in 14Be, very close to the structure observed experimentally. Analysis of the corresponding energy surface suggests, however, that this transition is not associated with a true resonance Des95 . Consequently, the enhanced strength observed near threshold in the EMD invariant mass spectrum may be qualified as a nonresonant “soft” dipole excitation.

In light of the breakdown in the neutron p-shell closure in 12Be discussed previously, the importance of p-sd cross shell excitations in the 14Be ground state should be explored. In a first instance, the search for core excited states (12Be) in the dissociation of 14Be may provide indications for the presence of such configurations, whilst theoretically the inclusion of a deformed core Be12beta2 , in three-body calculations should be undertaken.

### Neutron–Neutron Correlations

One of the most intriguing questions regarding the description of two-neutron halo systems is the degree of correlation between the neutrons. Considering only the intrinsic momentum distributions, a spatially compact dineutron will be characterised by $`p_{core}=2p_n`$, whereas for a system with no correlations $`p_{core}=\sqrt{2}p_n`$. Unfortunately no unperturbed experimental measure of the momentum distributions is accessible.

Perhaps the method the most well adapted to probing spatial correlations is intensity interferometry Boa . In this approach the relative motion of the two outgoing neutrons is governed by the neutron–neutron final-state interaction and quantum statistics (Fermi-Dirac), both of which are related to the spatial characteristics of the source. Providing that any other effects on the neutron momenta may be neglected or eliminated in the construction of the correlation function, interferometry provides a means to probe the spatial correlations of the halo neutrons Mar99 .

Importantly, owing to the low momentum content of the halo neutrons, the standard approach to constructing correlation functions (applied, for example, in the measurement of Ieki et al. Sac93 ) is no longer valid Mar00 . In particular, the narrow momentum distributions result in strong residual correlations and consequently a significant overestimate of the source size. As a result a new iterative technique has recently been developed and applied to the dissociation on a Pb target of beams of 6He, 11Li and 14Be Mar99 . Assuming that the timescale between the emission of the two neutrons was short ($`\tau _{nn}`$100 fm/c), as is most probably the case for EMD, neutron-neutron RMS separations of 5.9$`\pm `$1.2 (6He), 6.6$`\pm `$1.5 (11Li), and 5.4$`\pm `$1.0 fm (14Be) have been deduced. These results appear to exclude the presence of any significant dineutron configurations. By way of comparison it is interesting to note that the RMS proton-neutron distance in the deuteron is some 3.8 fm. Future high statistics experiments emplying a well modelled system such as 6He should allow the emission timescale and source sizes to be extracted simultaneously from the longitudinal and transverse neutron-neutron relative momenta as well as coherent analyses of the neutron-neutron and core-neutron correlations.

## Conclusions

In this paper some of the facets of nuclear halo and molecular states in light nuclei have been reviewed. In particular, various illustrative examples provided by the neutron-rich beryllium isotopes have been discussed. In addition, a number of related experimental probes have also been presented. Clearly no single technique can furnish a complete description of these nuclei and it will require the application of a broad range of theoretical and experimental tools to obtain a better understanding of the phenomena outlined here.

It is a pleasure to thank my colleagues in the Groupe Exotiques at LPC and in the DEMON, CHARISSA and E264/281/295 collaborations who have contributed to the work described here.