\documentclass[12pt]{article}
\textwidth= 6.5in
\textheight= 9.0in
\topmargin = -20pt
\evensidemargin=0pt
\oddsidemargin=0pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9

\usepackage{amsfonts,amssymb,latexsym,amsmath,amsxtra}
\usepackage[dvips]{graphics}

 
% \theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
% \theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
% \theoremstyle{remark}
\newtheorem{notation}{Notation}
\numberwithin{equation}{section}

\newcommand{\ve}{\varepsilon}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\Shat}{S_{n}'}
\newcommand{\Chat}{C_{d}'}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\Qbar}{{\overline{\mathbb Q}}}
\newcommand{\F}{{\mathbb F}}
\newcommand{\rk}{ \mbox{\rm rk} }
\newcommand{\norm}[1]{\left|#1\right|}
\newcommand{\fix}[1]
    { \ \\ \begin{center} {\huge \bf FIX THIS!!! -- {#1}} \end{center} }


\def\({\left(}
\def\){\right)}

\newcommand{\ontop}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\newcommand{\mymod}[1]{\,\,({\rm mod}\,\,{#1})}


\def\secmatrix{2}
\def\Directed{3}
\def\Undirected{4}
\def\CONJECTURE{5}


\begin{document}
\vspace*{-40pt}
{\smalltt INTEGERS: \smallrm ELECTRONIC
 JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 6 (2006), \#A33\hfill}
\vskip 40pt


\begin{center}
{\bf TRIVIAL SELMER GROUPS AND EVEN PARTITIONS OF A GRAPH}
\vskip 20pt
{\bf Morgan V. Brown \footnote{Partially supported by NSF grant 
                         DMS:0244001.}}\\
{\smallit Department of Mathematics, Duke University, Durham, NC 27708, USA} \\
%{\tt mvb2@duke.edu} \\ 
\vskip 10pt
{\bf Neil J. Calkin \footnote{Partially supported by NSF grant
                          DMS:0244001}}\\
{\smallit Department Mathematical Sciences, Clemson University,
         Clemson, SC 29634, USA}\\
%{\tt calkin@clemson.edu}\\ 
\vskip 10pt
{\bf Kevin James \footnote{Partially supported by NSF grant
                          DMS:0244001}}\\
{\smallit Department Mathematical Sciences, Clemson University,
         Clemson, SC 29634, USA}\\ 
%{\tt kevja@clemson.edu} \\ 
\vskip 10pt
{\bf Adam J. King \footnote{Partially supported by NSF grant
                        DMS:0244001}}\\
{\smallit Department Mathematical Sciences, 
          University of California - Los Angeles, 
          Los Angeles, CA 90095,
          USA}\\
%{\tt aking@math.ucla.edu } \\ 
\vskip 10pt
{\bf Shannon Lockard \footnote{Partially supported by NSF grant
                                               DMS:0244001}}\\
{\smallit Department Mathematical Sciences, Clemson University,
         Clemson, SC 29634, USA}\\ 
%{\tt renees@clemson.edu} \\ 
\vskip 10pt
{\bf Robert C Rhoades \footnote{Partially supported by NSF grant
                   DMS:0244001 and an NSF graduate fellowship}}\\
{\smallit Department Mathematics, University of Wisconsin--Madison,
         Madison, WI 53706, USA}\\ 
%{\tt rhoades@math.wisc.edu } \\ 
\end{center}
\vskip 30pt
\centerline{\smallit Received: 3/23/06,
Revised: 8/30/06, Accepted: 10/6/06, Published: 11/2/06}
\vskip 30pt

\centerline{\bf Abstract}

\noindent
Feng and Xiong give necessary and sufficient conditions to determine
when the elliptic curve $E_n: y^2 = x^3 - n^2x$ has trivial 2-Selmer
groups in terms of certain graphs $G(n)$ determined by the prime
factorization of $n$. These conditions involve understanding when
this graph has no {\it even} partitions of its vertex set; such a
graph is called {\it odd}. Our main theorems give the probability
that a random graph on $k$ vertices is odd, and the probability that
a random undirected graph on $k$ vertices has a certain number of
even partitions.  We relate these probabilities to the problem of
determining how many square-free integers yield 2-Selmer groups of a
given size and the problem of counting congruent numbers.


\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC
 JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 6 (2006), \#A33\hfill}

\thispagestyle{empty}
\baselineskip=15pt
\vskip 30pt 

\addtocounter{section}{1}
\section*{\normalsize \thesection. \ Introduction}
A square-free integer $n$ is said to be congruent provided that it
is the area of a rational right triangle. The determination of which
$n$ are congruent is an old problem studied by many mathematicians
(see \cite{k}). It is well known (see \cite[sections 1.1 and
1.2]{k}) that $n$ is congruent if and only if the rank of the the
elliptic curve \begin{equation*} E_n: y^2= x^3-n^2x\end{equation*} is
positive.


The rank of an elliptic curve can be a difficult property to study, so
we study a more tractable invariant, namely the sizes of the
2-Selmer groups. In particular we study the 2-Selmer groups of the
congruent number curves $E_n$.   Let $S=\{\infty\} \cup \{
p \mbox{ prime}: p|2n\}$ and $M$ be the subgroup of
$\Q^\times/(\Q^\times)^2$ generated by $-1$ and all the prime
factors of $2n$.  For each $d\in M$, we define the curves
\begin{align*}
&C_d: dw^2 = t^4 + (2n/d)^2 z^4 \\
&C_d': dw^2 = t^4 - (n/d)^2 z^4.
\end{align*}
Then the Selmer groups $S_n$ and $S_n'$  arising from a 2-isogeny of $E_n$
and its dual are defined by
\begin{align*}
S_n:=& \{d \in M:  C_d(\Q_v) \ne \emptyset \text{ for all } v\in S\} \\
S_n':=&  \{d \in M:  C_d'(\Q_v) \ne \emptyset \text{ for all } v\in S\},
\end{align*}
where $C_d(\Q_v)\ne \emptyset$ means the curve $C_d$ has nontrivial
solutions $(w,t,z) \ne (0,0,0)$ in $\Q_v$.


The sizes of these Selmer groups can give information about the rank
of $E_n$ as well as information useful in verifying the Birch and
Swinnerton-Dyer conjecture. It is clear from the definition that
$\{1\} \subset S_n$ and $\{\pm 1, \pm n\} \subset S_n'$.  It is well
known (\cite{sil}) that when $S_n =\{1\} $ and $S_n' =\{\pm 1, \pm
n\}$, the rank of $E_n$ is zero.  In particular, in this case $n$ is
a non-congruent number. Furthermore, under these assumptions on
$S_n$ and $S_n'$ it is possible to deduce that the Tate-Shafarevic
group of $E_n$ has odd order.  The significance of this is that for
such $E_n$, verifying the celebrated Birch and Swinnerton-Dyer
conjecture becomes a matter of showing a certain special value of
the $L$-function associated to $E_n$ is odd.   For more about this
the interested reader should see \cite{r1, r2}. This analysis shows
why it is useful to understand when the Selmer groups are as small
as possible.

The focus of this paper is the problem of
counting how many $n <X$, for large $X$, have Selmer groups a given
size. This question was the focus of Heath-Brown's two papers
\cite{hb1, hb2}. He gave the following answer to this question.

\begin{theorem}[Heath-Brown, \cite{hb2} Theorem 2]\label{thm:heathbrown}
Let $2^{2+s(n)} = \norm{S_n}\cdot\norm{S_n'}$, $\lambda =
\prod_{n\ge 1} (1+2^{-n})^{-1}=\prod_{j\ge 1} (1-2^{-2j+1})
=0.4194\ldots,$ and
$$d_r = \lambda \frac{2^r}{\prod_{1\le j \le r} (2^{j}-1)}.$$ Then
if $h\equiv 1, 3 \mymod{8}$ and $r$ is even, or $h\equiv 5,
7\mymod{8}$ and $r$ is odd, we have $$\norm{\{n\in S(X,h): s(n) =
r\}}\sim d_r S(X,h),$$ where $S(X,h)$ is the set of all square-free
integers less than $X$ which are congruent to $h$ modulo 8.
\end{theorem}


%As we will see below, $s(n)$ is completely determined by the
%congruence classes of the $p_j$ modulo $8$ and the values
%$\(\frac{p_i}{p_j}\)$, the Legendre symbol $p_i$ over $p_j$.  As the
%primes vary over all possibilities every possibility appears and
%furthermore, since they are independent they will appear equally
%likely.
Heath-Brown remarks in \cite{hb2} that the convergence in this
theorem is very slow. He also remarks that one should consider the rate
of convergence to the limiting distribution as depending on the
number of prime factors of the number rather than the size of the
numbers.
%He
%adds that when $k$ is small $s(n)$ tends to take larger values than
%what is predicted by Theorem \ref{thm:heathbrown}.
For this reason we study the refined problem of determining an
asymptotic for the size of
$$\{n \in S(X,h,k):s(n) = r\},$$ where $S(X,h,k)$ is the set of all
square-free integers less than $X$ congruent to $h$ modulo 8 which
have exactly $k$ prime factors.  We will focus on the case where
$h=3$ and $r=0$.

Our approach begins with a theorem of Feng and Xiong \cite{fx}, who
give necessary and sufficient conditions for the Selmer groups
associated to $E_n$ to have this trivial form. In order to
characterize the $n$ for which $E_n: y^2 = x^3 -n^2x$ has trivial
2-Selmer groups, Feng and Xiong \cite{fx} introduce the idea of an
even partition of a graph.

\begin{definition}
Suppose that $G$ is a graph with vertex set $V$ and edge set $E$.
A {\em partition} of $G$ is a pair $(S,T)$ of sets such
that $S \cap T = \emptyset$ and $S\cup T = V$.
(Furthermore, we consider the partitions $(S,T)$ and $(T,S)$ to be the same
partition.)
% Additionally, we say that a vertex $v$ is a neighbor of $w$ if
% $\overrightarrow{wv} \in E(G)$.
A partition $(S, T)$ is {\em even} provided that all $v\in S$ have
an even number of edges directed from $v$ to vertices in $T$ and all
$v\in T$ have an even number of edges directed from $v$ to vertices
in $S$.
\end{definition}

In particular, the partition $(G, \emptyset)$ is always an even
partition. We call this the trivial (even) partition.
\begin{definition}
A graph $G$ is called {\em even} provided that it admits a nontrivial even
partition.
A graph $G$ is said to be {\em odd} provided that it only admits the
trivial even partition.
\end{definition}

For example, note that all disconnected graphs are even. Likewise
$K_4$, the complete graph on 4 vertices, is an even graph. To see
this, note that the partition $\( \{ v_1, v_2\}, \{v_3, v_4\}\)$ is
even since each vertex has two neighbors in the other set. In fact,
$K_{2n}$ is an even graph for all $n$. It is easy to see that
$K_{2n+1}$ is an odd graph for all $n\ge 1$. Indeed, if $\(S, T\)$
is a nontrivial partition of $V(K_{2n+1})$, either $S$ or $T$
(say $S$) contains an odd number of vertices. Then all $v \in
T$ have an odd number of neighbors in $S$, so that $(S,T)$ is not
even. Thus $K_{2n+1}$ is an odd graph. Furthermore, all undirected
cycles on an even number of vertices are even.  Let $C_{2n}$ be a
cycle on $2n$ vertices $v_1, \ldots, v_{2n}$ with $E(C_{2n}) =
\{\overline{v_1v_2}, \ldots, \overline{v_{2n}v_1} \}$, and let $S =
\{v_1, v_3, \ldots, v_{2n-1}\}$ and $T= \{v_2, v_4, \ldots,
v_{2n}\}$. Then every vertex in $S$ is adjacent to exactly two
vertices in $T$, and every vertex in $T$ is adjacent to exactly two
vertices in $S$.% Similarly, any bipartite graph with all vertices
%having even degree is even.

Before stating the first of the main theorems of \cite{fx}, we will
need to define the graphs considered in that paper. For a
square-free odd integer $n = p_1\dots p_t$, define the directed graph
$G(n)$ by
\begin{equation*}
V(G(n)) = \{p_1, \ldots, p_t\} \hspace{.05in} \text{ and }
\hspace{.05in} E(G(n)) = \bigg\{\overrightarrow{p_ip_j}:
\(\frac{p_i}{p_j}\) = -1, 1 \le i\ne j \le t \bigg\}.
\end{equation*}

\begin{theorem}[Feng-Xiong, \cite{fx} Theorem 2.4]\label{Thm2.4}
Suppose that $n \equiv \pm 3\mymod{8}$.  Then $S_n = \{1\}$ and
$S_n' = \{\pm 1,\pm n\}$ if and only if the following three
conditions are satisfied:\begin{enumerate}

\item $n \equiv 3\mymod{8}$
\item $n = p_1 \dots p_t$, $p_1 \equiv 3\mymod{4}$ and $p_j \equiv 1
\mymod{4}$ for  $(2\le j \le t)$.
\item  $G(n)$ is an odd graph. \end{enumerate}
\end{theorem}

For any $n$ that satisfies the first two conditions, by quadratic
reciprocity $G(n)$ can be viewed as an undirected graph.
Furthermore, by Dirichlet's theorem on primes in arithmetic
progressions and induction on the number of prime factors of $n$, we
see that for any undirected graph $G$ there exist infinitely many
$n$ such that $G(n) = G$.

Given that there are infinitely many $n$ such that each undirected
graph $G$ appears as $G(n)$, one might hope that selecting $n$ at
random would result in selecting a random graph $G(n)$. To make this
more precise, fix an integer $k$, and let $n_1, n_2, n_3,
\dots$ be the square-free integers with $k$ prime
factors that satisfy the first two conditions of Theorem
\ref{Thm2.4}. We might hope that if we look at the corresponding sequence of graphs $G(n_1), G(n_2), \dots$, the undirected graphs on $k$
vertices will appear in the sequence with equal proportion.  If this is true
the proportion of $n_j \in \{n_1, n_2, \dots\}$ that have trivial
Selmer groups $S_n$ and $S_n'$ should be the same as the probability
that a random undirected graph on $k$ vertices is odd.

In Section~\Undirected, we compute the probability that a
random undirected graph on $k$ vertices is odd, denoted $q(k)$.  We
show \begin{equation}\label{eqn:oddprob} q(k) = \prod_{j=1}^s
\(1-2^{-2j+1}\),\end{equation} where $s=\lfloor \frac{k}{2}\rfloor$
is the greatest integer less than or equal to $k/2$. This yields $$\norm{\{n \in
S(X,3,k):s(n) = 0\}} \sim q(k) S_k(X),$$ where
\begin{equation}\label{eqn:eligibleNums}S_k(X) :=\{n< X: n\equiv
3\mymod{8} \text{ and } n =p_1p_2\cdots p_k \text{ where } p_1
\equiv 3, p_j \equiv 1 \mymod{4}, j\ne 1\}.\end{equation}


%{\it To compare this with Theorem \ref{thm:heathbrown} notice that
%$\lim_{k\to \infty} q(k) = \lambda =d_0$ and that $q(k) > \lambda$
%for all $k$. This shows that $n\equiv 3\mymod{8}$ tends to have
%$s(n)=0$ more often when $n$ has a small number of prime factors,
%then a general $n$.  Additionally, using $\lim_{k\to\infty }q(k) =
%\lambda$ we can also obtain the special case of Heath-Brown's result
%for $h=3$ and $r=0$ by summing over all $k$. }


%
%In Section~\CONJECTURE, we state the conjecture hinted upon in
%the previous paragraph more formally.  We also give a heuristic
%argument and numerical evidence to support the conjecture.

Although we only give the details for computing an asymptotic for
the size of $\{n\in S(X,3,k): s(n) =0\}$, the approach given
here can be generalized to computing asymptotics for the size of
the sets
\begin{align*}&
\{n\in S(X,h,k): s(n) =r\} \\ &\{n\in S(X,h,k): \norm{S_n} =2^r\}\\
&\{n\in S(X,h,k): \norm{S_n'} =2^r\},
\end{align*} where $h, k,$ and $r$ are arbitrary.
To do so, one would begin with additional work of Feng and Xiong and
more recent work of James and Faulkner.  Feng and Xiong \cite{fx}
give theorems like Theorem \ref{Thm2.4} for the cases when $n\equiv
\pm 1 \mymod{8}$ and for the case when $n$ is even. Furthermore,
recent work of Faulkner and James \cite{fj} has greatly generalized
the work of Feng and Xiong. For each $n$, Faulkner and James use the
prime factorization of $n$ to define a graph associated to $n$. Then
they describe how to compute the size of $S_n$ and $S_n'$ by
counting the number of even partitions of a graph depending on $n$
which is defined similarly to $G(n)$.

As a result of their work and the results presented in 
Sections~\Directed\  and~\Undirected, for any fixed $k, h, s,$ and
$s'$, it is possible to conjecture the proportion of $n$ congruent
to $h$ modulo 8 with $k$ prime factors that have $|S_n| = 2^s$ and
the proportion of such $n$ with $|S_n'|=2^{s'}$.

In general, for some set of square-free positive integers $S(X,h,k) = \{n_1,
n_2, \dots \}$, we may determine the set of graphs that appear among $G(n_1), G(n_2), \dots$, where $G(n)$ is the
appropriately defined graph. Once the structure of these graphs is
understood, using Theorems \ref{GenDir} and \ref{thm:GenUnDir}, or
slight variations of them, we can determine the probability that a
graph selected at random from this set will have $r$ even
partitions. Using the results of Faulkner and James we can then
conjecture the proportion of integers in $\{n_1, n_2, \dots \}$ that
have Selmer group with size $r$.  To prove the conjecture it is
enough to establish the fact that the graphs in the set are
independent.  In all cases, this should follow from the fact that as
we run over all primes $p_i$ and $p_j$ the values of the Legendre
symbol $\(\frac{p_i}{p_j}\)$ are independent.

Though the motivation for studying even partitions of a graph was
its connection to the congruent number problem, the results may be
of independent interest. In Section~\secmatrix\  
we will give
some preliminary results about matrix representations of graphs and
how to compute the number of odd partitions of a graph via that
representation.  One result from this section is that the number of
even partitions is a power of two.  With this result in hand, in
Section~\Directed\  we obtain the following theorem:
\begin{theorem}\label{thm:DIRECTED}
If a directed graph on $k$ vertices is chosen at random where the
probability of each such graph being selected is equal, then the
probability that our graph  has $2^j$ even partitions is given by
\begin{equation*}
\frac{1}{2^{k(k-1)}} \frac{2^{(k-1)^2}
(2^k-1)\prod_{i=j+1}^{k-1}\left[1-(1/2)^{i}\right]^2} {2^{j^2}
(2^{j+1}-1)\prod_{i=1}^{k-1-j}\left[1-(1/2)^{i}\right]}.
\end{equation*}
\end{theorem}
Answering the same question for the set of undirected graphs is
harder.  We do that in Section~\Undirected\  with the following
theorem:

\begin{theorem}\label{thm:UNDIRECTED}
Let $q(k,n)$ be the probability that a graph on $k$ vertices has
$2^n$ even partitions with $0\le n\le k-1$.  Then
$$
q(k,n) = d(k-1,n) \cdot
2^{\left[\binom{k-n}{2} - \binom{k}{2}\right]}
       \prod_{j=1}^s \(1-\(\frac{1}{2}\)^{2j-1}\),
$$
where $s = \lfloor \frac{k-n}{2}\rfloor,$ and
$$d(n,j) = \prod_{i=0}^{j-1}\frac{2^n-2^i}{2^j - 2^i}.$$
% and
%$q(k)=q(k,0)$ is defined in equation (\ref{eqn:oddprob}).
\end{theorem}
Finally in Section~\CONJECTURE\  we relate these results back to
the number theoretic results about the congruent number curves by
giving numerical evidence to support the claims discussed in this
introduction.

%\section*{Acknowledgments}
%This research took place during the 2004 REU at Clemson University.
%The authors are thankful for useful discussions with Bryan Faulkner. The
%sixth author is also thankful for useful discussions with Pamela
%Gorkin and Jeremy Rouse.  We are grateful to the referee for making
%several helpful corrections and very useful suggestions which
%greatly improved this paper.


%The conjecture we will present at the end of this paper is in some sense the easiest case of
%these conjectures, since the graphs that appear are always
%undirected graphs.

%
%For the case $n \equiv \pm 1 (\mod{8})$, Feng and Xiong define a
%second graph $G(-n)$ as follows. Let $n =p_1\dots p_t q_1\dots q_s$
%where $p_j \equiv 1(\mod{4})$ and $q_j \equiv 3(\mod{4})$.  The
%graph $G(-n)$ is defined by
%\begin{align*}
%V(G(-n)) =& \{-1,p_1, \ldots, p_t, q_1, \ldots, q_s\} \\
%E(G(-n)) =& \{\overline{p_ip_j}: \(\frac{p_j}{p_i}\) = -1,
%1 \le i\ne j \le t\} \\
%& \cup \{\overrightarrow{p_iq_j}: \(\frac{q_j}{p_i}\) = -1,
%1 \le i\le t, 1\le j\le s \} \\
%& \cup\{ \overrightarrow{(-1)r}: r\in \{p_1, \ldots, p_t, q_1,
%\ldots, q_s\}, r \equiv \pm 3(\mod{8}) \}
%\end{align*}
%
%\begin{theorem}[{\bf Feng-Xiong Theorem 2.5}] \label{Thm2.5}
%Suppose that $n \equiv \pm 1(\mod{8})$.  Then $S_n = \{1\}$ and
%$S_n' = \{\pm 1,\pm n\}$
%if and only if the following three conditions are satisfied:\\
%{\it (i)} $n \equiv 1(\mod{8})$ \\
%{\it (ii)} the decomposition of $n$ has one of the following forms:
%\begin{align}
%\nonumber
%n =& p_1\dots p_rP_1\dots P_s Q_1 Q_2;   \\
%\nonumber
%n =& p_1\dots p_rP_1\dots P_t q_1 q_2;  \\
%\nonumber n=& p_1\dots p_rP_1\dots P_l Q_1 q_1;
%\end{align}
%where $p_i \equiv 1, P_j \equiv 5, Q_i \equiv 3, q_j \equiv 7
%(\mod{8})$ and
%$$r\ge 0, \, \, \, 2|s \ge 0 \, \, \, 2|t \ge 2\,\,\, 2 \nmid l\ge 1.$$
%{\it (iii)} $G(-n)$ has only one non-trivial even partition, namely
%$\{-1\}$ and $V\setminus \{-1\}$.
%
%\end{theorem}
%
%Consider a graph $G$ on the vertex set $\{-1, p_1,\dots,
%p_r,P_1,\dots, P_s, Q_1, \dots, Q_{t},q_{1}, \dots,q_{u}\}$ having
%undirected edges among the the vertices in $P = \{p_1,\dots,
%p_r,P_1,\dots, P_s\}$, directed edges from the vertices in $Q=
%\{Q_1, \dots, Q_{t},q_{1}, \dots,q_{u}\}$ to the vertices in $P$, no
%edges from vertices in $P$ to those in $Q$ and a directed edge from
%-1 to each vertex in $\{P_1,\dots, P_s,Q_1, \dots, Q_{t} \}$. Using
%Dirichlet's theorem, it is easy to see that there are infinitely
%many values of $n$ such that $G(-n)=G$.
%
%The final case to consider is when $2|n$. In this case we define a
%third graph $G'(n)$. Let $n = 2p_1\dots p_t q_1\dots q_s$ where $p_j
%\equiv 1(\mod{4})$ and $q_j \equiv 3(\mod{4})$. The graph $G'(n)$ is
%defined by
%\begin{align*}
%V(G'(n)) =& \{2, p_1, \ldots, p_t, q_1, \ldots, q_s\} \\
%E(G'(n)) =& \{\overline{p_ip_j}: \(\frac{p_j}{p_i}\) = -1,
%1 \le i\ne j \le t\} \\
%& \cup \{\overrightarrow{p_iq_j}: \(\frac{q_j}{p_i}\) = -1,
%1 \le i\le t, 1\le j\le s \} \\
%& \cup\{ \overrightarrow{(p_i2}: \(\frac{2}{p_i}\) = -1, 1\le i \le
%t\}
%\end{align*}
%
%We now have the final of the three main theorems given in \cite{fx}.
%
%\begin{theorem}[{\bf Feng-Xiong Theorem 2.6}] \label{Thm2.6}
%Suppose that $2|n$ and $n$ has the decomposition given above.  Then
%$S_n = \{1\}$ and $S_n' = \{\pm 1,\pm n\}$ if and only if the graph
%$G'(n)$ is odd.  Furthermore, if $S_n = \{1\}$ and $S_n' = \{\pm
%1,\pm n\}$ then $s=0$ and there exists at least one $i$ such that
%$p_i \equiv 5(\mod{8}).$
%\end{theorem}
%
%As before, we can use Dirichlet's theorem to see that any graph $G$
%which could be $G'(n)$ actually occurs infinitely often as $n$
%varies.

%%%%%%%%%%%%%%%%%%%   Matrix Representation   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vskip 30pt
\addtocounter{section}{1}
\section*{\normalsize \thesection. \ Matrix Representations} 
%\label{sec:matrix}

The adjacency
matrix $A(G)$ of a graph $G$
 is defined by $A(G) = \(a_{ij}\)_{1\le i,j\le k}$,
where $a_{ij} = 1$ if $\overrightarrow{v_iv_j} \in E(G)$ and $a_{ij}
= 0$ otherwise. It will be more convenient to work with the Laplace
matrix of $G$. Let $d_i = \sum_{j=1}^k a_{ij}$ (the out degree of
vertex $v_i$ $(1\leq i \leq k)$). The Laplace matrix of $G$ is
defined by $L(G) = diag(d_1, \cdots ,d_k) - A(G)$.  We will consider
$L(G)$ as a matrix over $\F_2$. The following proposition allows us
to use this matrix representation to tell whether or not a partition
is an even partition. Let $(S,T)$ be a partition. Then we define the
vector $\vec{v}(S) = \(g_j\)_{1\le j\le k}$ by $g_j = 1$ if $v_j
\notin S$ and $g_j = 0$ if $v_j \in S$.

\begin{proposition}  \label{fxCondition}
The partition $(S, T)$ of $V(G)$ is even if and only if
$L(G)\vec{v}(S) = \vec{0}$.
\end{proposition}

%\begin{proof}
\noindent
{\it Proof.}
Suppose that
$b = L(G)\vec{v}(S) \in \F_2^k$ and $b = (b_1, \dots, b_n)$.
Then we have
\begin{align*}
b_j =& \sum_{i=1}^k g_i l_{ji}\\
=& d_jg_j+ \sum_{i=1}^k g_i a_{ji}\\
=& g_j \sum_{i=1}^ka_{ji} +  \sum_{i=1}^k g_i a_{ji}\\
=& \sum_{i=1}^k (g_i+g_j)a_{ji}.
\end{align*}

If $v_j \notin S$, then $g_j = 1$ and we have
$b_j = \sum_{i=1}^k (g_i+1)a_{ji}$.
Since $(g_i +1)a_{ji}=1$ if and only if $v_i \in S$ and $\overrightarrow{v_jv_i}\in E$,
 $\sum_{i=1}^k (g_i+1)a_{ji}$ counts the number of neighbors of $v_j$ in $S$.
So $b_j$, which is either 0 or 1, is 0 if and only if $v_j$ has an
even number of neighbors in $S$.

Similarly, if $v_j \in S$, then $g_j = 0$ and we have
$b_j = \sum_{i=1}^k g_ia_{ji}$.
But $\sum_{i=1}^k g_ia_{ji}$ counts the number of edges from $v_j$ to $T$,
since
$g_ia_{ji} = 1$ if and only if $v_i \in T$ and $\overrightarrow{v_jv_i} \in E$.
So $b_j$ is 0 if and only if there are an even number of edges from
$v_j$ to $T$.
\hfill$\Box$
%\end{proof}


Notice, the matrix $L(G)$ is constructed so that the sum of its columns is 0.
This fact in combination with the previous result gives
us a proof that the trivial partition $\(G,\emptyset\)$ is always even.
Furthermore, the rank of $L(G)$ is at most $k-1$, since the vector
$\(1, 1, \cdots, 1\)$ is in the nullspace.

The following theorem which appears as Lemma 2.2 in \cite{fx} is an
immediate corollary of Proposition \ref{fxCondition}.

\begin{corollary}\label{fx1}
Let $G = (V,E)$ be a directed graph, $k = |V|$ and $r=
rank_{\F_2}L(G).$ Then the total number of even partitions of $V$ is
$2^{k-r-1}$. In particular, $G$ is an odd graph if and only if
$r=k-1$.
\end{corollary}

In particular, we see that the number of even partitions must be a power of 2.
By Corollary~\ref{fx1}, counting graphs on $k$ vertices with $2^m$ even
partitions is equivalent to counting
the matrices $L(G)$ which have rank $k-m-1$.
In particular, to
determine the number of odd graphs on $k$ vertices it is
enough to determine the number of $L(G)$ that have rank $k-1$.

In the next section, we determine the number of directed graphs on
$k$ vertices with $2^m$ even partitions for all $k$ and $m$. In
Section~\Undirected\  we consider the case of undirected graphs.


%%%%%%%%%%%%%%%  Directed Graphs  %%%%%%%%%%%%%%%%%%%%%%%555
\vskip 30pt
\addtocounter{section}{1}
\section*{\normalsize \thesection. \  Directed Graphs}
%\label{Directed}
If $G$ is a directed graph on $k$ vertices then the matrix $L(G)$ is
$k\times k$. By the definition of $L(G)$ we see that the sum of its
first $k-1$ columns is equal to the $k$-th column. As a result, the
rank of $L(G)$ is the same as the rank of the $k \times (k-1)$
matrix formed by removing the $k$-th column from $L(G)$. Using this
operation there is a 1-1 correspondence between the $k \times (k-1)$
matrices of rank $k-j$ $(1\le j\le k)$ and the directed graphs with
$2^{k-j}$ even partitions. Thus it suffices to enumerate the $k
\times (k-1)$ matrices over $\F_2$ with given rank. This problem has
been considered in \cite{bm1} and \cite{gr}. For completeness, we
provide a simple proof of the theorem that counts the number of such
matrices of rank $k-1$. We then give a second theorem which treats
the general problem. For each theorem we state the result in both
the language of graph theory and that of matrices over $\F_2$.


We begin by counting the number of $k\times (k-1)$ matrices over
$\F_2$ with rank $k-1$.

\begin{theorem}\label{Dir}
The number of directed odd graphs $G$ on $k$ vertices is
$\prod_{j=0}^{k-2} (2^k - 2^j)$.  This is also the number of $k\times k$
matrices over $\F_2$ that have rank $k-1$ and the sum of the first $(k-1)$
columns is the $k^{\text{th}}$ column.

%Hence the probability that an directed graph is odd is
%$\prod_{j=2}^{k}(1-(\frac{1}{2})^j)$.
\end{theorem}
%\begin{proof}

\noindent
{\it Proof.}
Counting the $k\times k$ matrices over $\F_2$ which have rank $k-1$
and the sum of the first $(k-1)$ columns is the $k^{\text{th}}$
column is simply the number of ways of selecting $k-1$ independent
vectors over $(\F_2)^k$. Once we have selected the first $k-1$
columns of the matrix the final column is determined since it is the
sum of the previous $k-1$ columns. Now an ordered set of one
linearly independent vector is just a single nonzero vector, of
which there are $2^k-1$ of length $k$ over $\F_2$.  Now, assume that
there are $$\prod_{j=0}^{m-1} (2^k - 2^j)$$ ordered sets of $m$
linearly independent vectors of length $k$.  To extend this ordered
set to an ordered set of $m+1$ linearly independent vectors, we must
append a vector which is not in the span of the first $m$ vectors.
Since every vector in this span has the form $\sum_{j=0}^m c_jv_j$,
where $c_j \in \F_2$, and each choice of $c_j$'s corresponds to a
unique vector in the span, there are $2^m$ vectors in the span. Thus
there are $2^k-2^m$ vectors which are independent with the first
$m$, and therefore there are $2^k-2^m$ choices for the ($m+1$)st
vector.  Thus there are
$$\prod_{j=0}^{m} (2^k - 2^j)$$ ordered sets of $m+1$ linearly
independent vectors.  The following is therefore true by induction:
There are exactly $$\prod_{j=0}^{k-2} (2^k - 2^j)$$ linearly
independent ordered sets of $k-1$ vectors of length $k$.
\hfill$\Box$
%\end{proof}

It remains to find the number of graphs on $k$ vertices that have
$2^j$ even partitions where $j >0$. Theorem 1.1 from \cite{bm1}
gives the number of $(n+\Delta) \times n$ matrices over $\F_2$ that
have a given rank for all $n$ and $\Delta \ge 0$. We now give this
result in terms of graphs.

\begin{theorem}\label{GenDir}
Suppose that $0 \le j \le k-1$.
Let $J(k,j)$ denote the number of directed graphs $G$ on $k$ vertices
that have $2^{j}$ even partitions.  Then $J(k,j)$ is also the number of
$k\times (k-1)$ matrices over $\F_2$ that have rank $k-1-j$ and
\begin{equation*}
J(k,j) = \frac{2^{(k-1)^2} (2^k-1)\prod_{i=j+1}^{k-1}\left[1-(1/2)^{i}\right]^2}
              {2^{j^2} (2^{j+1}-1)\prod_{i=1}^{k-1-j}\left[1-(1/2)^{i}\right]}.
\end{equation*}
%% $$ J(k, j) = \frac{2^{k(k-1)}}{2^{(j+1)j}}
%% \left[\begin{matrix}k-1 \\ j \end{matrix}\right]
%% \frac{\prod_k(1/2)}{\prod_{j+1}(1/2)}
%% $$
%% where \begin{displaymath} \left[\begin{matrix}n \\ j \end{matrix}\right] =
%% \frac{\prod_n (1/2)}{\prod_j(1/2) \prod_{n-j}(1/2)}
%% \end{displaymath}
%% and $\prod_{n}(1/2) = (1-1/2)\dots (1-(1/2)^n)$.
\end{theorem}

Taking $j=0$ in Theorem \ref{GenDir}, we see that
the number of odd
graphs on $k$ vertices is given by
\begin{equation*}
\begin{aligned}
2^{(k-1)^2}(2^k-1)\prod_{i=1}^{k-1}\left[1-(1/2)^{i}\right]
&=& (2^k-1) \prod_{i=1}^{k-1}\left[ 2^{k-1} - 2^{k-1-i}  \right]  \\
&=& \frac{1}{2^{k-1}} \prod_{i=0}^{k-1}\left[2^k - 2^i \right]  \\
\end{aligned}
\end{equation*}
which is consistent with Theorem \ref{Dir}.


We easily obtain the proof of Theorem \ref{thm:DIRECTED}.

%\begin{proof}[Proof of Theorem \ref{thm:DIRECTED}]
\noindent
{\it Proof. (of Theorem \ref{thm:DIRECTED})} 
We note that the total number of directed graphs on $k$ vertices is
$2^{k(k-1)}$ and invoke Theorem \ref{GenDir}.
\hfill$\Box$
%\end{proof}




%%%%%%%%%%% Undirected Graphs %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vskip 30pt
\addtocounter{section}{1}
\section*{\normalsize \thesection. \  Undirected Graphs}%
%\label{Undirected}
As mentioned after the statement of Theorem \ref{Thm2.4} we will be
interested in determining the number of odd undirected graphs.
Counting the number of odd undirected graphs is a bit more difficult to handle than was the case for directed graphs.
%It is
%a bit more difficult to count the number of undirected graphs that are
%odd, than to count the number of directed graphs that are odd.
We will again proceed by counting the number of graphs $G$ on $k$
vertices for which the matrix $L(G)$ has rank $k-1$. To do this we
require the following lemma.

\begin{lemma} \label{*reduction}
Let $G$ be an undirected graph on $k$ vertices. Let $L(G)$ be defined
as before.
%Then $L(G)$ will have rank $r$ if and only if the matrix
Define
$L^*(G) = \(l_{ij}\)_{1\le i, j \le k-1}$.
Then $\rk(L(G))=\rk(L^{*}(G))$.
\end{lemma}

%\begin{proof}
\noindent
{\it Proof.}
We recall from the definition of $L(G)$ that the $k$-th column is just
the sum of the first $k-1$ columns.  Since, for undirected graphs,
$L(G)$ is symmetric, we also have that the $k$-th row of $L(G)$ is the
sum of the first $k-1$ rows.  By performing a sequence of elementary
row operations, we can replace the $k$-th row of $L(G)$ by the sum of
all rows. This will have the effect of replacing the $k$-th row of
$L(G)$ by a zero row. (Recall that we are considering $L(G)$ to be a
matrix over $\F_2$.)  We can then perform a sequence of elementary column
operations to replace the $k$-th column of $L(G)$ by the sum of all columns.
This will have the effect of zeroing the $k$-th column of our matrix.
Since none of these operations change the rank of our matrix, the
resulting matrix will have the same rank as $L(G)$.
However, the resulting matrix has only zeros in its $k$-th row and
column and has $(1,1)$-minor equal to $L^*(G)$. Thus the rank of this
matrix is the same as that of $L^*(G)$.
\hfill$\Box$
%\end{proof}

We note that the $^*$ operator gives a 1-1 correspondence between
the set of all $L(G)$ as $G$ varies over all undirected graphs on
$k$ vertices and the set of $(k-1)\times (k-1)$ symmetric matrices.
To see this, note that if we are given any  $(k-1)\times (k-1)$
symmetric matrix $A = \(a_{ij}\)_{1\le i,j \le (k-1)}$, we can
define $a_{ik} = a_{ki} = \sum_{j=1}^{k-1} a_{ij}$ and $a_{kk}
=\sum_{j=1}^{k-1} a_{kj}$ and let $A_{*}= \(a_{ij}\)_{1\le i, j \le
k}$.  Then $A_{*}$ is a symmetric $k\times k$ matrix whose $k$-th
column is equal to the sum of its first $k-1$ columns.  Thus there
is an undirected graph $G$ on $k$ vertices such that $L(G)=A_{*}$.
Also, $(A_{*})^* =A$ and $(L(G)^*)_{*}=L(G)$.

So to count
undirected graphs on $k$ vertices with a given number of even partitions,
it suffices to count
symmetric $(k-1)\times (k-1)$ matrices with a given rank.
% The case of counting the number of
% $n\times n$ symmetric matrices over $\F_2$ with rank $n$ has been
% treated before.
Brent and McKay \cite{bm2} determined the number of $n\times n$
symmetric matrices over $\F_2$ with rank $n$.  %We give a similar
%argument to count these matrices.
We extend their results to count the number of matrices with
prescribed rank. Throughout the section we give the results in terms
of graph theory as well as in terms of matrices.

\vskip 20pt
\addtocounter{subsection}{1}
\subsection*{\normalsize \thesubsection \  Number of Odd Graphs on $k$ Vertices}
We begin by counting the number of odd graphs
on $k+1$ vertices.  To do this we will
count the number of $k \times k$ invertible symmetric matrices.
The next two lemmas will allow us to give a recursive formula for the
probability that such a symmetric matrix is invertible.


\begin{lemma}\label{lemma1}
Suppose $A= \(a_{ij}\)_{1\le i,j\le k}$ is a symmetric $k\times k$ matrix
over $\F_2$ and
that $a_{11} = 1$.
Additionally, let $\Lambda = \(\lambda_{ij}\)_{1\le i,j\le k}$ with
\begin{equation*}
\lambda_{ij} = \begin{cases} 1 & \mbox{ if  $i=j$,} \\
                      a_{1j} & \mbox{ if  $i = 1$,} \\
                     0  & \mbox{ otherwise.}
\end{cases}
\end{equation*}
Then
\begin{equation*}
\Lambda^T A \Lambda =
\begin{pmatrix} 1 & 0 & 0 & \ldots & 0 \cr
         0  & b_{11} & b_{12} & \ldots & b_{1(k-1)}\cr
        \vdots &\vdots & \vdots &\ddots &\vdots \cr
       0  & b_{(k-1)1} &  b_{(k-1)2} & \cdots & b_{(k-1)(k-1)}
\end{pmatrix}
\end{equation*}
where the matrix
$B = \(b_{ij}\)_{1\le i,j\le (k-1)}$ is a symmetric $(k-1) \times (k-1)$ matrix.
Furthermore, if $A$ is random then so is $B$.
\end{lemma}

%\begin{proof}
\noindent
{\it Proof.}
Multiplying out, we see that $\Lambda^T A \Lambda$ has the desired
form. Furthermore, $$b_{ij} = a_{1(i+1)}a_{1(j+1)}+a_{(i+1)(j+1)}.$$
Thus $b_{ij} = b_{ji}$, so that $B$ is symmetric. It also follows from this formula that if the first row and column of $A$ are held fixed, then the the lower right $(k-1) \times (k-1)$ submatrix of $A$ completely determines $B$. Thus, if $A$ is
chosen uniformly from the set of all symmetric matrices then so will
$B$ be.
\hfill$\Box$
%\end{proof}


\begin{lemma}\label{lemma2}
Suppose $A= \(a_{ij}\)_{1\le i,j\le k}$ is a symmetric $k\times k$ matrix
over $\F_2$, $a_{11} = 0$ and $a_{12} = 1$.
Additionally, let
$\Gamma = \(\gamma_{ij}\)_{1\le i,j\le k}$ with
\[\gamma_{ij} = \begin{cases} 1 & \mbox{ if  $i=j$} \\
                            a_{1j} & \mbox{ if  $i = 2$} \\
                                                a_{2j}+a_{22}a_{1j} &\mbox{ if $i = 1$}\\
                                                0  & \mbox{ otherwise}   \end{cases} .
\]
Then \[\Gamma^T A \Gamma =
\begin{pmatrix} 0 & 1 & 0 & \ldots & 0 \cr
                             1  & a_{22} & 0 & \ldots 0\cr
                             0  & 0 & c_{11} & \ldots & c_{1(k-2)}\cr
                            \vdots &\vdots & \vdots &\ddots &\vdots \cr
                            0  & 0 &  c_{(k-2)1} & \cdots & c_{(k-2)(k-2)}
                                                                     \end{pmatrix}
\]
where the matrix
$C = \(c_{ij}\)_{1\le i,j\le (k-2)}$ is a symmetric $(k-2)\times (k-2)$ matrix.
Furthermore, if $A$ is random then so is $C$.
\end{lemma}

%\begin{proof}
\noindent
{\it Proof.}
The proof is similar to the proof of the previous lemma. Doing the
multiplication we see that the matrix has the desired form and that
$c_{ij} = a_{1(i+2)}a_{2(j+2)}+
a_{1(j+2)}a_{2(i+2)}+a_{22}a_{1(i+2)}a_{1(j+2)}+a_{(i+2)(j+2)}$. So
$C$ is a symmetric matrix.   As above, the formula implies that if the first row and column of $A$ are held fixed, then the the lower right $(k-2) \times (k-2)$ submatrix of $A$ completely determines $C$.  Thus if $A$ is
chosen uniformly from the set of all symmetric matrices, then so
will $C$ be.
\hfill$\Box$
%\end{proof}

The following theorem now gives us a recursion for the probability
that a graph on $k+1$ vertices is odd.

\begin{theorem}\label{probRecursion}
Let $p(k)$ be the probability that a random $k\times k$ symmetric
matrix over $\F_2$ is invertible. Then
\begin{equation}\label{recursion}
p(k) = \frac{1}{2}\(p(k-1) +
\(1-\(\frac{1}{2}\)^{k-1}\)p(k-2)\)
\end{equation}
for $k\ge 2$. We define $p(0) = 1$, and we have $p(1) = 1/2$.

This recursion gives
\begin{align} \label{ProbabilityFormula}
p(2n) =& p(2n-1)\\  \nonumber
p(2n-1) =& \(1-\(\frac{1}{2}\)^{2n-1}\)p(2n-2)
\end{align}
for all $n\ge 1$.
\end{theorem}

%\begin{proof}
\noindent
{\it Proof.}
We begin by deriving (\ref{recursion}).  Let $A$ be a random
symmetric $k\times k$ matrix with $k \ge 2$.
%Throughout the proof we use the fact that $A$
%is invertible if and only if $\det(A) \ne 0$.
We derive the recursion by calculating the probability that $A$ is invertible in each of the two cases $a_{11} = 1$ and $a_{11} = 0$. Since these cases are equally likely, we then average their respective conditional probabilities to find $p(k)$.

First suppose $a_{11} = 1$.
With the notation of Lemma \ref{lemma1} and using the fact
$\det(\Lambda )= \det( \Lambda^T )= 1$, we see that $\det(A)  =
\det(\Lambda^T A \Lambda) = \det(B).$ Since $A$ was random, $B$ is a
random symmetric $(k-1)\times (k-1)$  matrix. Hence, if $a_{11} = 1$
then the probability that $A$ is invertible is $p(k-1)$.

Next suppose that $a_{11} = 0$.  If $a_{1j} = 0$ for all $j$, then
$\det(A) = 0$, and $A$ is not invertible. Suppose that there exists
at least one $j \ne 1$ such that $a_{1j} \ne 0$.  This happens with
probability $\(1-\(\frac{1}{2}\)^{k-1}\)$.  Switching the
$j^{\text{th}}$ column with the $2^{\text{nd}}$ column and switching
the $j^{\text{th}}$ row with the $2^{\text{nd}}$ row keeps $A$ a
symmetric matrix.  Furthermore, whether or not the determinant is 0
is not changed.  Thus we may assume without loss of generality that
$a_{12} = 1$. With the notation of Lemma \ref{lemma2} and using the
fact $\det(\Gamma)= \det(\Gamma^T)= 1$, we see that $\det(A) =
\det(\Gamma^T A \Gamma) = \det(C).$ Since $A$ was random $C$ is a
random symmetric $(k-2)\times (k-2)$  matrix. Hence, if $a_{11} = 0$
then the probability that $A$ is invertible is
$\(1-\(\frac{1}{2}\)^{k-1}\) p(k-2)$. Averaging these two
probabilities gives (\ref{recursion}).

We will now prove (\ref{ProbabilityFormula}) by using
(\ref{recursion}) and induction. Suppose for some $n$ that
\begin{align*}
p(2n) =& p(2n-1)\\
p(2n-1) =& \(1-\(\frac{1}{2}\)^{2n-1}\)p(2n-2).
\end{align*}
This is easily verified for small $n$. Then by (\ref{recursion}) we
have
\begin{align}\label{eq1}
p(2n+1) =&  \frac{1}{2}\(p(2n) +
\(1-\(\frac{1}{2}\)^{2n}\)p(2n-1)\) \\
=& \frac{1}{2}\(1+\(1-\(\frac{1}{2}\)^{2n}\)\) p(2n) =
\(1-\(\frac{1}{2}\)^{2n+1}\)p(2n),\nonumber
\end{align}
as desired.

Now using (\ref{eq1}) we have
\begin{align*}
p(2n+2) =& \frac{1}{2}\(p(2n+1) +
\(1-\(\frac{1}{2}\)^{2n+1}\)p(2n)\) \\
=& \frac{1}{2}\(p(2n+1)+p(2n+1)\)\\
=& p(2n+1).
\end{align*}
This completes the proof.
\hfill$\Box$
%\end{proof}

The following theorem is an immediate consequence of the previous
theorem and the discussion at the opening of this section.

\begin{corollary}\label{probGraphOdd}
Let $G$ be an undirected graph on $k$ vertices. 
The probability that $G$ is odd is $$q(k) = \prod_{j=1}^s
\(1-\(\frac{1}{2}\)^{2j-1}\)$$ where $s = \lfloor \frac{k}{2}\rfloor.$
Hence there are $2^{\binom{k}{2}} q(k)$ odd graphs on $k$ vertices.
\end{corollary}

%\begin{proof}
\noindent
{\it Proof.}
From the discussion above and in the notation of Theorem
\ref{probRecursion} we see that
$q(k) = p(k-1)$. Also,
using the second set of recursions in Theorem \ref{probRecursion}, it is easy to deduce that
$p(k-1) =  \prod_{j=1}^s
\(1-\(\frac{1}{2}\)^{2j-1}\)$ where $s = \lfloor \frac{k}{2}\rfloor.$
\hfill$\Box$
%\end{proof}


\addtocounter{subsection}{1}
\subsection*{\normalsize \thesubsection \ Number of Even Partitions of a Graph}
Using the same kinds of ideas that we used to derive the number of odd graphs
on $k$ vertices,
we can determine the number of graphs on $k$ vertices that have $2^n$ even partitions, for any $n$.
Again, we can use Corollary \ref{fx1} and Lemma \ref{*reduction},
to reduce the problem to finding how many
graphs on $k$ vertices have $k-n-1 = \rk(L(G))=\rk(L^{*}(G))$.
In the above discussion we found
the number of graphs with $2^0$ distinct even partitions and hence
the number of $L^{*}(G)$ with rank $k-1$.


Let $I(k, r)$ be the number of $k \times k$ symmetric matrices of rank $r$ over $\F_2$.
Then in the previous section we showed that $$I(k,k) =2^{\binom{k+1}{2}}  \prod_{j=1}^s
\(1-\(\frac{1}{2}\)^{2j-1}\)$$ where $s = \lfloor \frac{k+1}{2}\rfloor.$

Now, using this result and the following theorem, we can calculate $I(k,r)$ explicitly.

\begin{theorem}\label{thm:GenUnDir}In the notation above,
$I(n,n-j) = d(n,j)I(n-j,n-j),$
where $d(n,j)$ is the number of $j$ dimensional subspaces of $\F_2^n$
and $$d(n,j) = \prod_{i=0}^{j-1}\frac{2^n-2^i}{2^j - 2^i}.$$
\end{theorem}

%\begin{proof}
\noindent
{\it Proof.}
We will prove this theorem in three steps.

\noindent {\it Step 1.}  As usual, let $e_i = (\underbrace{0,\dots, 0}_{i-1
\text{ times}}, 1, 0, \dots, 0)^T\in \F_2^n$ and $E = \text{span
}\{e_{1}, \ldots, e_{j}\}$. Then we will show that there are $I(n-j,
n-j)$ matrices $A$ of size $n\times n$ with rank $n-j$ and Null($A)
= E$.

To see this we begin by noting that $Ae_m$ is the $m^{\text{th}}$ column
of the matrix $A$.
Therefore, if $A$ is a symmetric matrix with $Ae_m = \vec{0}$ then the
$m^{\text{th}}$ column and row of $A$ must be zero.  Furthermore, $A$ has rank $n-j$ if and only if
$n-j$ of the column vectors are independent.

Let $A$ be a symmetric $k\times k$ matrix with rank $n-j$ that takes
$E$ to zero.  Since the first $j$ columns of $A$ are zero,
if $A$ has rank $n-j$ we must have that the final $n-j$ column vectors
 of $A$ are linearly independent.
Since the first $j$ rows of $A$ are also all zero, $A$ will send
$e_1, \ldots, e_j$ to $\vec{0}$ and have rank $n-j$ if and only if
the symmetric $(n-j) \times (n-j)$ submatrix $\hat{A} =
\(a_{ij}\)_{(j+1)\le i, j\le n}$ has linearly independent column
vectors, that is, if and only if $\hat{A}$ is invertible. Therefore,
there are $I(n-j,n-j)$ symmetric $n \times n$ matrices of rank $n-j$
that send $e_1,\ldots, e_j$ to $\vec{0}$.



\noindent {\it Step 2.} Let $S$ be any $j$ dimensional subspace with
basis $\{v_1, \cdots, v_j\}$. Also let $\cS = \{$ all $n\times n$
symmetric matrices of rank $n-j$ that take $S$ to zero$\}$ and let
$\cE = \{$ all $n\times n$ symmetric matrices of rank $n-j$ that
take $E$ to zero$\}$. We will show that there is a 1-1 map from
$\cS$ onto $\cE$, so that these sets have the same size.

We will demonstrate the 1-1 onto map as follows.
There exist $k_1, \dots, k_{n-j}$ such that $\{v_1, \dots, v_j,$ $e_{k_1}, \dots, e_{k_{n-j}}\}$
is a basis for $\F_2^n$.  Let $B$ be the change of basis matrix such that
$e_s \mapsto v_s$ for $1\le s\le j$ and $e_{j+t} \mapsto e_{k_t}$ for $1\le t\le (n-j)$.

Define the map $\phi : \cS \to \cE$ by $\phi(A) = B^TA B$.  Since $B$ is invertible,
so is $B^T$.  Thus,
$B^TABv = \vec{0}$ if and only if $ABv=\vec{0}$.  But $ABv=\vec{0}$ if and only if
$Bv \in S$.  Since $B$ is the change of basis matrix from $\{e_1, \ldots, e_j\}$ and
$\{v_1,\ldots, v_j\}$ we have $B^TABv = \vec{0}$ if
and only if $v \in E$.  Therefore, the map is well-defined onto the spaces indicated.
Furthermore, $\phi$ is 1-1 and onto, since $B$ and $B^T$ are both invertible.
%To show that
%$\phi$ is onto let $X \in \cE$ be arbitrary and $Y = (B^T)^{-1} X B^{-1}$.  Since
%$\phi(Y) = B^T YB = B^T (B^T)^{-1} X B^{-1} B = X$, it is enough to show that $Y \in \cS$.
%Since $B^T$ is invertible $Yv = \vec{0}$ if and only if $XB^{-1}v = \vec{0}$.  Furthermore,
%since $X \in \cE$,  $XB^{-1}v = \vec{0}$ if and only if $B^{-1}v \in E$.  But
%$B^{-1}$ is the change of basis matrix from $\{v_1, \ldots, v_j\}$ to
%$\{e_1,\ldots, e_j\}$, thus $Yv = \vec{0}$ if and only if $v \in S$.  So $Y \in \cS$.

 Additionally if $A$, a
symmetric $n\times n$ matrix over $\F_2$, has rank $n-j$ then it has
a null space of dimension $j$. That is $\text{Null}(A) = S$ for some
$j$ dimensional subspace $S$. There are $d(n,j)$ such choices for
$S$. So this step completes the proof that $I(n,n-j) =
d(n,j)I(n-j,n-j)$. The final step in the proof is to compute
$d(n,j)$.



\noindent {\it Step 3.}  There are $\prod_{i=0}^{j-1} (2^n - 2^i)$
ways to choose $j$ linearly independent vectors from $\F_2^n$.
Also, for any subspace of $\F_2^n$ of dimension $j$ there are
$\prod_{i=0}^{j-1} (2^j - 2^i)$ different bases for that subspace.
Hence, the total number of subspaces of $\F_2^n$ of dimension $j$ is
$\prod_{i=0}^{j-1} \frac{2^n - 2^i}{2^j - 2^i}$.
\hfill$\Box$
%\end{proof}

\noindent
{\em Proof of Theorem \ref{thm:UNDIRECTED}.}  We note that
the number of undirected graphs on $k$ vertices with $2^{n}$ even partitions
is given by
\begin{eqnarray*}
I(k-1,k-1-n) &=& d(k-1,n) \cdot I(k-1-n,k-1-n) \\
&=& d(k-1,n)\cdot
2^{\binom{k-n}{2}}  \prod_{j=1}^s
\(1-\(\frac{1}{2}\)^{2j-1}\),
\end{eqnarray*}
where $s = \lfloor \frac{k-n}{2}\rfloor.$
Theorem \ref{thm:UNDIRECTED} follows immediately.
%\qed

The following table gives the values for the number of even partitions
of a graph for some
small graphs. Each entry gives the number of undirected graphs on $k$ vertices with
$m$ distinct even partitions.
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|}
\hline
$k\backslash m$ & 1 &2 &4 &8 \\
\hline
%0 &1 & & & & \\
1 &1 & & &  \\
2 &1 &1 & &  \\
3 &4 &3 &1 &  \\
4 &28 &28 &7 &1 \\
\hline

\end{tabular}
\end{center}

\vskip 20pt
\addtocounter{section}{1}
\section*{\normalsize \thesection. \ The Random Model for $E_n$}%
%\label{CONJECTURE}
In our discussion after Theorem \ref{Thm2.4}, we explained that for
each graph $G(n)$ with $n\equiv \pm 3 \mymod{8}$, if $n$ satisfies
the first two conditions of the theorem, then $G(n)$ is an
undirected graph.  In the previous section we computed the
probability that an undirected graph on $k$ vertices is odd.  We would like to think of the graph $G(n)$ as being a random
graph, and hence be able to deduce the probability that the elliptic
curve $E_n$ has trivial Selmer groups.


Theorem \ref{Thm2.4} shows that for each $n=p_1 \cdots p_k \equiv
3\mymod{8}$, the fact that $s(n)=0$ depends only on the congruence
classes of each $p_j$ modulo 8 and the values of
$\(\frac{p_i}{p_j}\)$.   Thus if these are independent as we vary
over all possible sets of primes, then we may deduce that the random
model is the appropriate one. More precisely we are led to the
following notation. Let $S_{k}(X)$, be defined as in equation
(\ref{eqn:eligibleNums}), so $S_{k}(X)$ is the set of all $n\equiv
\pm 3\mymod{8}$ with $n<X$ such that $n$ also satisfies the first
two conditions of Theorem \ref{Thm2.4}. Let
$$G(S_k(X)) = \(G(n): n\in S_k(X)\),$$ where this list contains each
graph with multiplicity. That is, the set $G(S_3(X))$ may contain
more than one copy of any particular graph.

In fact, as mentioned earlier each undirected graph on $k$ vertices
will appear infinitely often as $X\to \infty$.  Thus for large
enough $X$, $G(S_k(X))$ must contain more than one copy of any
particular graph.  We would like to be able to conclude that as
$X\to \infty$ each of the $2^{k(k-1)/2}$ undirected graphs appears
equally often in the set $G(S_k(X))$. %Then if we combine the
%findings of \cite{fj} with the main results of this paper, we can
%develop a family of conjectures describing the proportion of a
%family of square-free integers which have Selmer groups of a certain
%size.  The simplest of these conjectures follows:
%\begin{conjecture}
%Let $k$ be fixed and consider $S_k(X)$, the set of all $n\equiv 3
%\mymod{8}$ such that $n=p_1 p_2 \cdots p_k$ with $p_1\equiv
%3\mymod{4}$ and $p_j\equiv 1\mymod{4}$ for $j>1$.  Then as $X\to
%\infty$ for $n\in S_k(X)$, the probability that $E_n$ has trivial
%Selmer groups is $q(k) = \prod_{j=1}^s
%\(1-\(\frac{1}{2}\)^{2j-1}\),$ where $s=\lfloor \frac{k}{2}\rfloor$.
%\end{conjecture}

For $k=2,3,4$ we have $q(k) = 1/2, 1/2, 7/16 =
.4375$, respectively. Thus, if the random model is correct, we would expect the
proportion of $n\in S_k(X)$ such that $G(n)$ is odd to approach
$q(k)$.  We tested this conjecture computationally for $k=2,3,4$.  
The results are presented in Figures 
\ref{2primeNumbers}, \ref{3primeNumbers} and \ref{4primeNumbers} below.  
Although these computations are not extensive enough to be conclusive, they do seem to suggest that the conjecture
is true for $k=2$ and that it possibly holds for $k=3,4$ as well.

\begin{figure}[!htbp]
\begin{center}
\begin{tabular}{c r r c}
$X$ & Number with $G(n)$ odd & $|S_{2}(X)|$ &Proportion\\
\hline
$10^6$ & 21207 &42045 & 0.504388 \\
$10^7$ & 195391 & 388944 & 0.502363\\
$10^8$ & 1806154 & 3606013 &0.500873\\
$10^9$ & 16815798  & 33606444&$0.500374$  \\
$10^{10}$ & 157413227&314705475&$0.500192$ \\
$10^{11}$ & 1480332478& 2960087660&$0.500098$ \\
\end{tabular}
\end{center}
\caption{generated from products of two primes not greater than $X$.
\label{2primeNumbers}}
\end{figure}

\begin{figure}[!htbp]
\begin{center}
\begin{tabular}{c r r c}
$X$ & Number with $G(n)$ odd & $|S_{3}(X)|$ &Proportion\\
\hline
$10^6$ &   11291&19810 & 0.569965 \\
$10^7$ & 118637& 214556 & 0.552942\\
$10^8$ & 1211721 &2241087 & 0.540685\\
$10^9$ &  12215739& 22901580 &0.533402  \\
$10^{10}$ & 122070712&231002932& 0.528438 \\
$10^{11}$ & 1213147587& 2311247337& 0.524889 \\
$10^{12}$ & 12012228025&23002085447   &0.522223
\end{tabular}
\end{center}
\caption{products of three primes not greater than $X$.
\label{3primeNumbers}}
\end{figure}


\begin{figure}[!htbp]
\begin{center}
\begin{tabular}{c r r c}
$X$ & Number with $G(n)$ odd & $|S_{4}(X)|$ &Proportion\\
\hline
$10^6$ & 1402 &2709 & 0.517534 \\
$10^7$ & 19864& 39896 & 0.497895\\
$10^8$ & $248032$ &514136 & 0.482425\\
$10^9$ &  2906818& 6137321 &$0.473630$  \\
$10^{10}$ & 32641358& 69830762&$0.467435$ \\
$10^{11}$ & 356306278& 769488112&$0.463043$ \\
$10^{12}$ &3813142242 & 8293523085  &0.459774
\end{tabular}
\end{center}
\caption{products of four primes not greater than $X$.
\label{4primeNumbers}}
\end{figure}


One possible approach to showing that each graph appears with equal
probability as $X\to \infty$ would be to show that each edge
$\overline{p_ip_j}$ appears with probability $1/2$.  We expect this
probability to be about $\frac{1}{2}$, since the existence of an
edge between the vertices corresponding to the primes $p_i$ and
$p_j$ is entirely dependent on whether $(\frac{p_i}{p_j})$ is 1 or
$-1$. Furthermore, each possibility occurs for half of the
congruence classes modulo $p_j$. Actually, since we are putting an
extra restriction on $p_i$, it is necessary to look at which
congruence class $p_i$ falls in modulo $8p_j$. This distinction
makes no real difference, since each of the two possible values for
$(\frac{p_i}{p_j})$ still occurs for exactly half of the allowed
congruence classes modulo $8p_j$.

Dirichlet's theorem says that there are infinitely many primes in
any arithmetic progression $\{8p +a\}_{k\in \N}$ for each $a$ that
is relatively prime to $8p$ and there are the same density of primes
in the set $\{8p+a\}$ for each $a$. Since $(\frac{a}{p})$ is 1 for
half of the allowable $a$'s relatively prime to $8p$, it is
reasonable to suspect that each edge on $G(n)$,
for some $n$ with $k$ prime factors, appears with probability $1/2$.
Furthermore, if each edge appears with probability $1/2$, then each
graph appears equally likely. 



\vskip 10pt
\section*{\normalsize Acknowledgments}
\vspace*{-10pt}
This research took place during the 2004 REU at Clemson University.
The authors are thankful for useful discussions with Bryan Faulkner;
sixth author is also thankful for useful discussions with Pamela
Gorkin and Jeremy Rouse.  We are grateful to the referee for making
several helpful corrections and very useful suggestions that
greatly improved this paper.



\renewcommand{\refname}{\normalsize References}
\begin{thebibliography}{99} \footnotesize \baselineskip=11pt \parskip=2pt

\bibitem[BM1]{bm1} R. P. Brent and B. D. McKay, \emph{ Determinants of and rank of random
matrices over $\Z_m$}, {\it Discrete Math.}, {\bf 66} (1987) 35 - 49.

\bibitem[BM2]{bm2} R. P. Brent and B. D. McKay, \emph{ On determinants of random
symmetric matrices over $\Z_m$}, {\it ARS Combinatoria}, {\bf 26A}
(1988) 57 - 64.

%\bibitem[DAV]{Davenport}Davenport, Harold. {\it Multiplicative Number Theory},
%     Third Edition (Revised by Hugh L. Montgomery), Springer, New York, 1994.

\bibitem[FJ]{fj} B. Faulkner and K. James {\it A graphical approach to
                 computing Selmer groups of congruent number curves},
                 (preprint).

\bibitem[FX]{fx} K. Feng and M. Xiong, \emph{On elliptic curves $y^2 =
x^3 - n^2x$ with rank zero}, {\it J. Number Theory}, {\bf 109} (2004), no. 1, 1 - 26.

\bibitem[GR]{gr} J. Goldman and G.-C. Rota, \emph{ On the foundations of combinatorial theory IV:
Finite vector spaces and Eulerian generating functions}, {\it Stud.
Appl. Math}. 49(3) (1970) 239 - 258.

\bibitem[HB1]{hb1} D. R. Heath-Brown,
\emph{The size of Selmer groups for the congruent number problem}, {\it Invent. Math}.
{\bf 111} (1993), no.1, 171-195.

\bibitem[HB2]{hb2}
D.R. Heath-Brown, {\it The size of Selmer groups for the congruent
number problem. II}. Invent. Math. 118 (1994), no. 2, 331--370

\bibitem[K]{k} N. Koblitz, {\it Introduction to elliptic curves and
               modular forms}, Springer-Verlag, 1984.

\bibitem[JO]{JO}
K. James and K. Ono, {\it Selmer groups of quadratic twists of elliptic
curves}. Math. Ann. 314 (1999), no. 1, 1-17.

\bibitem[R1]{r1} K. Rubin, \emph{Tate-Shafarevich group and
$L$-functions of elliptic curves with complex multiplication},
Invent. Math. {\bf 89} (1987), 527 - 560.

\bibitem[R2]{r2} K. Rubin, \emph{The main conjecture for imaginary
quadratic fields}, Invent. Math. {\bf 103} (1991), 25 - 68.
%\bibitem[SAT]{sat} L. G. Sathe, \emph{ On a problem of Hardy on the
%distribution of integers having a given number of prime factors I},
%{\it J. Indian Math. Soc.}. {\bf 17} (1953) 63-82.\

%\bibitem[SEL]{sel} A. Selberg, \emph{ Note on a paper by L. G. Sathe},
%{\it J. Indian Math. Soc.}. {\bf 18} (1954) 83-87.

\bibitem[S]{sil} J. Silverman {\it The arithmetic of elliptic curves},
Grad. Texts in Math. 106, Springer, 1986.

\bibitem[Y]{GY}
G. Yu, \emph{Average size of 2-Selmer groups of elliptic curves,
II}, Acta Arith. 117 (2005), no. 1, 1-33

\end{thebibliography}


\end{document}