text:
\section{Introduction}

The chromatic polynomial of a graph is probably the most famous graph
polynomial. In 1973 Stanley \cite{stanley73} gave an ``unorthodox''
interpretation of graph colorings in terms of acyclic orientations and
compatible maps. The benefit of this interpretation is a natural,
combinatorial interpretation of (suitably normalized) evaluations of the
chromatic polynomial at a negative argument. In some sense this was one of the
first \emph{combinatorial reciprocity theorems} \cite{stanley74}. In 2006,
Beck and Zaslavsky \cite{BZ06} gave a different perspective on this result by
casting it into the realms of geometry. They identified graph colorings as
lattice points ``inside'' a polytope but ``outside'' a hyperplane arrangement
--- an object answering to the name of \emph{inside-out polytope}. Thus, the
chromatic polynomial can be understood as a sum of Ehrhart functions and a
suitably generalized Ehrhart-Macdonald reciprocity yields the combinatorial
interpretation. We explain more of the details in the sections to come.

An equally important polynomial invariant of a graph is given by the
\emph{modular flow polynomial}. Let $G = (V,E)$ be an \emph{oriented graph}
and let $\Grp$ be an abelian group. An \emph{$\Grp$-flow} is an assignment $f :
E \rightarrow \Grp$ such that at every vertex we have a conservation of flow,
i.e.~
\[
    \sum_{uv \in E} f_{uv} - \sum_{vu \in E} f_{vu} = 0
\]
for every $v \in V$. The \emph{support} of the flow $f$ is $\supp(f) = \{ e
\in E : f_e \not= 0 \}$ and $f$ is called \emph{nowhere-zero} if $\supp(f) =
E$.  Tutte \cite{tutte47} was the first to consider nowhere-zero flows for a
fixed group $\Grp$.  He proved that the number of nowhere-zero $\Grp$-flows
only depends on the order of the group and that $\mFlow_G(k)$, the number of
nowhere-zero $\Zk$-flows, is a polynomial in $k$.  Clearly, this is only
meaningful for finite groups, but in the case of $\Z$-flows a natural
concept is that of a \emph{$k$-flow} which is a $\Z$-flow with values strictly
smaller than $k$ in absolute values. Tutte \cite{tutte54} proved that there is
a nowhere-zero $\Z_k$-flow if and only if there is a nowhere-zero $k$-flow.
However, the number of nowhere-zero $k$-flows and $\Z_k$-flows differ in
general.

In 2002 Kochol \cite{kochol02} proved that $\iFlow_G(k)$, the number of
nowhere-zero $k$-flows, is also a polynomial and in \cite{BZ06-2} Beck and
Zaslavsky showed that this is yet another incarnation of Ehrhart theory of
inside-out polytopes. Moreover, this approach yields a reciprocity statement
that parallels that for the chromatic polynomial: $(-1)^{\xi(G)}\iFlow_G(-k)$
counts pairs of $k$-flows and compatible totally cyclic orientations. This
raised the question for a combinatorial reciprocity theorem of the modular
flow polynomial (cf.~\cite[Problem 3.2]{BZ06-2}).

As an answer to this question, the first result of this paper gives an
interpretation of $(-1)^{\xi(G)}\mFlow_G(-k)$ as naturally counting pairs of
$\Zk$-flows and totally cyclic reorientations on certain subgraphs. We give
the precise statement in Section~\ref{sec:Flows}. A little surprisingly, our
proof is somewhat simpler than the one for $k$-flows in \cite{BZ06-2}. For
starters, we do not need the theory of inside-out polytopes \emph{per se}; in
Section \ref{sec:FlowsInsideOut} we relate our proof to inside-out polytopes
which sheds ``geometric light'' on some well-known properties of flow
polynomials. In Section~\ref{sec:Tensions}, we discuss colorings and their
relations to $\Z_k$-tensions. We sketch how analogous arguments yield a
reciprocity statement for $\Z_k$-tensions that corresponds to Stanley's
reciprocity for
colorings \cite{stanley73}.  In Section~\ref{sec:TutteInterpretation} we make
use of the reciprocity statements to prove a enumerative interpretation for
arbitrary evaluations of Tutte polynomials of graphs at positive arguments,
which is implicit in the work of Reiner~\cite{reiner99}.  In the appendices we
give traditional, that is deletion-contraction, proofs for the main results of
Section~\ref{sec:Flows} and \ref{sec:TutteInterpretation}.

{\bf Acknowledgments.} We would like to thank Matthias Beck for valuable
conversations and comments on an earlier version of this paper.

\section{Modular flow reciprocity}
\label{sec:Flows}

Let $G = (V,E)$ be an \emph{oriented graph}, that is, an unoriented graph
equipped with an orientation of its edges.  We allow, even encourage, $G$ to
have multiple edges and loops. For an $S \subseteq E$ we denote by
$G_{\setminus S}$, $G_{/ S},$ and $G[S]$ the result of \emph{deleting},
\emph{contracting}, and \emph{restricting} to $S$, respectively.  Moreover, we
denote by $_SG$ the \emph{reorientation} of $G$ along $S$, i.e.~the graph
obtained by reversing the orientation of the edges in $S$. We denote by $c(G)$
the number of (weakly) connected components and we call $e \in E$ a
\emph{coloop} or \emph{bridge} if $c(G_{\setminus e}) = c(G) + 1$.  Finally,
we denote by $\xi(G) := |E| - |V| + c(G)$ the \emph{cyclotomic number} of $G$.

Let us give a precise definition for the main character.
\begin{dfn} For an oriented graph $G = (V,E)$,  the \emph{modular flow
    polynomial} $\mFlow_G$ of $G$ is the function
    \[
        \mFlow_G(k) = \# \left\{ f : E \rightarrow \Zk : f \text{ nowhere-zero
        $\Zk$-flow} \right\}.
    \]
\end{dfn}

The name was justified by Tutte \cite{tutte54} who showed that $\mFlow_G$ is
indeed a polynomial of degree $\xi(G)$.  In particular, $\mFlow_G$ can be
extended to negative arguments. In order to state our main result of this
section we need the notion of a totally cyclic orientation. An oriented graph
is called \emph{totally cyclic} if every edge is contained in a directed cycle
and $\s \subseteq E$ is a \emph{totally cyclic reorientation} if $_\s G$ is
totally cyclic.

\begin{thm}[Modular flow reciprocity]\label{thm:MainFlow}
    Let $G = (V,E)$ be an oriented graph and let $k$ be a positive integer.
    Then $(-1)^{\xi(G)}\mFlow_G(-k)$ counts pairs $(f,\s)$ where $f$ is a
    $\Zk$-flow and $\s \subseteq E \setminus \supp(f)$ is a totally cyclic
    reorientation for $G_{/ \supp(f)}$.
\end{thm}

Let us remark, that our result differs from the reciprocity theorem for
$k$-flows (cf.~\cite[Thm~3.1b]{BZ06-2}) inasmuch, that the flow and the
reorientation are not subject to a compatibility constraint. Rather, we reorient
at most those edges $e$ with $f(e)=0$ in the first place and contract all other
edges.

Let us illustrate the result with two examples that will accompany us
throughout.
\begin{Ex1}
    Consider the following graph $G_1$ with two vertices and three parallel
    and identically oriented edges $e_1,e_2,e_3$.
    \begin{center}
        \begin{overpic}[width=3cm]{figs/3parallel}
            \put(45,8){\scriptsize$e_1$}
            \put(45,28){\scriptsize$e_2$}
            \put(45,48){\scriptsize$e_3$}
        \end{overpic}
    \end{center}
    The flow conservation for a flow $f$ is given by $f(e_1) + f(e_2) + f(e_3)
    = 0$ and this readily yields the number of nowhere-zero $\Zk$-flows as
    $\mFlow_{G_1}(k) = (k-1)(k-2)$.  The cyclotomic number of $G_1$ is
    $\xi(G_1) = 2$ and hence $(-1)^2\mFlow_{G_1}(-k) = (k+1)(k+2)$.  Now let
    us count the number of pairs $(f,\s)$ stated in Theorem~\ref{thm:MainFlow}
    according to $n_f = |\supp(f)|$. For $n_f = 0$, $f$ is the unique
    zero-flow and the number of totally cyclic orientations is $6$. The case
    $n_f = 1$ does not show up and for $n_f = 2$ there are exactly
    $\tbinom{3}{2}$ choices of non-zero edges and $(k-1)$ flows each time. The
    contraction in each case yields a loop which has two totally cyclic
    reorientations. Together with $n_f = 3$, in which case we count the number
    of nowhere-zero $\Zk$-flows, we get
    $
        (k-1)(k-2) + 6 (k-1) + 6 = (k+1)(k+2).
    $
    \hfill $\exampleEnd$
\end{Ex1}

\begin{Ex2}
    Our second example is the multigraph $G_2$:
    \begin{center}
        \begin{overpic}[width=3cm]{figs/triangle+2}
            \put(17,57){$a$}
            \put(62,57){$b$}
            \put(85,57){$b^\prime$}
            \put(42,22){$c$}
            \put(42,3){$c^\prime$}
        \end{overpic}
    \end{center}
    In order to compute the flow polynomial, consider the case of a $3$-cycle
    $a,b,c$ without parallel edges. It is clear that the flow is determined by
    the (non-zero) value on the edge $a$ and the flow polynomial is thus
    $k-1$. Now every nowhere-zero flow on the $3$-cycle yields $(k-2)^2$
    nowhere-zero flows on $G_2$ since flow on $b$ and $c$ can be ``rerouted''
    through $b^\prime$ and $c^\prime$ as long as all remain nonzero. Hence,
    $\mFlow_{G_2}(k) = (k-1)(k-2)^2$ and $(-1)^{\xi(G_2)}\mFlow_{G_2}(-k) =
    (k+1)(k+2)^2$ with $\xi(G_2) = 3$.  The argument extends to counting the
    pairs $(f,\s)$ combinatorially, by lifting the pairs from the $3$-cycle.
    \hfill $\exampleEnd$
