\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

%\usepackage{setspace}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}


\begin{center}
\vskip 1cm{\LARGE\bf Counting the Regions in a\\
\vskip .1in
Regular Drawing of $K_{n,n}$}
\vskip 1cm
\large
Martin Griffiths\\
School of Education\\
University of Manchester\\
Manchester\\
M13 9PL\\
United Kingdom\\
{\tt  martin.griffiths@manchester.ac.uk}
\end{center}

\vskip 0.2 in

\begin{abstract}
We calculate here both exact and asymptotic formulas for the number of
regions enclosed by the edges of a regular drawing of the complete
bipartite graph $K_{n,n}$.  This extends the work of Legendre, who
considered the number of crossings arising from such a graph.  We also
show that the ratio of regions to crossings tends to a rational
constant as $n$ increases without limit.
\end{abstract}

\section{Introduction}
A graph $G$ is called \textit{bipartite} if its vertex set can be partitioned into two parts, $A$ and $B$ say, such that every edge of $G$ has one end in $A$ and the other in $B$; see \cite{cameron} or \cite{dolan}, for example.  In a \textit{complete bipartite graph}, denoted by $K_{a,b}$, each of the $a$ vertices in $A$ is connected via an edge to each of the $b$ vertices in $B$.

In \cite{legendre} the author calculated the number of crossings in a regular drawing of $K_{n,n}$. By  `regular drawing' we mean that parts $A$ and $B$ of the vertex set of $K_{n,n}$ are positioned at coordinates $\{(0,m):m=1,2,\ldots,n\}$ and $\{(1,m):m=1,2,\ldots,n\}$ respectively (or at least have some similar arrangement).  As an example, a regular drawing of $K_{7,7}$ is shown in Figure \ref{k77}.  For the sake of clarity the $x$-axis has been stretched somewhat, but note that this does not alter the number of crossings or regions.

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.91]{mgBipartitePic1.eps}
\caption{A regular drawing of the complete bipartite graph $K_{7,7}$.}
\label{k77}
\end{center}
\end{figure}

 In this article we broaden the scope of the work carried out in \cite{legendre}, and go on to consider the enumeration of the regions enclosed by the edges of a regular drawing of $K_{n,n}$.  We obtain both exact and asymptotic formulas for $r(n)$, the number of regions.  It is also shown that the ratio of regions to crossings tends to a rational constant as $n$ increases without limit.

\section{Some notation and preliminary results}
In preparation for the enumeration of $r(n)$ in the following section, we define here some notation and provide two lemmas.  Let $V_{k,m}$ denote the vertex of $K_{n,n}$ positioned at $(k,m)$, where $k\in\{0,1\}$ and $m\in\{1,2,\ldots,n\}$, and  let $E_{i,j}$ denote the edge of $K_{n,n}$ joining $V_{0,i}$ to $V_{1,j}$.  Two distinct edges, $E_{i,j}$ and $E_{p,q}$, intersect if, and only if, either $1\leq p<i$ and $j<q\leq n$ or $i<p\leq n$ and $1\leq q<j$.

Note that if $E_{i,j}$ and $E_{p,q}$ intersect then we may write $p=i+ka$ and $q=j-kb$ for some non-zero $k\in\mathbb{Z}$ and $a,b\in\mathbb{N}$ such that $\gcd(a,b)=1$.  The point of intersection of $E_{i,j}$ and $E_{p,q}$ is known as an \textit{$(a,b)$ crossing}.  It is straightforward to show that this has coordinates
\[\left(\frac{a}{a+b},\frac{aj+bi}{a+b}\right).\]
For example, we see in Figure \ref{crossing} an $(a,b)$ crossing for which $a=3$, $b=2$, $i=2$, $j=6$ and $k=1$.  The edges $E_{2,6}$ and $E_{5,4}$ intersect at
\[\left(\frac{3}{3+2},\frac{3\cdot 6+2\cdot 2}{3+2}\right)=\left(\frac{3}{5},\frac{22}{5}\right).\]

It is worth mentioning here that there is the possibility for more than two edges to intersect at a particular $(a,b)$ crossing.  Furthermore, $E_{i,j}$ is involved in an $(a,b)$ crossing if, and only if, there exists an edge $E_{p,q}$ such that $p=i+ka$, $q=j-kb$, $\gcd(a,b)=1$ and either $k=1$ or $k=-1$.  Finally, let $N(a,b)$ denote the total number edges of $K_{n,n}$ that are involved in $(a,b)$ crossings.

\begin{figure}[!h]
\centering
\setlength{\unitlength}{1.6cm}
\begin{picture}(4,3.7)(0,0.8)

\put(1.05,3.05){\line(4,-1){2}}
\put(1.05,1.55){\line(1,1){2}}

\put(1.0,1.0){$\bullet$}
\put(1.0,1.5){$\bullet$}
\put(1.0,2.0){$\bullet$}
\put(1.0,2.5){$\bullet$}
\put(1.0,3.0){$\bullet$}
\put(1.0,3.5){$\bullet$}
\put(1.0,4.0){$\bullet$}

\put(3.0,1.0){$\bullet$}
\put(3.0,1.5){$\bullet$}
\put(3.0,2.0){$\bullet$}
\put(3.0,2.5){$\bullet$}
\put(3.0,3.0){$\bullet$}
\put(3.0,3.5){$\bullet$}
\put(3.0,4.0){$\bullet$}

\put(0.4,3.0){$i+a$}
\put(0.8,1.5){$i$}
\put(3.2,3.5){$j$}
\put(3.2,2.5){$j-b$}

\end{picture}
\caption{An $(a,b)$ crossing with $a=3$, $b=2$, $i=2$, $j=6$ and $k=1$.}
\label{crossing}
\end{figure}

\begin{lemma}\label{rlemma}
Let $a,b\in\mathbb{N}$ such that $1\leq a,b<n$ and $\gcd(a,b)=1$.  Then
\begin{displaymath}
N(a,b)=\left\{
\begin{array}{cl}
n^2-2ab, & \quad\textrm{if $n>2\max\{a,b\}$};\\
 2(n-a)(n-b), & \quad\textrm{otherwise}.
 \end{array} \right.
 \end{displaymath}
\end{lemma}

\begin{proof}
Since $N(a,b)=N(b,a)$ by symmetry, we may, without loss of generality, assume that $a\geq b$, so that $\max\{a,b\}=a$.  The set $S$ of edges involved in $(a,b)$ crossings is given by
\[\left\{E_{i,j}:1\leq i\leq n-a\quad\textup{and}\quad b+1\leq j\leq n\right\}\bigcup\left\{E_{i,j}:a+1\leq i\leq n\quad\textup{and}\quad 1\leq j\leq n-b\right\}.\]
Suppose first that $n\leq 2a$.  In this case the two sets on either side of the union are disjoint, and the cardinality of $S$ is thus given by $2(n-a)(n-b)$.

On the other hand, if $n>2a$ then the sets on either side of the union have elements in common. In fact, the set of edges common to both is given by
\[\left\{E_{i,j}:a+1\leq i\leq n-a\quad\textup{and}\quad b+1\leq j\leq n-b\right\}.\]
The cardinality of this set is $(n-2a)(n-2b)$, so that
\begin{align*}
|S|
&=2(n-a)(n-b)-(n-2a)(n-2b)\\
&=n^2-2ab
\end{align*}
in this case, thereby proving the lemma.
\end{proof}

In order to illustrate Lemma \ref{rlemma} it is convenient to consider the $n\times n$ matrix $M_n(a,b)$ with entries $m_{i,j}(a,b)$, $1\leq i,j\leq n$, such that $m_{i,j}=1$ if $E_{i,j}$ is involved in an $(a,b)$ crossing, while $m_{i,j}=0$ otherwise.  We let $M_{sub}(p,q,r,s)$ denote the $(r-p+1)\times(s-q+1)$ submatrix of $M_n(a,b)$ whose top left and bottom right elements are $m_{p,q}(a,b)$ and $m_{r,s}(a,b)$ respectively.

If $n\leq 2a$ we obtain two disjoint submatrices of 1s.  Consider, for example, the matrix $M_5(3,1)$ shown below, in which the disjoint submatrices $M_{sub}(1,2,2,5)$ and $M_{sub}(4,1,5,4)$ of 1s can clearly be seen.  In this case
\begin{align*}
N(a,b)
&=N(3,1)\\
&=2(5-3)(5-1)\\
&=16.
\end{align*}

\begin{equation*}
\left(
\begin{array}{ccccc}
0 & 1 & 1 & 1 & 1\\
0 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 0\\
1 & 1 & 1 & 1 & 0
\end{array}\right)
\end{equation*}

\vskip 0.7cm

For $n> 2a$ the submatrices of 1s overlap.  For example, the matrix $M_7(3,2)$ is given below.  We can see the overlapping submatrices of 1s $M_{sub}(1,3,4,7)$ and $M_{sub}(4,1,7,5)$.  In this case
\begin{align*}
N(a,b)
&=N(3,2)\\
&=7^2-2\cdot3\cdot2\\
&=37.
\end{align*}

\begin{equation*}
\left(
\begin{array}{ccccccc}
0 & 0 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 1 & 1 & 1 & 1 & 1\\
1 & 1 & 1 & 1 & 1 & 1 & 1\\
1 & 1 & 1 & 1 & 1 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 0 & 0
\end{array}\right)
\end{equation*}

\vskip 0.7cm

\begin{lemma}\label{clemma}
The number $c(n)$ of crossings in a regular drawing of the complete bipartite graph $K_{n,n}$ is given by
\begin{displaymath}
c(n)=\sum_{\substack{1 \leq a,b < n\\ \gcd(a,b)=1}}\!\!\!\!\!\!(n-a)(n-b)-\!\!\!\sum_{\substack{1 \leq 2a,2b <n\\\gcd(a,b)=1}}\!\!\!\!\!\!(n-2a)(n-2b).
\end{displaymath}
\end{lemma}

\begin{proof}
This appears as one of the main results in \cite{legendre}, a full proof of which is given there.
\end{proof}

With regard to notation, note that the first sum above is taken over all pairs $(a,b)$ such that $1\leq a<n$, $1\leq b<n$ and $\gcd(a,b)=1$, and that it is not necessary that $b\geq a$.  A similar comment applies to the second sum.   The sequence $\{c(n)\}$ appears in Sloane's \textit{On-line Encyclopedia of Integer Sequences} \cite{sloane} as entry A159065.

\section{An exact formula for $r(n)$}
\begin{theorem}\label{rtheorem}
The number $r(n)$ of regions in a regular drawing of the complete bipartite graph $K_{n,n}$ is given by
\begin{displaymath}
r(n)=(n-1)^2+\!\!\!\sum_{\substack{1 \leq a,b <n\\ \gcd(a,b)=1}}\!\!\!\!\!\! (n-a)(n-b).
\end{displaymath}
\end{theorem}

\begin{proof}
The method of proof adopted here to enumerate $r(n)$ is to browse a regular drawing of $K_{n,n}$ from left to right in order to associate each region with a unique vertex or a unique crossing, and then to use Lemmas \ref{rlemma} and \ref{clemma}.

First, by the construction of $K_{n,n}$, each vertex $V_{0,m}$, $m=1,2,\ldots,n$, is associated with the $n-1$ regions emanating from it to the right. This contributes $n(n-1)$ to $r(n)$.  On the other hand, the vertices $V_{1,m}$, $m=1,2,\ldots,n$, have no regions emanating from them as we browse from left to right.

Next, let us consider the regions associated with crossings.  Note that, as we browse a regular drawing of $K_{n,n}$ from left to right, each region, other than those mentioned in the previous paragraph, is associated with precisely one crossing.  In other words, there is a unique crossing at the leftmost point of each of these regions (it is of course possible for several regions to share a particular crossing).  This uniqueness is a consequence of the fact that no edges in a regular drawing of $K_{n,n}$ are vertical. Furthermore, other than for the $(n-1,1)$ crossings, each crossing of $K_{n,n}$ has exactly $q-1$ regions emanating from it to the right, where $q$ is the number of edges involved in that particular crossing.  The $(n-1,1)$ crossings, of which there $n-1$, are the rightmost ones, each with abscissa $\frac{n-1}{n}$.   Each of these crossings involves exactly two edges and has no regions associated with it; remember that $r(n)$ enumerates regions enclosed by $K_{n,n}$.  Thus, in order to obtain the number of regions associated with crossings, we can sum the number of edges involved with each individual crossing and then subtract both the total number of crossings and the number of  $(n-1,1)$ crossings.

Using the above, in conjunction with Lemmas \ref{rlemma} and \ref{clemma}, gives
\begin{align}\label{intres1}
r(n)
&=n(n-1)-c(n)-(n-1)+\!\!\!\sum_{\substack{1 \leq a,b <n\\ \gcd(a,b)=1}}\!\!\!\!\!\! N(a,b)\nonumber\\
&=(n-1)^2-\!\!\!\sum_{\substack{1 \leq a,b < n\\ \gcd(a,b)=1}}\!\!\!\!\!\!(n-a)(n-b)+\!\!\!\sum_{\substack{1 \leq 2a,2b <n\\\gcd(a,b)=1}}\!\!\!\!\!\!(n-2a)(n-2b)\nonumber\\
&\qquad\qquad\qquad\qquad+\!\!\!\sum_{\substack{1 \leq a,b <n\\ \gcd(a,b)=1}}\!\!\!\!\!\! \left(n^2-2ab+f(a,b,n)\right),
\end{align}
where
\begin{displaymath}
f(a,b,n)=\left\{
\begin{array}{cl}
0, & \quad\textrm{if $n>2\max\{a,b\}$};\\
 (n-2a)(n-2b), & \quad\textrm{otherwise}.
 \end{array} \right.
 \end{displaymath}
Note that
\begin{equation}\label{intres2}
\sum_{\substack{1 \leq a,b <n\\ \gcd(a,b)=1}}\!\!\!\!\!\! f(a,b,n)+\!\!\!\sum_{\substack{1 \le 2a,2b < n\\\gcd(a,b)=1}}\!\!\!\!\!\!(n-2a)(n-2b)=\!\!\!\sum_{\substack{1 \leq a,b < n\\\gcd(a,b)=1}}\!\!\!\!\!\!(n-2a)(n-2b).
\end{equation}
Then, from (\ref{intres1}) and (\ref{intres2}), we have
\begin{align*}
r(n)
&=(n-1)^2+\!\!\!\sum_{\substack{1 \leq a,b <n\\ \gcd(a,b)=1}}\!\!\!\!\!\! \left(n^2-2ab-(n-a)(n-b)+(n-2a)(n-2b)\right)\\
&=(n-1)^2+\!\!\!\sum_{\substack{1 \leq a,b <n\\ \gcd(a,b)=1}}\!\!\!\!\!\! (n-a)(n-b),
\end{align*}
as required.
\end{proof}

The first few terms of $\{c(n)\}$ and $\{r(n)\}$ are given in Table \ref{Table1}.  At the time of writing, the latter sequence does not appear on the website \cite{sloane}.  However, with $a(n)$ as the $n$th term of A115004, we have $r(n)=a(n)+(n-1)^2$.

\renewcommand\arraystretch{1.4}
\begin{table}[!h]
\begin{center}
  \begin{tabular}{c |c c c c c c c c c c c}
 $n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
  \hline
 $c(n)$ & 0 & 1 & 7 & 27 & 65 & 147 & 261 & 461 & 737 & 1143\\
 \hline
 $r(n)$ & 0 & 2 & 12 & 40 & 96 & 204 & 368 & 634 & 1012 & 1544
  \end{tabular}\caption{The number of crossings $c(n)$ and regions $r(n)$ in a regular drawing of $K_{n,n}$.}\label{Table1}
\end{center}
\end{table}

By regarding each crossing of $K_{n,n}$ as a vertex, a regular drawing of $K_{n,n}$ induces a graph $G$ on $2n+c(n)$ vertices.  The following corollary provides a formula for the number of edges of $G$.
\begin{corollary}
The number of edges $e(n)$ of $G$ is given by
\[e(n)=n^2+2\!\!\!\!\sum_{\substack{1 \leq a,b < n\\ \gcd(a,b)=1}}\!\!\!\!\!\!(n-a)(n-b)-\!\!\!\sum_{\substack{1 \leq 2a,2b <n\\\gcd(a,b)=1}}\!\!\!\!\!\!(n-2a)(n-2b).\]
\end{corollary}

\begin{proof}
Using Euler's formula $V+F=E+2$ it follows that
\[2n+c(n)+r(n)+1=e(n)+2.\]
The stated formula for $e(n)$ is then obtained by using Lemma \ref{clemma} and Theorem \ref{rtheorem}.
\end{proof}

In Table \ref{Table2} we see the first few terms of $\{e(n)\}$.  As was the case with $\{r(n)\}$, this sequence does not appear in \cite{sloane}.

\renewcommand\arraystretch{1.4}
\begin{table}[!h]
\begin{center}
  \begin{tabular}{c |c c c c c c c c c c c}
 $n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
  \hline
 $e(n)$ & 1 & 6 & 24 & 74 & 170 & 362 & 642 & 1110 & 1766 & 2706\\
  \end{tabular}\caption{The number of edges $e(n)$ of $G$.}\label{Table2}
\end{center}
\end{table}

\section{An asymptotic formula for $r(n)$}
\begin{theorem}\label{asymtheorem}
\[r(n)\sim\frac{3n^4}{2\pi^2}.\]
\end{theorem}

\begin{proof}
It is straightforward to show that
\[\sum_{1 \leq a,b < n}\!\!\!ab\sim\frac{n^4}{4}.\]
Using this, we obtain
\begin{align*}
(n-1)^2+\!\!\!\sum_{1\leq a,b <n}\!\!\! (n-a)(n-b)
&=(n-1)^2+\!\!\!\sum_{1\leq a,b <n}\!\!\! ab\\
&\sim\frac{n^4}{4}.
\end{align*}
Now, since the probability that two numbers chosen at random from $\{1,2,3,\ldots,n\}$ are coprime tends to $\frac{6}{\pi^2}$ as $n$ increases without limit (see \cite{apostol}, for example), we have
\[r(n)\sim\frac{n^4}{4}\cdot\frac{6}{\pi^2}=\frac{3n^4}{2\pi^2}.\]
\end{proof}

\begin{corollary}\label{coroll}
\[\frac{r(n)}{c(n)}\rightarrow\frac{4}{3}\quad\textup{as}\quad n\rightarrow\infty.\]
\end{corollary}

\begin{proof}
This follows on using Theorem \ref{asymtheorem} with the result $c(n)\sim\frac{9n^4}{8\pi^2}$ from \cite{legendre}.
\end{proof}

 It is interesting to compare this to the corresponding situation for a complete graph $K_n$ formed from a regular $n$-sided polygon by drawing in all the diagonals.  Exact formulas for the number of crossings $I(n)$ and regions $R(n)$ in this case are given in \cite{poonen}.  The sequences $\{I(n)\}$ and $\{R(n)\}$ appear in \cite{sloane} as A006561 and A007678 respectively.  Since
\[I(n)\sim\frac{n^4}{24}\quad\textup{and}\quad R(n)\sim\frac{n^4}{24},\]
we  see that
\[\frac{R(n)}{I(n)}\rightarrow 1\quad\textup{as}\quad n\rightarrow\infty.\]

 There would appear to be no simple geometrical explanation as to why, for large $n$, there are approximately 4 regions for every 3 crossings in a regular drawing of $K_{n,n}$.  If it were the case that the proportion of crossings comprising exactly two edges and the proportion of regions that are triangular both tended to 1 as $n$ increased without limit then this would indeed provide a geometrical interpretation of Corollary \ref{coroll}.  This is because every such crossing sits at the corner of 4 regions, and every such region has 3 vertices.  However, it seems that the proportion of crossings comprising exactly two edges tends to some limit $L$ such that $L<1$ and the proportion of regions that are triangular decreases with $n$.
 
\section{Acknowledgement}
I would like to thank an anonymous referee for their helpful comments.


\begin{thebibliography}{9}
\bibitem{apostol} T. M. Apostol, \textit{Introduction to Analytic Number Theory}, Springer, 1976.
\bibitem{cameron} P. J. Cameron, \textit{Combinatorics: Topics, Techniques, Algorithms}, Cambridge University Press, 1994.
\bibitem{dolan} S. Dolan, \textit{Discrete Mathematics 1}, Cambridge University Press, 2000.
\bibitem{legendre} S. Legendre, The number of crossings in a regular drawing of the complete bipartite graph, \textit{J. Integer Sequences} \textbf{12} (2009),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Legendre/legendre2.html}{Article 09.5.5}.
\bibitem{poonen} B. Poonen and M. Rubinstein, The number of intersection points made by the diagonals of a regular polygon, \textit{SIAM J. Discrete Math.} \textbf{11} (1998), 135--156.
\bibitem{sloane} N. Sloane,
The On-Line Encyclopedia of Integer Sequences,
2010. Available at 
\href{http://www.research.att.com/~njas/sequences}{\tt http://www.research.att.com/$\sim$njas/sequences}.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05C62; Secondary 05A15, 05A16, 11A05.\\

\noindent \emph{Keywords: } 
complete bipartite graph, crossing, greatest common divisor, region.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A006561},
\seqnum{A007678},
\seqnum{A115004}, and
\seqnum{A159065}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 23 2009;
revised version received   March 31 2010; August 5 2010.
Published in {\it Journal of Integer Sequences}, August 13 2010.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}