Counting the Regions in a Regular Drawing of K_{n,n}

Martin Griffiths School of Education University of Manchester Manchester M13 9PL United Kingdom

               martin.griffiths@manchester.ac.uk

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.

1 Introduction

A graph G is called 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 [2] or [3], for example. In a 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 [4] 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, …, n} and {(1, m) : m = 1, 2, …, n} respectively (or at least have some similar arrangement). As an example, a regular drawing of K_{7,7} is shown in Figure 1. 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.

In this article we broaden the scope of the work carried out in [4], 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.

2 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),

Figure 1: A regular drawing of the complete bipartite graph K_{7,7}.

where k ∈ {0, 1} and m ∈ {1, 2, …, 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 ≤ p < i and j < q ≤ n or i < p ≤ n and 1 ≤ 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 ∈ ℤ and a, b ∈ ℕ such that gcd(a, b) = 1. The point of intersection of E_{i,j} and E_{p,q} is known as an (a, b) crossing. It is straightforward to show that this has coordinates

(\frac{a}{a + b}, \frac{aj + bi}{a + b}) .

For example, we see in Figure 2 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

(\frac{3}{3 + 2}, \frac{3 · 6 + 2 · 2}{3 + 2}) = (\frac{3}{5}, \frac{22}{5}) .

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.

Lemma 1. Let a, b ∈ ℕ such that 1 ≤ a, b < n and gcd(a, b) = 1. Then

N(a, b) = \{ \begin{matrix}n^{2} − 2ab, & if n > 2 max\{a, b\}; \\ 2(n − a)(n − b), & otherwise. \end{matrix}

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; i + a; i; j; j − b]

Figure 2: An (a, b) crossing with a = 3, b = 2, i = 2, j = 6 and k = 1.

Proof. Since N(a, b) = N(b, a) by symmetry, we may, without loss of generality, assume that a ≥ b, so that max{a, b} = a. The set S of edges involved in (a, b) crossings is given by

{E_{i,j} : 1 ≤ i ≤ n − a and b + 1 ≤ j ≤ n} ⋃ {E_{i,j} : a + 1 ≤ i ≤ n and 1 ≤ j ≤ n − b} .

Suppose first that n ≤ 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

{E_{i,j} : a + 1 ≤ i ≤ n − a and b + 1 ≤ j ≤ n − b} .

The cardinality of this set is (n − 2a)(n − 2b), so that

|S| = 2(n − a)(n − b) − (n − 2a)(n − 2b)
= n^{2} − 2ab

in this case, thereby proving the lemma.

In order to illustrate Lemma 1 it is convenient to consider the n×n matrix M_{n}(a, b) with entries m_{i,j}(a, b), 1 ≤ i, j ≤ 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) × (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 ≤ 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

N(a, b) = N(3, 1)
= 2(5 − 3)(5 − 1)
= 16.

( \begin{matrix}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{matrix} )

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

N(a, b) = N(3, 2)
= 7^{2} − 2 · 3 · 2
= 37.

( \begin{matrix}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{matrix} )

Lemma 2. The number c(n) of crossings in a regular drawing of the complete bipartite graph K_{n,n} is given by

c(n) = ∑_{\begin{matrix}1≤a,b<n \\ gcd(a,b)=1 \end{matrix}} (n − a)(n − b) − ∑_{\begin{matrix}1≤2a,2b<n \\ gcd(a,b)=1 \end{matrix}} (n − 2a)(n − 2b).

Proof. This appears as one of the main results in [4], a full proof of which is given there.

With regard to notation, note that the first sum above is taken over all pairs (a, b) such that 1 ≤ a < n, 1 ≤ b < n and gcd(a, b) = 1, and that it is not necessary that b ≥ a. A similar comment applies to the second sum. The sequence {c(n)} appears in Sloane’s On-line Encyclopedia of Integer Sequences [6] as entry A159065.

3 An exact formula for r(n)

Theorem 3. The number r(n) of regions in a regular drawing of the complete bipartite graph K_{n,n} is given by

r(n) = (n − 1)^{2} + ∑_{\begin{matrix}1≤a,b<n \\ gcd(a,b)=1 \end{matrix}} (n − a)(n − b).

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 1 and 2.

First, by the construction of K_{n,n}, each vertex V_{0,m}, m = 1, 2, …, 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, …, 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 1 and 2, gives

r(n) = n(n − 1) − c(n) − (n − 1) + ∑_{\begin{matrix}1≤a,b<n \\ gcd(a,b)=1 \end{matrix}} N(a, b)

= (n − 1)^{2} − ∑_{\begin{matrix}1≤a,b<n \\ gcd(a,b)=1 \end{matrix}} (n − a)(n − b) + ∑_{\begin{matrix}1≤2a,2b<n \\ gcd(a,b)=1 \end{matrix}} (n − 2a)(n − 2b)

+ ∑_{\begin{matrix}1≤a,b<n \\ gcd(a,b)=1 \end{matrix}} (n^{2} − 2ab + f(a, b, n)) ,  (1)

where

f(a, b, n) = \{ \begin{matrix}0, & if n > 2 max\{a, b\}; \\ (n − 2a)(n − 2b), & otherwise. \end{matrix}

Note that

∑_{\begin{matrix}1≤a,b<n \\ gcd(a,b)=1 \end{matrix}} f(a, b, n) + ∑_{\begin{matrix}1≤2a,2b<n \\ gcd(a,b)=1 \end{matrix}} (n − 2a)(n − 2b) = ∑_{\begin{matrix}1≤a,b<n \\ gcd(a,b)=1 \end{matrix}} (n − 2a)(n − 2b).  (2)

Then, from (1) and (2), we have

r(n) = (n − 1)^{2} + ∑_{\begin{matrix}1≤a,b<n \\ gcd(a,b)=1 \end{matrix}} (n^{2} − 2ab − (n − a)(n − b) + (n − 2a)(n − 2b))

= (n − 1)^{2} + ∑_{\begin{matrix}1≤a,b<n \\ gcd(a,b)=1 \end{matrix}} (n − a)(n − b),

as required.

The first few terms of {c(n)} and {r(n)} are given in Table 1. At the time of writing, the latter sequence does not appear on the website [6]. However, with a(n) as the nth term of A115004, we have r(n) = a(n) + (n − 1)^{2}.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ c(n) & 0 & 1 & 7 & 27 & 65 & 147 & 261 & 461 & 737 & 1143 \\ r(n) & 0 & 2 & 12 & 40 & 96 & 204 & 368 & 634 & 1012 & 1544 \end{matrix}

Table 1: The number of crossings c(n) and regions r(n) in a regular drawing of K_{n,n}.

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.

Corollary 4. The number of edges e(n) of G is given by

e(n) = n^{2} + 2 ∑_{\begin{matrix}1≤a,b<n \\ gcd(a,b)=1 \end{matrix}} (n − a)(n − b) − ∑_{\begin{matrix}1≤2a,2b<n \\ gcd(a,b)=1 \end{matrix}} (n − 2a)(n − 2b).

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 2 and Theorem 3.

In Table 2 we see the first few terms of {e(n)}. As was the case with {r(n)}, this sequence does not appear in [6].

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ e(n) & 1 & 6 & 24 & 74 & 170 & 362 & 642 & 1110 & 1766 & 2706 \end{matrix}

Table 2: The number of edges e(n) of G.

4 An asymptotic formula for r(n)

Theorem 5.

r(n) ∼ \frac{3n^{4}}{2π^{2}} .

Proof. It is straightforward to show that

∑_{1≤a,b<n}ab ∼ \frac{n^{4}}{4} .

Using this, we obtain

(n − 1)^{2} + ∑_{1≤a,b<n}(n − a)(n − b) = (n − 1)^{2} + ∑_{1≤a,b<n}ab

∼ \frac{n^{4}}{4} .

Now, since the probability that two numbers chosen at random from {1, 2, 3, …, n} are coprime tends to \frac{6}{π^{2}} as n increases without limit (see [1], for example), we have

r(n) ∼ \frac{n^{4}}{4} · \frac{6}{π^{2}} = \frac{3n^{4}}{2π^{2}} .

Corollary 6.

\frac{r(n)}{c(n)} → \frac{4}{3} as n → ∞.

Proof. This follows on using Theorem 5 with the result c(n) ∼ \frac{9n^{4}}{8π^{2}} from [4].

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 [5]. The sequences {I(n)} and {R(n)} appear in [6] as A006561 and A007678 respectively. Since

I(n) ∼ \frac{n^{4}}{24} and R(n) ∼ \frac{n^{4}}{24},

we see that

\frac{R(n)}{I(n)} → 1 as n → ∞.

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 6. 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.

5 Acknowledgement

I would like to thank an anonymous referee for their helpful comments.

References

[1] T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1976.

[2] P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994.

[3] S. Dolan, Discrete Mathematics 1, Cambridge University Press, 2000.

[4] S. Legendre, The number of crossings in a regular drawing of the complete bipartite graph, Journal of Integer Sequences 12 (2009), Article 09.5.5.

[5] B. Poonen and M. Rubinstein, The number of intersection points made by the diagonals of a regular polygon, SIAM J. Discrete Math. 11 (1998), 135–156.

[6] N. Sloane, The On-Line Encyclopedia of Integer Sequences, 2010.

   http://www.research.att.com/∼njas/sequences.

2010 Mathematics Subject Classification: Primary 05C62; Secondary 05A15, 05A16, 11A05. Keywords: Complete bipartite graph, crossing, greatest common divisor, region. (Concerned with sequences, A006561, A007678, A115004 and A159065.)