\end{Ex2}

We will now set the stage for the proof of Theorem~\ref{thm:MainFlow} which
will mainly consist of casting the statement of Theorem~\ref{thm:MainFlow}
into a discrete geometric statement involving lattice polytopes. As a first
step we will identify $\Zk$ with a set of coset representatives given by the
integers $0,1,\dots,k-1$. With this identification the flow conservation at a
vertex $v \in V$ can be rephrased as
\begin{equation*}
\begin{aligned}
    \sum_{uv \in E} f_{uv} &\;-\; \sum_{vu \in E} f_{vu} \ = \ 0 & \text{ over
    $\Zk$}\\
    \Leftrightarrow \sum_{uv \in E} f_{uv} &\;-\; \sum_{vu \in E} f_{vu} \
    \equiv \ 0 & \text{ mod $k$ }\\
    \Leftrightarrow \sum_{uv \in E} f_{uv} &\;-\; \sum_{vu \in E} f_{vu} \
    = \ k \cdot b_v & \text{ for some  } b_v \in \Z.\\
\end{aligned}
\end{equation*}

Letting $A = A_G \in \{0,\pm1\}^{V \times E}$ be the \emph{incidence matrix}
of $G$, the last equivalence yields the following polyhedral reformulation: A
point $f \in \Z^E$ represents a nowhere-zero $\Zk$-flow if there is a $b \in
\Z^V$ such that $f$ is contained in $(k\cdot P^\circ_G(b)) \cap \Z^E$ where
\[
    P^\circ_G(b) := \{ p \in \R^E : Ap = b, 0 < p_e < 1 \text{
    for all } e \in E \}.
\]
Note that for such a $b$, $P^\circ_G(b)$ is a relatively open polytope of
dimension $\dim \Pbo = \rk A_G = \xi(G)$. Denote by $\B_G = \{ b \in \Z^V :
\Pbo \not= \emptyset \}$ the collection of all \emph{feasible} $b$'s. The set
$\B_G$ is clearly finite (since the cube is compact) and for distinct $b,
b^\prime \in \B_G$, the relatively open polytopes $\Pbo$ and $\Po{b^\prime}$ are necessarily
disjoint. The incidence matrix $\A_G$ of an oriented graph is \emph{totally
unimodular} (cf.,~for example, \cite[Sec.~19.3,Ex 2]{schr86}). This remains true
if we add rows that contain just a single $1$ to encode constraints like
$0\leq p_e\leq 1$. Standard methods (cf.  \cite[Thm.~19.1]{schr86}) then imply
that the closure $\Pb = \overline{\Pbo}$ is a vertex induced subpolytope of
the $|E|$-dimensional standard cube and, in particular, a \emph{lattice}
polytope.

\begin{Ex1}[continued]
The edge space of $G_1$ is three dimensional. The incidence matrix of $G_1$ is
\[
    A = A_{G_1} =
    \left(\begin{array}{rrr} -1 & -1 & -1 \\ 1 & 1 & 1 \end{array}\right)
\]
It follows that $P^\circ_{G_1}(b) = \{ x \in \R^3 : 0 < x_1,x_2,x_3 < 1,
x_1+x_2+x_3 = -b_1, x_1 + x_2 + x_3 = b_2 \}$ is non-empty iff $b^\prime = (-1,1)$ or
$b^{\prime\prime} = (-2,2)$. The following figure shows the two polytopes as
slices of the cube. The points correspond to the $6$ nowhere-zero
$\Z_4$-flows.
\begin{center}
    \hfill\includegraphics[width=7cm]{figs/example1}
     \hfill $\exampleEnd$
\end{center}
\end{Ex1}

For a polytope $P \subset \R^d$ the function $\ehr(P;k) := (k \cdot P) \cap
\Z^d$ is called the \emph{Ehrhart function} of $P$. Ehrhart \cite{ehr77}
showed that $\ehr(P;k)$ is a polynomial of degree $\dim P$ in case $P$ is a
lattice polytope.

\begin{prop}\label{prop:EhrFlow}
    Let $G = (V,E)$ be an oriented graph. Then
    \[
        \mFlow_G(k) = \sum_{b \in \B_G} \ehr(\Pbo;k)
    \]
    is a sum of Ehrhart polynomials.\qed
\end{prop}

Probably the most appealing feature of Ehrhart theory is that Ehrhart
polynomials adhere to a beautiful geometric reciprocity (for details
see e.g.~\cite[Sect.~4]{BR07}).

\begin{thm}[Ehrhart--Macdonald reciprocity] \label{thm:EM}
    Let $P$ be a rational polytope and denote by $P^\circ$ the (relative) interior of
    $P$. Then
    \[
        \ehr(P^\circ;k) = (-1)^{\dim P} \ehr(P;-k).
    \]
\end{thm}

In light of Proposition~\ref{prop:EhrFlow} together with  Ehrhart-Macdonald
reciprocity it is sufficient to give a combinatorial meaning to the lattice
points in the boundary of $k \cdot \Pb$. Fix a $b \in \B_G$ and let $F \subset
\Pb$ be a proper face. As $\Pb$ is a section of the $|E|$-cube, there is a
partition $\s_- \cup \s_0 \cup \s_+ = E$ into disjoint parts such that the
relative interior of $F$ is given by all the points $p \in \Pb$ such that
\[
    \begin{array}{cccccl}
        0 &=& p_e & &   & \text{ for } e \in \s_-,\\
        0 &<& p_e &<& 1 & \text{ for } e \in \s_0, \text{ and }\\
          & & p_e &=& 1 & \text{ for } e \in \s_+.\\
    \end{array}
\]
A lattice point $f$ in the relative interior of $k \cdot F$ represents a
$\Zk$-flow but, since $0 \equiv k\; \mathsf{mod}\, k$, this representation is
not unique.  However, if $f^\prime \in (k \cdot \P{b^\prime}) \cap \Z^E$ for
some $b^\prime \in \B_G$ yields the same $\Zk$-flow modulo $k$ but is
different from $f$ otherwise, then $f^\prime \in \relint(k \cdot F^\prime)$
for a proper face $F^\prime \subset P_G(b^\prime)$ and $F \not= F^\prime$.
Thus, the idea is to keep track of the \emph{origin} of $f$. This leads to
reorientations on the contraction.

To this end, let $z_F$ and $z_P$ be points in the relative interiors of $F$
and $\Pb$ respectively and consider $z := z_P - z_F$. Then $z \in \ker A_G$
and we can predict the sign of $z_e$ for $e \in \s_- \cup \s_+$.  The next
lemma relates the kernel of $A_G$ to totally cyclic reorientations of $G$.

\begin{lem}[{\cite[Lem.~8.1]{GZ83}}] \label{lem:TotCyc}
    Let $G = (V,E)$ be a graph and $A = A_G$ its incidence matrix. The
    connected components of $ \ker A \setminus \{ p \in \R^E : p_e = 0 \text{
    for some } e \in E \}$ are in bijection with the totally cyclic
    reorientations of $G$. The totally cyclic reorientation $\s$ associated to
    a connected component is $\s = \{ e \in E : p_e < 0 \}$ for an arbitrary
    point $p$ in that component.
\end{lem}

The restriction $\tilde{z}$ of $z$ to $\s_+ \cup \s_-$ is an element of $\ker
A_{G / \s_0}$ and Lemma~\ref{lem:TotCyc} then asserts that $\s_+$ is a totally
cyclic reorientation for $G_{/\s_0}$ and uniquely identifies the face $F$ for
which $z_F \in \relint\,F$.

\begin{proof}[Proof of Theorem~\ref{thm:MainFlow}]
    Let $f \in k \cdot [0,1]^E \cap \Z^E$ be a lattice point in the $k$-th
    dilate of the $|E|$-dimensional standard cube. Let $\s(f) = \{ e \in E :
    f_e = k \}$ and denote by $\fb$ the point $f$ modulo $k$ componentwise.

    By our discussion and, in particular, Ehrhart-Macdonald reciprocity we
    have that
    \[
    (-1)^{\xi(G)}\mFlow_G(-k) = \left| \bigcup_{b \in \B_G} (k \cdot \Pb) \cap
    \Z^E \right|
    \]
    where the union on the right-hand side is over disjoint sets. The
    theorem follows by proving that $f \mapsto (\fb,\s(f))$ is a bijection
    between points in the right-hand side and pairs of $\Zk$-flows and totally
    cyclic orientations on the contraction of the support. However, by our
    previous reasoning it is clear that this is a well-defined map and we are
    left with showing that there exists an inverse mapping.

    Let $(\fb,\s)$ be a pair with $\fb : E \rightarrow \Zk$ a $\Zk$-flow and
    $\s \subseteq E \setminus \supp(\fb)$ a totally cyclic reorientation of
    $G_{/ \supp(\fb)}$. Let $f^\prime \in k \cdot [0,1]^E \cap \Z^E$ be the
    unique point with $f^\prime_e = k$ iff $e \in \s$ and $\overline{f^\prime}
    = \fb$. The point $f^\prime$ is in the boundary of $\Pb$ for $b =
    Af^\prime$ and we are done if we can show that $b \in \B_G$. Now, by
    Lemma~\ref{lem:TotCyc}, we can pick a vector $z \in \R^E$ with $Az = \0$,
    $z_e < 0$ for $e \in \sigma$ and $z_e > 0$ for $e \not\in \supp(\fb) \cup
    \s$.  Thus, for $\varepsilon > 0$ sufficiently small, $f^\prime +
    \varepsilon z$ is a point of $\Pb$ in the interior of the cube and this
    concludes the argument.
\end{proof}

As an immediate Corollary we get the following known enumerative result.

\begin{cor}[{\cite[Cor.~1.3]{stanley73}}]
    Let $G = (V,E)$ be an oriented graph. Then $(-1)^{\xi(G)}\mFlow_G(-1)$ is
    the number of totally cyclic reorientations of $G$.
\end{cor}

In particular, every totally cyclic reorientation belongs to exactly one
$\Pb$. It is worthwhile interpreting this partition of totally cyclic
reorientations as an equivalence relation.  The following proposition phrases
the equivalence in combinatorial terms.  For a set $\sigma \subseteq E$ we
denote by $e_\sigma \in \{0,1\}^E$ the characteristic vector of $\sigma$.

\begin{prop}
    Let $G = (V,E)$ be an oriented graph and $\sigma, \sigma^\prime \subseteq
    E$ two totally cyclic reorientations.  The points $e_\sigma,
    e_{\sigma^\prime} \in \{0,1\}^E$ are both vertices of $\Pb$ for some $b
    \in\B_G$ if and only if $_\sigma G$ can be obtained from $_{\sigma^\prime}
    G$ by the reversal of directed cycles.
\end{prop}
\begin{proof}
    The points $e_\sigma, e_{\sigma^\prime} \in \{0,1\}^E$ are both contained
    in a common $\Pb$ iff $z := e_\sigma - e_{\sigma^\prime}$ is an element of
    $\ker A_G$. By \cite[Lem.~8.5]{GZ83}, $z$ is a linear combination with
    non-negative coefficients of orientations of cycles of $G$.
\end{proof}

For an oriented graph $G = (V,E)$, we denote by $I_G \in \Z^V$ the
\emph{in-degree sequence}, that is the number $(I_G)_v$ of incoming edges for
every vertex $v \in V$. Similar, we define the \emph{out-degree sequence} $O_G
\in \Z^V$ of~$G$.

\begin{thm}
    Let $G = (V,E)$ be an oriented graph. Then $\B_G$ is in bijection with
    \[
        \{ I_{_\sigma G} : \sigma \subseteq E \text{ totally cyclic
        reorientation} \}.
    \]
\end{thm}

\begin{proof}
    Let $A_G$ be the incidence matrix of $G$. It is clear that we can recover
    $I_G$ from the knowledge of the (undirected) degree sequence $D = I_G +
    O_G$ and $I_G - O_G = A_G \1 =: b_0$. Now, for any reorientation $\sigma
    \subseteq E$, we have
    \[
        I_{_\sigma G} - O_{_\sigma G} = A_{_\sigma G} \1 = A_G (\1 - 2
        e_\sigma) = b_0 - 2A_G e_\sigma.
    \]
    Hence, the in-degree sequence of $_\sigma G$ is uniquely determined by
    $b_\sigma = A_G e_\sigma$.  Moreover, the reversal of a directed cycle in
    $G$ leaves the in- and out-degree sequences invariant and thus is
    invariant within $\Pb$. Using that $\B_G = \{ b = A_G e_\sigma : \sigma
    \subseteq E \text{ totally cyclic reorientation } \}$ finishes the proof.
\end{proof}

Dilating a lattice polytope by a factor $0$ yields a lattice point and it can
be shown that indeed the Ehrhart polynomial has constant term equal to $1$.
As $\mFlow_G$ is the sum of the (open) Ehrhart polynomials for $\Pbo$, we
recover the following result by Gioan~\cite{gioan07}.

\begin{cor}[{\cite[Thm.~3.1]{gioan07}}]
    Let $G = (V,E)$ be an oriented graph and $t_G(x,y)$ its Tutte polynomial.
    Then
    \[
    t_G(0,1) = (-1)^{\xi(G)} \mFlow_G(0) = \sum_{b \in \B_G} \ehr(\Pb;0) =
    |\B_G|
    \]
     is the number of in-degree sequences of
    totally cyclic reorientations of $G$.
\end{cor}

The evaluation $t_G(0,1)$ has several known interpretations as, for example, the number of spanning trees with zero external activity,
the Euler characteristic of the independence complex of the matroid $M_G$
associated to $G$, or the number of facets of the broken circuit complex of
the dual matroid $M_G^\perp$. We refer the reader to the survey article by
Brylawski and Oxley \cite{BO92} for further details.

\section{Modular flows inside-out}
\label{sec:FlowsInsideOut}

In this section we relate our previous construction to inside-out
polytopes. The benefit in doing so will be a simple geometric explanation for
the following fact.

\begin{cor}
    The modular flow polynomial of an oriented graph $G$ has degree $\xi(G)$
    and leading coefficient $1$.
\end{cor}

This, in turn, is a consequence of the fact that the number of modular
$\Zk$-flows is a \emph{generalized Tutte--Grothendieck invariant}
(cf.\ Section~\ref{sec:TutteInterpretation}) and, hence, obeys the following
deletion-contraction property.

\begin{prop}[{\cite[Prop.~6.3.4]{BO92}}] \label{prop:FlowRecursion}
    Let $G = (V,E)$ be an oriented graph and $e \in E$ an edge. If $e$ is
    neither a loop nor a coloop, then
    \[
    \mFlow_G(k) = \mFlow_{G_{/e}}(k) - \mFlow_{G_{\setminus e}}(k).
    \]
    Otherwise, $\mFlow_G(k) = (k-1)\mFlow_{G_{\setminus e}}(k)$ if $e$ is a loop
    and $\mFlow_{G}(k) = 0$ if $e$ is a coloop.
\end{prop}

While the degree of the polynomial is clear from our interpretation in terms
of Ehrhart polynomial, the fact that the leading coefficient is $1$ is not.

\begin{prop}[{\cite[Cor.~3.20]{BR07}}]
    Let $P$ be a $d$-dimensional lattice polytope then the leading coefficient
    of $\ehr(P;k)$ is the volume $\vol(P)$ of $P$.
\end{prop}

So, the best we can say so far is that
\[
    1 = \sum_{b \in \B_G} \vol(\Pb).
\]
However, the answer we are aiming at is that suitably arranging the polytopes
$\Pb$ yields a subdivision of a standard cube of dimension $\xi(G)$. Thus, the
total volume of the $\Pb$'s is that of the standard cube.

In particular, the subdivision of the cube is induced by an arrangement of
hyperplanes and therefore directly leads to inside-out polytopes.  For our
needs a \emph{(lattice) inside-out polytope} is a pair $(P,\H)$ consisting of
a $d$-dimensional lattice polytope $P \subset \R^d$ and a hyperplane
arrangement $\H = \{H_1,\dots,H_m\}$ such that any flat that meets $P$ also
meets the interior of $P$.  The hyperplane arrangement is allowed to be
infinite as long as only finitely many hyperplanes meet $P$.  The \emph{open
Ehrhart function} of $(P,\H)$ is the function $\ehr(P^\circ,\H;k) = | k
\cdot(P^\circ \setminus \cup\H)  \cap \Z^d |$. In the case of a lattice
inside-out polytope, i.e. $\H$ subdivides $P$ into lattice polytopes, the open
(as well as the closed) Ehrhart function is a polynomial of degree $d$ and
leading coefficient $\vol(P)$.

Let $G = (V,E)$ be an oriented graph and let $T \subseteq E$ be a spanning
forest, i.e.,~a spanning tree per component.  Let $\Tc = E \setminus T$ denote
the edges not in the forest. We will use $T$ to construct a cycle basis,
i.e.,~a basis for $\ker \A_G$, combinatorially. Let $\oA \in \{0,\pm1\}^{ \Tc
\times E}$ be the matrix with rows $\oA_{f\bull}$ for $f \in \Tc$ defined as
follows: The support of $\oA_{f\bull}$ is given by the edges in the unique
undirected cycle $K$ in $G[T \cup f]$. There is a unique reorientation of $K$
that makes it an oriented cycle and that fixes the orientation on $f$. The
signs keep track of which edges have to be reoriented.  It is known
(e.g.~\cite[Thm.~11.1]{Schri03}) that every flow is an integral linear
combination of the $C_{f\bull}$.  This implies that every nowhere-zero
$\Zk$-flow corresponds to a unique point $h \in \Z^{\Tc}$ with $0 < h_f < k$
for $f \in \Tc$ and $(h\oA)_e \not\equiv 0 \mod k$ for all $e \in T$. Denote
by $\oA_{\bull e}$ the columns of $\oA$ for $e \in T$, then this yields the
following interpretation in terms of inside-out polytopes.

\begin{prop}
    Let $P = [0,1]^{\Tc}$ be the standard cube in $\R^{\Tc}$ and let $\H$ be
    the arrangement of hyperplanes $H_{e,d_e} = \{ q \in \R^{\Tc} :
    \oA_{\bull e}^T\,  q  = d_e \}$ for $e \in T$ and $d_e \in \Z$. Then
    \[
        \mFlow_G(k) = \ehr(P^\circ,\H;k).
    \]
\end{prop}

In some sense the above construction is dual to that presented in
Section~\ref{sec:Flows}: whereas the linear conditions in the construction of
Section~\ref{sec:Flows} forced the points to be $\Zk$-flows, the construction
here satisfies that automatically, and violating the linear conditions enforces
the nowhere-zero condition. This is an instance of oriented matroid duality
of the hyperplane arrangement $\H$.

\begin{Ex1}[continued]
    For the choice of the spanning tree $T = \{e_1\}$, the cycle basis is
    \begin{align*}
        &\hphantom{\Bigl(}\begin{array}{rrr} \scriptstyle e_1 & \scriptstyle
            e_2 & \scriptstyle e_3 \end{array}\\
        \oA =
        \begin{array}{rr}
            \scriptstyle e_2 \\
            \scriptstyle e_2 \\
        \end{array}
        &
        \Bigl(\!
        \begin{array}{rrr} -1 & 1 & 0 \\ -1 & 0 & 1 \end{array}\!\Bigr).
    \end{align*}
    The polytope $P$ is a $2$-cube and the hyperplane
    arrangement $\H$ is given by $H_{e_1,d} = \{ (q_1,q_2) \in \R^{\Tc} : q_1 +
    q_2 = -d \}$ for $d \in \Z$. The resulting inside-out polytope is the
    following.
    \begin{center}
        \includegraphics[width=4cm]{figs/example1a}
    \end{center}
     \hfill $\exampleEnd$
\end{Ex1}

\begin{Ex2}[continued]
    For $G_2$ we pick the spanning tree $T = \{a,b\}$ and, hence, the cycle
    basis
    \begin{align*}
        &\hphantom{\Bigl(}\begin{array}{rrrrr}
            \scriptstyle a &
            \hspace{1em}\scriptstyle b &
            \hspace{.3em}\scriptstyle b^\prime &
            \scriptstyle c &
            \scriptstyle c^\prime
        \end{array}\\
        \oA =
        \begin{array}{l}
            \scriptstyle b^\prime \\
            \scriptstyle c\\
            \scriptstyle c^\prime\\
        \end{array}\!\!
        &
        \Biggl(\!
        \begin{array}{rrrrr}
            & -1  & 1 &   &   \\
          1 &  1&   & 1 &   \\
          1 &  1&   &   & 1 \\
        \end{array}\!\Biggr).
    \end{align*}
    So the two parallel classes of hyperplanes correspond to $H_{a,d_a} = \{
    (b^\prime,c,c^\prime) \in \R^{\Tc} : c + c^\prime = d_a \}$ and
    $H_{b,d_b} = \{ (b^\prime,c,c^\prime) \in \R^{\Tc} : -b^\prime + c +
    c^\prime = d_b \}$. The resulting inside-out polytope is:
    \begin{center}
        \includegraphics[width=8cm]{figs/example0}
    \end{center}
    The four chambers correspond to the feasible $b$'s.
     \hfill $\exampleEnd$
\end{Ex2}

So the leading coefficient of $\mFlow_G$ refers to the volume of a
$\xi(G)$-dimensional standard cube $P = [0,1]^{\Tc}$.  The chambers,
i.e.,~connected components of $P^\circ \setminus \cup\H$ are in bijection with
$\B_G$. Indeed, every chamber is isomorphic to a unique $\Pbo$ under the
restriction to the coordinates $\Tc$.  With some more work it is possible to
see the reciprocity in this picture and, via toric arrangements, this line of
thought has been pursued by Babson and Beck \cite{BB09}. One point worth
mentioning is that the deletion-contraction property of the flow polynomial
can be nicely observed in terms of the freedom of choice for a spanning
forest.  The contraction of an edge $e$ simply removes the family of
hyperplanes $H_{e,d_e}$ from the arrangement. The resulting over count can be
compensated for by subtracting the number of lattice points in the inside-out
polytope obtained by restricting to this family. However, choosing a spanning
forest not containing $e$ yields an inside-out polytope where the family
$H_{e,d_e}$ corresponds to two parallel facets of the cube and restricting
yields the inside-out polytope for $G_{\setminus e}$.

\section{Modular tensions and Stanley's Reciprocity Theorem}
\label{sec:Tensions}

In the introduction we mentioned Stanley's reciprocity theorem for the
chromatic polynomial $\chi_G$ of a graph $G=(V,E)$. It turns out that this
reciprocity is best observed in the related setting of modular tensions. In
this section we sketch the changes to our previous constructions in order to
accommodate modular tensions and we formulate a reciprocity theorem.

An \defn{$\l$-coloring} is a map $c: V \rar \{0,\ldots,\l-1\}$. An
$\l$-coloring $c$ is called \defn{proper} if $c(u)\not=c(v)$ whenever $u$ and
$v$ are adjacent in $G$ and  the chromatic polynomial $\chi_G(\l)$ counts the
number of proper $\l$-colorings of $G$. A reorientation $\s$ of $G$ is
\defn{acyclic} if no edge of $G$ lies on a directed cycle. A coloring $c$ and
an acyclic reorientation $\s$ are \defn{compatible} if for every edge $uv$ of
$_\s G$ we have $c(u)\leq c(v)$.

\begin{thm}[Stanley \cite{stanley73}]\label{thm:StanleyReciprocity}
    For an oriented graph $G=(V,E)$ and $\l > 0$ an integer,
    $(-1)^{|V|}\chi_G(-\l)$ is the number of tuples $(c,\s)$ where $c$ is an
    $\l$-coloring and $\s \subseteq E $ is a compatible acyclic reorientation.
\end{thm}

The idea that leads to the notion of tensions is the following. Let us suppose
for a moment that $G$ is connected. Then we can recover the coloring $c$ by
knowing the \emph{initial} color $c_0 = c(v_0)$ of some vertex $v_0$ and the
difference of the colors $t(uv) := c(u) - c(v)$ on each (oriented) edge $uv$.
Of course, we now make use of the fact that our set of colors is embedded in
a group.  Thus, we recover the color on a vertex $w$ by adding and
subtracting the tensions $t(e)$ of edges along a path from $v_0$ to $w$.
Note that the color of $c(w)$ is independent of the chosen path and we take
this as the defining property of tensions.

For a cycle $C \subseteq E$ in the underlying undirected graph, we denote by
$C_- \subset C$ a collection of edges whose reorientation turns $C$ into a
directed cycle and we let $C_+ := C \setminus C_-$ be the remaining edges.
Let $\Grp$ be an abelian group. A map $t : E \rar \Grp$ is called an
\emph{$\Grp$-tension} if
\[
    \langle C, t \rangle := \sum_{e \in C_+} t(e) - \sum_{e \in C_-} t(e) = 0
\]
for each undirected cycle $C \subseteq E$. Note that this is independent of
the choice of $C_-$.  An induced coloring $c$ is proper if and only if $t$ is
\emph{nowhere-zero}, that is $\supp(t) := \{ e \in E : t(e) \not= 0 \} = E$.
It can be shown that, as in the case of flows, the number of nowhere-zero
$\Grp$-tensions depends only on the order of $\Grp$ and we define
$\mTen_G(\l)$ to be the number of nowhere-zero $\Zl$-tensions of $G$.

Every nowhere-zero $\Zl$-tension $t$ yields $|\Zl|^{c(G)}$ different colorings
by choosing an initial color for every component and this proves the following
known fact that $\chi_G(\l)=\l^{c(G)} \mTen_G(\l)$, i.e.\ the tension
polynomial is a non-trivial factor of the chromatic polynomial.  Hence, we
arrive at the following equivalent reformulation of
Theorem~\ref{thm:StanleyReciprocity} which is already implicit in Stanley's
work.

\begin{thm}\label{thm:TensionReciprocity}
    Let $G=(V,E)$ be an oriented graph.
    Then $(-1)^{|V|-c(G)}\mTen_G(-\l)$ counts pairs $(t,\s)$ where $t$ is
    a $\Zl$-tension on $G$ and $\s$ is an acyclic reorientation of
    $G_{\backslash\supp(t)}$.
\end{thm}

\begin{proof}[Equivalence of Theorems~\ref{thm:StanleyReciprocity} and \ref{thm:TensionReciprocity}]
In light of the fact that $\chi_G(\l)=\l^{c(G)} \mTen_G(\l)$ it suffices to
argue that for a given $k$-coloring $c$ and a corresponding $\Zk$-tension $t$,
the acyclic reorientations of $G_{\setminus\supp(t)}$ are in bijection with
the acyclic reorientations of $G$ that are compatible with $c$. If $\s$ is an
acyclic reorientation of $G$ then clearly $\s\cap E\setminus \supp(t)$ is an
acyclic reorientation of $G_{\setminus\supp(t)}$. Conversely, let $\s'$ be an
acyclic reorientation  of $G_{\setminus\supp(t)}$. We have to show that there
is a unique extension of $\s'$ to an acyclic reorientation $\s$ of $G$ that is
compatible with $c$. However, the condition that $e=uv$ has to be oriented
from $u$ to $v$ whenever $c(u)<c(v)$ fixes the reorientation of all edges in
$\supp(t)$. Suppose the resulting reorientation $\s$ did contain a directed
cycle $C$. Then all vertices on $C$ have to have the same color with respect
to $c$, as following an edge can never decrease the color. But this means that
$C\subseteq E\setminus\supp(t)$ which is a contradiction to
$_{\s'}G_{\setminus\supp(t)}$ being acyclic.
\end{proof}

Note the similarity to the statement of Theorem~\ref{thm:MainFlow}. This
is not at all surprising from the (oriented) matroid point of view as
we have the following correspondences:
\begin{center}
\begin{tabular}{r@{$\;\;\leftrightarrow\;\;$}l}
    flow $f$ & tension $t$ \\
    $\xi(G)$ & $|V| - c(G)$\\
    totally cyclic & acyclic\\
    $G_{/\supp(f)}$ & $G_{\backslash \supp(t)}$ \\
\end{tabular}
\end{center}

Let us quickly remark on the conception of a ``tension''. If $\Grp$ is an
ordered group, such as $\Z$, then the elements in $\Grp$ can be thought of
heights and a tension measures the difference in altitude along an edge. In
particular, if we reorient $G$ such that $t(e) > 0$ for all $e$, then it is
clear that every nowhere-zero $\Z$-tension yields an acyclic reorientation.

We refrain from giving a proof of Theorem~\ref{thm:TensionReciprocity} but
instead supply the necessary modifications to the proofs for flow reciprocity
in Sections~\ref{sec:Flows} and \ref{sec:FlowsInsideOut}.

For an arbitrary spanning tree $T$, let $C$ be the cycle basis constructed in
Section~\ref{sec:FlowsInsideOut}. It suffices to verify the defining
properties of tensions on such a cycle basis as every cycle is a
superposition of these elementary cycles. Thus, identifying $\Zl = \{ 0,\dots,
\l-1\}$, we have that $t : E \rar \Z$ represents a nowhere-zero $\Zl$-tension if
$0 < t(e) < \l$ for every $e \in E$ and there is a $d \in \Z^{\Tc}$ such that
$Ct = \l \cdot d$. Analogously to the flow case, this formulation furnishes a
collection of relatively open disjoint polytopes whose Ehrhart polynomials
yield the nowhere-zero tension polynomial.

For the reciprocity the key lemma that yields the interpretation in terms of
acyclic reorientations is

\begin{lem}[{\cite[Lem.~7.1]{GZ83}}]
    Let $G = (V,E)$ be an oriented graph and $C$ a cycle basis.
    Then the connected components of $\ker C \setminus \{ p \in \R^{E} : p_e =
    0 \text{ for some } e \in E \}$ are in bijection with the acyclic
    reorientations of $G$.
\end{lem}

Tensions can be parametrized by the edges in a spanning forest, leaving it to
the non-forest edges $\Tc$ to compensate along each cycle in the cycle basis
$C$. This yields the description of an inside-out polytope analogous to the
flow case in Section~\ref{sec:FlowsInsideOut}.

\section{An interpretation of the Tutte polynomial}
\label{sec:TutteInterpretation}

An (integral) \emph{generalized Tutte--Grothendieck (T-G) invariant} is an
assignment $f_G \in \Z$ to every graph $G$ such that for some constants
$\tau_f, \sigma_f \in \Z$
\begin{enumerate}
    \item $f_G = \sigma_f f_{G_{\setminus e}} + \tau_f f_{G_{/ e}}$ for every
        $e \in E$ that is neither a loop nor a coloop, and
    \item $f_G = f_{G[e]} \cdot f_{G_{\setminus e}}$ otherwise.
\end{enumerate}

A large collection of important invariants for graphs (or more generally
matroids) qualifies as Tutte--Grothendieck invariants (cf.~\cite{BO92}), among
them all evaluations of chromatic and modular flow and tension polynomials.
The \emph{Tutte polynomial} $t_G(x,y) \in \Z[x,y]$ of a graph $G$ is the
unique function such that every generalized T-G invariant $f_G$ can be
expressed as
\[
f_G = \sigma^{\xi(G)}_f \tau^{|V|-c(G)}_f
t_G(\tfrac{f_I}{\tau_f},\tfrac{f_L}{\sigma_f})
\]
where $f_L$ and $f_I$ is the invariant of a loop and coloop, respectively.

Insofar the Tutte polynomial expresses a multitude of enumerative invariants,
but, to the best of our knowledge, there is no enumerative interpretation for
arbitrary evaluations of the Tutte polynomial.
The
reciprocity statements of Sections~\ref{sec:Flows} and \ref{sec:Tensions} yield
a natural interpretation of what the Tutte polynomial evaluated at $(1+\l,1+k)$
for positive $k,\l$ counts.

\begin{thm} \label{thm:TutteInterpretation}
    Let $G$ be a graph and $k,\l$ two positive integers. Then $t_G(1+\l,1+k)$
    counts triples $(f,t,\s)$ where
    \begin{enumerate}[i)]
        \item $f$ is a $\Zk$-flow and $t$ is a $\Zl$-tension on $G$,
        \item $f$ and $t$ have disjoint support, and
        \item $\s \subseteq E\setminus\supp(f)\cup\supp(t)$ is a reorientation of $G_{\setminus \supp(f) \cup
            \supp(t)}$.
    \end{enumerate}
\end{thm}

The polynomial  $t_G(1+\l,1+k)$ is also known as the rank polynomial of $G$.

In Appendix~\ref{sec:CombTutteProof}, we give a proof of
Theorem~\ref{thm:TutteInterpretation} from first principles, i.e.~we prove
that the stated cardinality itself is a generalized T-G invariant with
structure constants $\tau = \sigma = 1$ and values $1+k$ and $1+\l$ for loops
and coloops, respectively.  Here, however, we give a proof by noting that
Theorem~\ref{thm:TutteInterpretation} is equivalent to the convolution formula
for Tutte polynomials of Kook, Reiner, and Stanton \cite{KRS99} specialized to
graphs.

We need the following observation regarding reorientations of graphs.

\begin{lem}\label{lem:AcyclicTotCyclic}
  Let $G = (V,E)$ be an oriented graph. Then there is a unique $S \subseteq E$
  such that $G[S]$ is totally cyclic and $G_{/ S}$ is acyclic.
\end{lem}
\begin{proof}
  Let $S \subseteq E$ be the collection of edges that lie on a directed cycle
  in $G$. Then, clearly, $G[S]$ is totally cyclic and, as $G[S]$ is
  componentwise strongly connected, $G_{/ S}$ is acyclic. As for uniqueness,
  suppose that $S^\prime \subseteq E$ has the same properties. As $G[S']$ is
  totally cyclic, clearly $S'\subset S$. Now if $e \in S \setminus S^\prime$,
  then $e$ is contained in a directed cycle which remains true in $G_{/
  S^\prime}$, in contradiction to $G_{/ S^\prime}$ being acyclic. Hence
  $S=S'$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:TutteInterpretation}]
    Consider the collection of triples $(f,t,\s)$ as in the theorem. For every
    triple, we claim that there is a unique $S \subseteq E$ such that
    \begin{compactenum}
    \item $f$ is a $\Zk$-flow on $G[S]$ and $\sigma \cap S$ is a totally
        cyclic reorientation of $(G[S])_{/ \supp(f)}$, and
    \item $t$ is a $\Zl$-tension on $G_{/ S}$ such that $\sigma \setminus S$
        is an acyclic reorientation of $(G_{/ S})_{\setminus \supp(t)}$.
    \end{compactenum}
    Indeed, let $S^\prime \subseteq E$ be the set for $_\s
    G_{/\supp(f)\setminus\supp(t)}$ whose existence and uniqueness is asserted
    by Lemma~\ref{lem:AcyclicTotCyclic}. Now, it is easy to verify that $S :=
    S^\prime \cup \supp(f)$ is the unique set with the properties above.

    In light of Theorem \ref{thm:MainFlow} and Theorem
    \ref{thm:TensionReciprocity}, the number of triples for which $S$ is the
    unique set obeying the above properties is
    \[
    (-1)^{\xi(G[S])}\mFlow_{G[S]}(-k) \cdot (-1)^{|V| - c(G_{/ S})} \mTen_{G_{/
    S}}(-\l)
    \]
    The flow and tension polynomials are both specializations of the Tutte
    polynomial and hence
    \begin{align*}
        t_{G[S]}(0,1+k) &= (-1)^{\xi(G[S])}\mFlow_{G[S]}(-k)\\
        t_{G_{/ S}}(1+\l,0) &= (-1)^{|V| - c(G_{/ S})} \mTen_{G_{/S}}(-\l).
    \end{align*}
    To finish the proof, we recall the result of Kook, Reiner, and Stanton
    \cite[Thm.~1]{KRS99}\note{fix ref} stating that
    \[
        t_G(1+\l,1+k) = \sum_{S \subseteq E} t_{G[S]}(0,1+k)\,t_{G_{/S}}(1+\l,0).
    \]
\end{proof}

This interpretation yields the following counting formula which matches a
result of Reiner~\cite{reiner99} but removes the restriction to prime powers.
It follows from Theorem~\ref{thm:TutteInterpretation} together with the fact
that every flow or tension is nowhere zero restricted to its support.

\begin{cor}
    Let $G = (V,E)$ be a graph, then the Tutte polynomial is given by
    \[
    t_G(1+\l,1+k) = \sum_{S \subseteq T \subseteq E}
    2^{|T \setminus S|} \mFlow_{G[S]}(k) \mTen_{G_{/T}}(\l)
    \]
\end{cor}

Let us remark that enumerative interpretations for \emph{all} evaluations of
the Tutte polynomial are not to be expected as for negative parameters the
sign of $t_G(x,y)$ depends on the magnitude of the arguments. However, our
interpretation misses some fundamental evaluations such as $t_G(1,2)$ for the
number of spanning sets and $t_G(2,1)$ for the number of independent sets.  We
also remark that interpretations for evaluations of the flow- and tension
polynomials at negative values also yield \emph{interpretations} in the spirit
of \cite[Cor.~2]{reiner99} for the missing two orthants $(1-\l,1+k)$ and
$(1+\l,1-k)$.

redpajama_set_name: RedPajamaArXiv


text:
\@ifstar{\@ssection}{\@section}{\@ifstar{\@ssection}{\@section}}

\def\@section#1
  \if@nobreak
    \everypar{}%
    \ifnum\LastMac=\Hae \addvspace{\half}\fi
  \else
    \addpen{\gds@cbrk}%
    \addvspace{\two}%
  \fi
  \bgroup
    \ninepoint\bf
    \Raggedright
    \global\advance\Sec \@ne
    \ifappendix
      \global\Eqnno=\z@ \global\SubEqnno=\z@\relax
      \def\ch@ck{#1}%
      \ifx\ch@ck\empty \def\c@lon{}\else\def\c@lon{:}\fi
      \noindent\@nohdbrk APPENDIX\ \arabic{Sec}\c@lon\hskip 0.5em%
        \uppercase{#1}\@par}
    \else
      \noindent\@nohdbrk\arabic{Sec}\hskip 1pc \uppercase{#1}\@par}
    \fi
    \global\SecSec=\z@
  \egroup
  \nobreak
  \vskip\half
  \nobreak
  \@noafterindent
  \LastMac=\Hae\relax
}

\def\@ssection#1
  \if@nobreak
    \everypar{}%
    \ifnum\LastMac=\Hae \addvspace{\half}\fi
  \else
    \addpen{\gds@cbrk}%
    \addvspace{\two}%
  \fi
  \bgroup
    \ninepoint\bf
    \Raggedright
    \noindent\@nohdbrk\uppercase{#1}\@par}
  \egroup
  \nobreak
  \vskip\half
  \nobreak
  \@noafterindent
  \LastMac=\Hae\relax
}

\def\@ifstar{\@ssubsection}{\@subsection}{\@ifstar{\@ssubsection}{\@subsection}}

\def\@subsection#1
  \if@nobreak
    \everypar{}%
    \ifnum\LastMac=\Hae \addvspace{1pt plus 1pt minus .5pt}\fi
  \else
    \addpen{\gds@cbrk}%
    \addvspace{\onehalf}%
  \fi
  \bgroup
    \ninepoint\bf
    \Raggedright
    \global\advance\SecSec \@ne
    \noindent\@nohdbrk\thesection.\arabic{SecSec} \hskip 1pc\relax #1\@par}
    \global\SecSecSec=\z@
  \egroup
  \nobreak
  \vskip\half
  \nobreak
  \@noafterindent
  \LastMac=\Hbe\relax
}

\def\@ssubsection#1
  \if@nobreak
    \everypar{}%
    \ifnum\LastMac=\Hae \addvspace{1pt plus 1pt minus .5pt}\fi
  \else
    \addpen{\gds@cbrk}%
    \addvspace{\onehalf}%
  \fi
  \bgroup
    \ninepoint\bf
    \Raggedright
    \noindent\@nohdbrk #1\@par}
  \egroup
  \nobreak
  \vskip\half
  \nobreak
  \@noafterindent
  \LastMac=\Hbe\relax
}

\def\@ifstar{\@ssubsubsection}{\@subsubsection}{\@ifstar{\@ssubsubsection}{\@subsubsection}}

\def\@subsubsection#1
  \if@nobreak
    \everypar{}%
    \ifnum\LastMac=\Hbe \addvspace{1pt plus 1pt minus .5pt}\fi
  \else
    \addpen{\gds@cbrk}%
    \addvspace{\onehalf}%
  \fi
  \bgroup
    \ninepoint\it
    \Raggedright
    \global\advance\SecSecSec \@ne
    \noindent\@nohdbrk\thesubsection.\arabic{SecSecSec} \hskip 1pc\relax #1\@par}
  \egroup
  \nobreak
  \vskip\half
  \nobreak
  \@noafterindent
  \LastMac=\Hce\relax
}

\def\@ssubsubsection#1
  \if@nobreak
    \everypar{}%
    \ifnum\LastMac=\Hbe \addvspace{1pt plus 1pt minus .5pt}\fi
  \else
    \addpen{\gds@cbrk}%
    \addvspace{\onehalf}%
  \fi
  \bgroup
    \ninepoint\it
    \Raggedright
    \noindent\@nohdbrk #1\@par}
  \egroup
  \nobreak
  \vskip\half
  \nobreak
  \@noafterindent
  \LastMac=\Hce\relax
}

\def\paragraph#1
  \if@nobreak
    \everypar{}%
  \else
    \addpen{\gds@cbrk}%
    \addvspace{\one}%
  \fi%
  \bgroup%
    \ninepoint\it
    \noindent #1\ \nobreak%
  \egroup
  \LastMac=\Hde\relax
  \ignorespaces
}

\newif\ifappendix

\def
\@ifstar{\@ssection}{\@section}{Introduction}

The origin of primordial magnetic fields is one of the most important
problems in astrophysics (Peebles 1993) and, as pointed out by
Barrow {\it et al.} (1997), is still a mystery. Various processes
have been proposed for the primordial origin of a seed field. In particular,
several mechanisms on small dimensions have been suggested such as
fluctuations in the primordial plasma, creation in phase transitions in the
inflation era, etc. However, no satisfactory theory has been proposed
which creates a sufficiently intense magnetic field on the large scales of
galaxies and clusters of galaxies.

The basic idea  of a seed field is that, once produced, it can be later
amplified by a dynamo process (e.g. Zel'Dovich {\it et al.}
1983). However, it is necessary to generate a seed field with a sufficient
intensity such that a dynamo process can amplify it to the present
observed values. Another aspect that should  be satisfied by the proposed
mechanism is that the magnetic field should have a sufficiently large
coherence length so that it can be amplified by the dynamo mechanism (e.g.,
be at least of galactic dimension such that the differential galactic
rotation can amplify it).

Harrison (1973) proposed a mechanism for the generation of magnetic fields
before the recombination epoch. Assuming the existence of turbulence
with nonzero vorticity, he arrived at a magnetic field $\sim 10^{-18}~G$
on galactic scales. Rees (1987) pointed out, however, that the significant
vorticity
required by the model of Harrison is difficult to reconcile with the
expected predominance of irrotational density perturbations that should
become dominant in the post-recombination epoch. Another mechanism
suggested in the plasma epoch, but without requiring vorticity, was proposed
by Tajima {\it et al.} (1992). Based on the fluctuation-dissipation theorem,
they studied the electromagnetic fluctuations present in plasma in thermal
equilibrium and showed that in the plasma epoch ($1s<\tau<10^{13}~s$, where
$\tau$ is the cosmic time), a high intensity magnetic field exists at
$\omega \sim0$ (i.e., zero frequency). It is difficult to exactly
quantify the present intensity of this magnetic field, but it could be
as high as $~10^{-12}~G$. However, a more detailed treatment of the plasma
processes by Opher and Opher (1997a, 1997b) showed that the magnetic field
at zero frequency is appreciably less than that predicted by Tajima
{\it et al.} (1992).

Some authors suggested that magnetic fields could be created during
inflation (Turner and Widrow 1988; Ratra 1992). These scenarios can
lead to sufficiently large coherence scales for the fields because inflation
can lead to mechanisms acting on horizon scales.  However, the predicted
amplitudes are extremely sensitive to the parameters used. Another
suggestion is the creation of magnetic
fields in phase transitions. Quasnock {\it et al.} (1988) proposed a seed
field generating mechanism during the quark-hadron phase transition
(assuming a first order transition). The field strength obtained is
$\sim 10^{-17}~G$ on a scale $\sim 10^{10}~cm$ at the recombination epoch.
This scale is of order $1 AU$ at the present time, very small compared to
galactic scales. More recently, Sigl {\it et al.} (1997) obtained for the
seed field, generated in a first order phase transition, strengths
$\sim 10^{-29}~G$ on a $10~Mpc$ scale for the electroweak transition and
$10^{-20}~G$ for the QCD transition.

The generation of primordial magnetic fields in the early Universe, as a
consequence of the electroweak phase transition, has been studied more
recently by T$\ddot {\rm o}$rnkvist (1997, 1998) and Olesen (1997).
In particular, Olesen showed that at the electroweak scale, considering
that the magnetic field is essentially random, it is necessary to
produce a field $<B>\sim 10^{15}G$ such that at the present time we have
a primordial magnetic field of order $10^{-15}G$ on a scale of $100kpc$.

Barrow {\it et al.} (1997) has obtained, through a statistical analysis of
the 4-year COBE data, an upper limit of $B_0<3.4\times 10^{-9}(
\Omega_0h_{50}^2)^{1/2}G$ for the present strength of any primordial
homogeneous magnetic field. This limit is important because it restricts
the value of the seed field during the pre-recombination epoch.

Opher and Wichoski (1997) suggested that the origin of the magnetic field
is due to a nonminimal electromagnetic-gravitational coupling. Assuming
that the magnetic dipole moment is proportional to the angular momentum
with the proportionality constant normalized to existing observations,
Opher and Wichoski (1997) obtained galactic magnetic fields comparable to
those observed ($^>_\sim \mu G$).

For stars, a totally spontaneous mechanism of generating magnetic fields,
not requiring seed fields, was suggested. It is the Biermann mechanism
(Biermann 1950) that depends on the differential rotation in stars. As
pointed out by Kemp (1982), what creates the Biermann effect is the
difference in the acceleration imparted to the electrons, as compared to
the ions, by the differential pressures. The difference in acceleration
results in currents generating a double toroidal magnetic field, with the
magnetic fields being oppositely circulating in the upper and lower
hemisphere (the upper and lower hemispheres are defined with respect to
the rotation axis).

Several works deal with this mechanism (e.g., Mestel and Roxburgh 1962 and
Roxburgh 1966). In particular, Roxburgh (1966) analyzed whether or not there
is a meridional circulation in stars.

Recently, Kulsrud {\it et al.} (1997) suggested a mechanism of generating
protogalactic magnetic fields by a Biermann type like mechanism on shocks
in the intergalactic medium. Their mechanism generates a seed field of
$10^{-21}~G$.

We present here an alternative model to generate a seed magnetic field
of magnitude $\sim 10^{-14}~G$ to $5\times 10^{-10}~G$ which is many orders
of magnitude greater than many of the previously suggested scenarios. It
also is created over a relatively large scale making it relatively easy
to amplify by galactic differential rotation. It is based on the
supernovae explosion model of Miranda and Opher (1996, 1997) for
large-scale structure formation. Whereas, for example, the Kulsrud
{\it et al.} (1997) scenario requires a very strong dynamo action to
amplify the seed magnetic field of $\sim 10^{-21}~G$ to presently observed
values of $\sim 10^{-6}~G$, our scenario requires only a relatively mild
amplification.

The mechanism here proposed for generating seed magnetic fields is based
on the study of Lazarian (1992). It is a Biermann type mechanism because
it requires that the electronic temperature and density gradients are not
parallel, similar to what happens in the original mechanism in rotating
stars. We coupled this Biermann type mechanism to the explosion model of
Miranda and Opher (1996, 1997) for structure formation.

The multiple explosion scenario here presented is an extension of the model
first studied by Ostriker and Cowie (1981) and Ikeuchi (1981). Several
extensions of the Ostriker-Cowie-Ikeuchi model were posteriorly made (e.g.,
Carr, Bond and Arnett 1984, Carr and Ikeuchi 1985). In particular, Carr and
Ikeuchi (1985) studied a hierarchical model composed of the evolution of
discreet explosive stages. After the first results of the COBE satellite,
this model was considered incapable to produce large structures without
violating the limit of the anisotropy observed in the cosmic background
radiation. The multiple explosion scenario was recently retaken by Miranda
and Opher (1996,1997). They showed that, within the limits of their model,
the multiple explosion scenario can produce large voids with Compton-y
distortions compatible with the COBE limits.

In \S 2, we show that it is possible to generate seed magnetic fields
$\sim 10^{-12}-10^{-14}G$ on scales of galactic clusters and in \S 3
up to $\sim 4.5\times 10^{-10}G$ on $\sim 100kpc$ scales. These seeds can
be amplified during galactic formation to the observed values $\sim 1\mu G$
by a dynamo mechanism. Our discussion and conclusions are presented in \S 3.

\@ifstar{\@ssection}{\@section}{The Model}

When magnetic fields are present, we use magnetohydrodynamics to follow their
effects. In this work we consider that the electrical conductivity is
infinite. Thus, using Ohm's law in the Faraday equation, we have

$$
{\partial{\bf B}\over {\partial t}}=\nabla \times ({\bf v}\times
{\bf B})\eqno\stepeq
$$

On the other hand, Miranda and Opher (1996, 1997) showed that the multicycle
explosion scenario produces voids with characteristic radii $\sim 18-40Mpc$
(with the present value of the Hubble constant $h=0.5$, in units of
$100kms^{-1}Mpc^{-1}$). In this turbulent ambient medium formed by the
explosions of Population III objects, we have a high probability for the
formation of a temperature gradient not parallel to the density gradient.

The process proposed by Biermann (1950) is an efficient battery
mechanism (compared with, for example, the battery mechanism based on
Compton drag) because it can act on scales smaller than the galactic scale.
Thus, we include an additional term in the anterior equation given by (see
Lazarian 1992)

$$
{\partial{\bf B}\over {\partial t}}=\nabla \times ({\bf v}\times {\bf B})+
{4k_BcT\over \pi e}\left[ {\nabla n_e(r)\over {n_e}}\times
{\nabla T(r) \over T}\right]\eqno\stepeq
$$

\noindent where $n_e$ is the electron density, $T$ is the temperature and
${\bf v}$ is the velocity of the shock front.

The second term on the right side of equation (2) is similar to the original
Biermann mechanism, with the difference that we do not require rotation of
the medium (as proposed by Biermann). It is worth stressing that an
electromotive force can also be generated if there is a non-symmetric
distribution of ions with different masses (e.g. the study made by Mestel
and Roxburgh 1962).

For a fluid in which shocks and photoheating can occur, temperature and
density gradients are naturally not parallel so that $\nabla T \times\nabla
n_e\not=\vec 0$. As shown by Miranda and Opher (1996, 1997), the multicycle
explosive scenario for void formation produces a sequence of supernova
explosions at high and moderate redshifts, beginning from the collapse of a
Population III object.

At redshifts $z>8$, the main mechanism for cooling the shell of matter is
the Compton cooling mechanism. This mechanism quickly produces a dense shell
of matter where globules (that is, new gravitationally bound objects) are
formed. These globules could be composed of stellar clusters of high mass,
because the short Compton cooling time and the absence of metals favors the
fragmentation of the globules into stars of high mass (that have a short
life time). Thus, the explosion of these ``stellar clusters'' produces a
turbulent medium where gradients of density and temperature which are not
parallel can appear.

When the mass contained in a sphere of radius half the shell thickness is
equal to the Jeans mass, objects (or globules) of mass $\delta m$ within
the shell begin to collapse. The mass of these objects is obtained from

$$
\delta m=\left({M_S\over 4\pi R_S^2\xi}\right) {4\pi\over 3}\left({
\xi \over 3}\right) ^3\eqno\stepeq
$$

\noindent where $\xi $ is the shell thickness, $M_S$ is the total mass
contained inside the shell and $R_S$ is the radius of the shock front.

The temperature gradient exists inside the shell in the time interval from
the explosion of the globules until the thermalization of the shell.
Assuming that when the globules explode the characteristic separation
distance between two globules is of the order of the shell thickness, we
have

$$
{{\nabla n_e(r)}\over {n_e}}\simeq {{\triangle n_e}\over{n_e}}{1\over
{\xi f_n}}\eqno\stepeq
$$

\noindent and
$$
{{\nabla T(r)}\over T}\simeq {{\triangle T}\over T} {1\over {\xi f_T}}
\eqno\stepeq
$$

In Eqs. 4 and 5, the density gradient occurs over a distance $\xi f_n$ and
the temperature gradient over a distance $\xi f_T$. In general, $f_n$ and
$f_T$ are less than 1/2 (and can be very much less). We then have
$f_nf_T\equiv 0.25F$ with $F\leq 1$. In the present investigation we
consider that $F$ is in the interval 0.01 to 1.

Thus, we obtain from equation (2)

$$
{\partial{\bf B}\over {\partial t}}=\nabla \times ({\bf v}\times {\bf B})+
{{16k_BcT}\over {\pi e\xi ^2F}}\left[{{\triangle n_e}\over {n_e}}
{{\triangle T}\over T}\sin (\phi )\right], \eqno\stepeq
$$

\noindent where $\phi $ is the angle between the temperature and
density gradients. The value $\phi = \pi/2$ determines the upper limit
to the seed magnetic field produced in the multiple explosion scenario.
After the explosion of the globules, we assume that the strong shock
condition is maintained. Thus, from the usual Rankine-Hugoniot relation, we
have $\triangle n_e/n_e=4$. The temperature gradient occurs over the distance
$\xi f_T$ in Eq. 5 and, over this distance, we may expect $\triangle T\sim T$
due to the fact that immediately after the explosion of the globules the
temperature of the shock front is $\sim 10^8K$ while the temperature of the
material external to the shock front is several orders of magnitude lower.
Thus, we obtain in Eq. 6

$$
{{{\partial {\bf B}}\over {\partial t}}}=\nabla \times ({\bf v}\times
{\bf B}) + {{64k_BcT}\over {\pi e\xi ^2F}}.\eqno\stepeq
$$

It is worth stressing that the angle $\pi /2$ produces an upper limit to the
seed magnetic field produced in this scenario, as mentioned above. On the
other hand, when the globules are formed within the shell of matter, these
objects have sufficiently small cross sections such that the external
medium does not impede their propagation. The objects formed maintain their
peculiar velocity $V_P=V_S-V_H$, where $V_H$ is the Hubble flow (see Miranda
and Opher 1996). In this situation, when the explosion of the globules
occurs, the density gradient is in the direction of the shell expansion,
while the temperature gradient is situated between the globules (until
the thermalization of the shell). In this case, the angle between the two
gradients is not much smaller than $\pi/2$.

When the globules are formed and begin to collapse, the first term on the
right side of equation (7) is not active. On the other hand, during
this phase of evolution, the magnetic field is frozen in the matter of the
globules and (from the conservation of the magnetic flux) we need to
include an additional term on the right side of equation (7) to take into
account the variation with time of the area of the globules during the
shell collapse. Thus

$$
{\partial {\bf B}\over \partial t}=\nabla \times ({\bf v}\times
{\bf B}) + {64k_BcT\over \pi e\xi ^2F} - {2{\bf B}\over \xi}
{{d\xi}\over {dt}}.\eqno\stepeq
$$

It is worthwhile noting that the three terms on the right side of equation
(8) act during well defined phases. The first term acts during the
shell expansion phase. The second term acts during a short time after the
explosion of the globules when a temperature gradient exists in the shell.
The third term acts during the collapse of the globules when the temperature
inside the shell is lower than the Jeans temperature.

By the conservation of magnetic flux, a magnetic field present in the
Universe decreases as a function of the scale factor ($B\propto a^{-2}$).
On the other hand, during the shell expansion phase, when the first term on
the right side of equation (8) is important, the shell expands with a
velocity greater than the expansion rate of the Universe. Thus, due to the
fact that the field is frozen into the matter, it decreases as
$B\propto R_S^{-2}$, where $R_S$ is the radius of the shock front.

In the last explosion cycle of our model, the seed magnetic field is
increased due to the growth of the density contrast of the globules (which
may collapse to form quasars and galaxies) in relation to the ambient medium
(that is $\delta \rho /\rho \sim 10^5$, where $\rho $ is the ambient
density). The final collapse can increase the intensity of the seed magnetic
field by a factor $\sim 3,000$. Our final (present ) seed magnetic field
takes this factor into account.

In table 1 we have the present value of the seed magnetic field produced
by the collapse and explosion, at an initial redshift $z_i$, of a Population
III object with mass $M_0$. The evolution in explosion cycles generates
large shells of matter with a Compton y-distortion within the limit imposed
by the COBE satellite ($y\;_{\sim }^{<}\;1.5\times 10^{-5}$, see Miranda and
Opher 1996, 1997). The explosion models, presented in table 1, produce voids
within the range $18-26Mpc$. The last column of table 1 shows the coherence
length ($L$) of the magnetic field. The magnetic field $B$ in the table is
for $F=0.01$. For other values of $F$, the magnetic field $B$ is
approximately proportional to $F^{-1}$.

\begintable{1}
\caption{{\bf Table 1.} Seed Magnetic Field.}
\halign{#\hfil & \qquad \hfil#\hfil\qquad &
         \hfil#\hfil\qquad & \hfil#\hfil\qquad &
         \hfil#\hfil \cr

$M_0(M_\odot)$ & $z_i$ & $B(G)$ & $L(Mpc)$ \cr
\noalign{\vskip 10pt}
$10^6$    & 290 & $1.2\times 10^{-12}$ & 1.6 \cr
$10^7$    & 150 & $1.1\times 10^{-12}$ & 1.8 \cr
$10^8$    & 120 & $1.0\times 10^{-12}$ & 2.0 \cr
$10^9$    & 70  & $8.5\times 10^{-13}$ & 1.5 \cr
$10^{10}$ & 70  & $5.0\times 10^{-13}$ & 2.2 \cr
}

\tabletext{The present value of the seed magnetic field ($B$), and its
respective coherence length ($L$), produced by the collapse and explosion,
at initial redshift $z_i$, of a Population III object with mass $M_0$.}
\endtable

\@ifstar{\@ssection}{\@section}{Discussion and Conclusions}

The results presented in table 1 show that seed magnetic fields with
intensity $\sim 10^{-12}-10^{-14}G$ (for values of $F$ within the interval
$0.01 - 1$) can naturally be produced in the multicycle explosion scenario,
without any previous seed magnetic field in the beginning of the explosions.
The intensity of this seed field is sufficiently high to produce, by future
dynamo amplification (for example the $\alpha -\omega $ dynamo), a magnetic
field with intensity $\sim \mu G$ (on the order of typical galactic magnetic
fields). The coherence length ($L$) of these seed fields is $\sim 1.8 Mpc$,
the typical dimension of clusters of galaxies.

Due to the low values of the seed magnetic fields produced by the previous
suggested mechanisms, it is questionable if the dynamo mechanisms have enough
time to amplify the suggested seed fields to the observed values. The
amplification time scale in the protogalactic disk is of the order of the
rotation period of the disk, $\sim 3\times 10^{8}$ years. Our proposed
mechanism creates relatively high values of the magnetic field over a
large coherence length so that the dynamo mechanism can be effective.

Because of the large initial magnetic field, the dynamo action needs to
operate only over a relatively short time. Comparing with the models
previously proposed for the production of magnetic fields, our mechanism
produces seeds of the greatest intensity. In this model, the generation of
the magnetic field occurs after the recombination era as a result of the
formation of the structures of the Universe.

The generation of seed magnetic fields, as a consequence of the explosive
scenario for the formation of the large-scale voids, is consistent with the
detection of a large-scale intercluster magnetic field, found in the Coma
supercluster, with an estimated strength of $0.3-0.6\mu G$. This detected
magnetic field could be the result of a primordial field, generated and
amplified during the formation of the supercluster (Kim {\it et al.} 1989).
It is worth mentioning that coherence of the magnetic field over a
large-scale (e.g., the Coma supercluster) could occur via reconnection
over causally unconnected regions (Hogan 1983).

It is interesting to note that the magnetic field can have several effects
on the history of the Universe (e.g., Kronberg 1994). The question of
whether magnetic fields are amplified is relevant in several areas related
with the formation and evolution of galaxies (e.g Rees 1978; Coles 1992).
For example, stellar formation can change for different values of the
magnetic field. That is, the star formation rate and the distribution of
stellar masses can be modified, because the magnetic field alters the
Jeans mass and is important in the loss of angular momentum during
protostellar collapse. Also, as shown by Wasserman (1978), and more recently
by Kim {\it et al.} (1996), a primordial magnetic field can have a direct
effect on triggering galaxy formation. Early creation of magnetic fields
can also play an important role in particle cosmology by modifying the
clustering properties of dark matter particles sensitive to the presence of
a magnetic field (Enqvist 1998).

Although in table 1 we present only models that produce large voids with
present radii $R_{SF}>18Mpc$, an interesting characteristic of the
multiple explosion scenario is that, independent of the radius of the void formed,
a seed field can naturally be produced. For example, in the multicycle
explosion model, the explosion of an object with initial mass
$10^5M_{\odot }$ (a typical mass of a globular cluster) at redshift $z=25$
produces a small void with a present diameter $1.5Mpc$ but with a magnetic
field of strength $4.5\times 10^{-10}G$ (with $F=0.01$) and a coherence
length $\sim 100kpc$.

A void with radius $1.5Mpc$ certainly makes a small contribution to the
formation of the large-scale structures of the Universe. But, on the other
hand, these small voids formed by explosions can be very important for
the generation of seed magnetic fields on galactic scales.

\@ifstar{\@ssection}{\@section}*{Acknowledgements}

We thank Dr. J.C.N. de Araujo for useful discussions. We would also like to
thank Dr Alex Lazarian, the referee, for his helpful suggestions and
comments that improved the present version of our paper.

\noindent O.D.M thanks the Brazilian agency FAPESP for support (grant
97/02596-3). M.O. would also like to thank the Brazilian agency FAPESP
for support. R.O. thanks the Brazilian agency CNPq for partial support.
We would also like to thank the Brazilian project Pronex/FINEP
(no. 41.96.0908.00) for support. The calculations were made on the
Workstation Apollo 9000 purchased by the Brazilian Agency FAPESP.

\@ifstar{\@ssection}{\@section}*{References}
\beginrefs
\bibitem  Barrow, J.D., Ferreira, P.G. \& Silk, J. 1997, Phys. Rev. Lett.,
78, 3610.

\bibitem  Biermann, L. 1950, Z. Naturforsch, 5a, 65.

\bibitem  Carr, B.J., Bond, J.R. \& Arnett, W.D. 1984, ApJ, 277, 445.

\bibitem  Carr, B.J. \& Ikeuchi, S. 1985, MNRAS, 213, 497.

\bibitem  Coles, P. 1992, Comm. on Astrop., 16, 45.

\bibitem  Enqvist, K. 1998, astro-ph/9803196.

\bibitem  Harrison, E.R. 1973, MNRAS, 165, 185.

\bibitem  Hogan, C.J. 1983, Phys. Rev. Lett., 51, 1488.

\bibitem  Ikeuchi, S. 1981, PASJ, 33, 211.

\bibitem  Kemp, J.C. 1982, PASP, 94, 627.

\bibitem  Kim, K.T., Kronberg, P.P., Giovannini, G. \& Venturi, T. 1989,
Nature, 341, 720.

\bibitem  Kim, E., Olinto, A.V. \& Rosner, R. 1996, ApJ, 468, 28.

\bibitem  Kronberg, P.P. 1994, Rep. Prog. Phys., 57, 325.

\bibitem  Kulsrud, R.M., Cen, R., Ostriker, J.P. \& Ryu, D. 1997,
ApJ, 480, 481.

\bibitem  Lazarian, A. 1992, A\&A, 264, 326.

\bibitem  Mestel, L. \& Roxburgh, I.W. 1962, ApJ, 136, 615.

\bibitem  Miranda, O.D. \& Opher, R. 1996, MNRAS, 283, 912.

\bibitem  Miranda, O.D. \& Opher, R. 1997, ApJ, 482, 573.

\bibitem  Olesen, P. 1997, hep-ph/9708320

\bibitem  Opher, M. \& Opher, R 1997a, Phys. Rev. D, 56, 3296.

\bibitem  Opher, M. \& Opher, R 1997b, Phys. Rev. Lett., 79, 2628.

\bibitem  Opher, R. \& Wichoski, U. 1997, Phys. Rev. Lett., 78, 787.

\bibitem  Ostriker, J.P. \& Cowie, L.L. 1981, ApJ, 243, L127.

\bibitem  Peebles, P.J.E. 1993, Principles of Physical Cosmology,
Princeton U.P., Princeton.

\bibitem  Quashnock, J.M., Loeb, A. \& Spergel, D.N. 1989, ApJ, 344, L49.

\bibitem  Ratra, B. 1992, ApJ, 391, L1.

\bibitem  Rees, M.J. 1978, Phys. Scrip., 17, 371.

\bibitem  Rees, M.J. 1987, QJRAS, 28, 197.

\bibitem  Roxburgh, I.W. 1966, MNRAS, 132, 201.

\bibitem  Sigl, G. \& Olinto, A.V. 1997, Phys. Rev. D, 55, 4582.

\bibitem  Tajima, T., Cable, S., Shibata, K. \& Kulsrud, R.M. 1992, ApJ,
390, 309.

\bibitem  T$\ddot {\rm o}$rnkvist, O. 1997, hep-ph/9707513

\bibitem  T$\ddot {\rm o}$rnkvist, O. 1998, hep-ph/9801286

\bibitem  Turner, M.S. \& Widrow, L.M. 1988, Phys. Rev. D, 37, 2743.

\bibitem  Wasserman, I. 1978, ApJ, 224, 337.

\bibitem  Zel'Dovich, Ya.B., Ruzmaikin, A.A. \& Sokolov, D.D. 1983,
Magnetic Fields in Astrophysics, Gordon \& Breach Pub.

\@notice\par\vfill\supereject\end