The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph

Stéphane Legendre Team of Mathematical Eco-Evolution Ecole Normale Supérieure 75005 Paris France

                        legendre@ens.fr

Abstract

The regular drawing of the complete bipartite graph K_{n,n} produces a striking pattern comprising simple and multiple crossings. We compute the number c(n) of crossings and give an asymptotic estimate for this sequence.

1 Introduction

A regular drawing of the complete bipartite graph K_{n,n} is obtained in the following way. Draw vertically n uniformly spaced nodes on the left, draw vertically n uniformly spaced nodes on the right, and join by straight lines the left and right nodes in all possible manners. A striking pattern appears, as in Figure 1.

This combinatorial pattern is one of many devised by ancient scholars — Ramon Lull (circa 1235–1316), Giordano Bruno (1548–1600) and Wilhem Leibniz (1646–1716) among others — who aimed at explaining phenomena in terms of extensive combinations of primordial entities. Athanasius Kircher (1601–1680) uses the K_{n,m} pattern in several instances in his book Ars Magna Sciendi [1]. His drawing of K_{18,18} is reproduced in the novel Foucault’s Pendulum by Umberto Eco [2]. As the protagonists of the novel delve into esoteric matters, the K_{n,n} pattern suggests to them that the Map would be reconstructed, provided that a device could compute all combinations.

Here we look more prosaically for a formula giving the number c(n) of crossings in a regular drawing of K_{n,n}. Figure 1 displays the first values of c(n).

Figure 1: Regular drawing of K_{n,n} for n = 2, 3, 4, 5 and 10, with the corresponding number c(n) of crossings.

2 Simple and multiple crossings

Let us assume that nodes on the left have integer coordinates (0, i), 1 ≤ i ≤ n, and nodes on the right have integer coordinates (1, j), 1 ≤ j ≤ n.

We define an (a, b)-crossing as the intersection point of two lines, each joining a left node to a right, where a is the distance between left nodes, 1 ≤ a ≤ n − 1, and b is the distance between right nodes, 1 ≤ b ≤ n − 1.

Let ⟨i, a|j, b⟩ denote the (a, b)-crossing whose nodes have ordinates i, i + a on the left, 1 ≤ i < i + a ≤ n, and j − b, j on the right, 1 ≤ j − b < j ≤ n, as in Figure 2. When a, b, i, j are understood from context, we shall abbreviate ⟨i, a|j, b⟩ as C.

A crossing has multiplicity m if it is the intersection of m + 1 lines. It is simple if m = 1 (two lines intersect), multiple if m ≥ 2.

Proposition 1. For given a and b, the (a, b)-crossings ⟨i, a|j, b⟩ have the same abscissa PSfrag replacements

i i + a j − b j

Figure 2: An (a, b)-crossing.

x = \frac{a}{a+b} when a ≤ b, and x = \frac{b}{a+b} when a > b, and ordinates y = \frac{aj+bi}{a+b} with 1 ≤ i ≤ n − a and b ≤ j ≤ n.

Proof. By the theorem of Thales, \frac{x}{a} = \frac{1−x}{b} gives the abscissa x, and \frac{(i+a)−(j−b)}{1} = \frac{y−(j−b)}{\frac{b}{a+b}} gives the ordinate y.

Corollary 2. The (a, b)-crossing C with gcd(a, b) = 1 and the (a′, b′)-crossing C′ have the same abscissa if and only if there exists d ≥ 1 such that a′ = da and b′ = db.

Proof. If \frac{a}{a+b} = \frac{a′}{a′+b′} then ab′ = ba′. As gcd(a, b) = 1, a divides a′ and b divides b′, so that there exist d ≥ 1 and e ≥ 1 such that a′ = da, b′ = eb. As ab′ = ba′, we get d = e. The converse is obvious.

Corollary 3. When disregarding superimposition, the number of (a, b)-crossings is (n − a)(n − b).

Proof. From Proposition 1, i can take n − a values and j can take n − b values.

Proposition 4. Let C = ⟨i, a|j, b⟩ be an (a, b)-crossing with gcd(a, b) = 1, and C′ = ⟨i′, da|j′, db⟩ a (da, db)-crossing with d ≥ 1. Then C and C′ are superimposed if and only if there exists k ∈ ℤ such that i′ = i + ka and j′ = j − kb.

Proof. Crossings C and C′ have the same abscissa by Corollary 2. By Proposition 1, they have the same ordinate if and only if aj + bi = aj′ + bi′, or a(j − j′) = b(i′ − i). As gcd(a, b) = 1, the latter condition is equivalent to the existence of k ∈ ℤ such that i′ −i = ka and j′ − j = −kb.

Corollary 5. If an (a, b)-crossings is simple then gcd(a, b) = 1. Every multiple crossing contains an (a, b)-crossing such that gcd(a, b) = 1.

Proof. Assume that C = ⟨i, a|j, b⟩ is simple and that there exist d ≥ 2 and a′, b′ such that a = da′, b = db′. Then the (a′, b′)-crossing C′ = ⟨i′, a′|j′, b′⟩ with i′ = i and j′ = j is superimposed on C by Proposition 4, contradicting simplicity. Hence gcd(a, b) = 1. Let C′ = ⟨i, a′|j, b′⟩ be an (a′, b′)-crossing contained in a multiple crossing. We set d = gcd(a′, b′), a = a′/d, and b = b′/d. Then the crossing C = ⟨i, a|j, b⟩ has the desired properties by Proposition 4.

PSfrag replacements

i

i + a
i + 2a
i + 3a
j − 3b
j − 2b
j − b

j

Figure 3: A multiple crossing.

Proposition 6. Suppose C is an (a, b)-crossing with gcd(a, b) = 1, superimposed to a multiple crossing M of multiplicity m ≥ 2. Then 1 ≤ ma ≤ n − 1 and 1 ≤ mb ≤ n − 1. In particular, 2a ≤ n − 1 and 2b ≤ n − 1. Moreover, M is the superimposition of m (a, b)-crossings, m − 1 (2a, 2b)-crossings, m − 2 (3a, 3b)-crossings, …, and a single (ma, mb)-crossing.

Figure 3 displays a crossing of multiplicity m = 3. It is the superimposition of three (2, 3)-crossings, two (4, 6)-crossings and one (6, 9)-crossing.

Proof. Among the (a, b)-crossings contained in M, we select ⟨i, a|j, b⟩ with i + a ≤ n and 1 ≤ j −b, such that i is minimum and j is maximum. For k = 1, …, m, the m (a, b)-crossings ⟨i+(k−1)a, a|j−(k−1)b, b⟩ are superimposed to M by Proposition 4. For k = m, i+ma ≤ n gives ma ≤ n − i ≤ n − 1, while 1 ≤ j − mb and j ≤ n give mb ≤ n − 1. Moreover, for k = 1, …, m−1, the m−1 (2a, 2b)-crossings ⟨i+(k−1)a, 2a|j−(k−1)b, 2b⟩ are superimposed to M, …, and the (ma, mb)-crossing ⟨i, ma|j, mb⟩ is superimposed to M.

Corollary 7. The multiplicity of a (u, v)-crossing that is not superimposed to another (u, v)- crossing, is the greatest common divisor of u and v.

Proof. This is a consequence of Corollary 5 and Proposition 6.

Proposition 8. The number of crossings of abscissa \frac{a}{a+b} (or \frac{b}{a+b}) with gcd(a, b) = 1 is

(n − a)(n − b) − (n − 2a)(n − 2b), if 2a ≤ n − 1 and 2b ≤ n − 1;
(n − a)(n − b),  otherwise.

Proof. The crossings of abscissa \frac{a}{a+b} are simple or multiple. If they are all simple, their number is (n − a)(n − b) by Corollary 3, and this occurs when 2a > n − 1 or 2b > n − 1 by Proposition 6. If some crossings are simple and others are multiple, then 2a ≤ n − 1 and 2b ≤ n − 1 by Proposition 6. Each simple crossing is counted one time in the first term, and 0 times in the second term. Indeed, the second term is the number of (2a, 2b)-crossings (disregarding superimposition), and they are not simple by Corollary 5. By Proposition 6, each multiple crossing of multiplicity m contributes m to the first term and m − 1 to the second term, hence contributes m − (m − 1) = 1 to the tally.

3 Number of crossings

We now state our main result.

Proposition 9. The number c(n) of crossings in a regular drawing of the complete bipartite graph K_{n,n} is

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

Proof. As each crossing in the drawing contains an (a, b)-crossing with gcd(a, b) = 1 by Corollary 5, we count the number of crossings using Proposition 8. Summing over all (a, b) such that gcd(a, b) = 1, within the bounds of validity, gives the result.

An alternative expression for c(n) has been proposed by Philippe Paclet [3]:

Proposition 10. Let f(i, j) be the number of irreducible fractions p/q with 1 ≤ p ≤ i and 1 ≤ q ≤ j, and f′(i, j) the number of rationals admitting at least one reducible form p/q with 1 ≤ p ≤ i and 1 ≤ q ≤ j. Then

c(n) = ∑_{1≤i,j≤n−1}(f(i, j) − f′(i, j)).

Proof. We denote

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

so that c(n) = s(n) − s′(n). By the definition of f,

∑_{1≤i,j≤n−1} f(i, j) = ∑_{1≤i,j≤n−1} ∑_{\begin{matrix}1≤a≤i \\ 1≤b≤j \\ gcd(a,b)=1 \end{matrix}} 1 = ∑_{\begin{matrix}1≤a,b≤n−1 \\ gcd(a,b)=1 \end{matrix}} ∑_{\begin{matrix}a≤i≤n−1 \\ b≤j≤n−1 \end{matrix}} 1 = ∑_{\begin{matrix}1≤a,b≤n−1 \\ gcd(a,b)=1 \end{matrix}}(n − a)(n − b) = s(n).

Similarly,

∑_{1≤i,j≤n−1} f′(i, j) = ∑_{\begin{matrix}1≤c,d≤n−1 \\ gcd(c,d)≠1 \end{matrix}} ∑_{\begin{matrix}c≤i≤n−1 \\ d≤j≤n−1 \end{matrix}} 1.

The set {(c, d); 1 ≤ c, d ≤ n − 1, gcd(c, d) ≠ 1} is identical to the set {(a, b); 1 ≤ 2a, 2b ≤ n − 1, gcd(a, b) = 1}. Indeed, gcd(c, d) ≠ 1 is equivalent to the existence of m ≥ 2 such that c = ma, d = mb, with gcd(a, b) = 1, 2a ≤ ma ≤ n − 1, 2b ≤ mb ≤ n − 1. We obtain

∑_{1≤i,j≤n−1} f′(i, j) = ∑_{\begin{matrix}1≤2a,2b≤n−1 \\ gcd(a,b)=1 \end{matrix}}(n − 2a)(n − 2b) = s′(n).

Sequence s(n) is \underline{A115004} in Sloane [4]. Values of c(n) are given in Table 1.

\begin{matrix}n & s(n) & s′(n) & c(n) & d(n) \\ 1 & - & - & 0 & 0 \\ 2 & 1 & 0 & 1 & 1 \\ 3 & 8 & 1 & 7 & 9 \\ 4 & 31 & 4 & 27 & 36 \\ 5 & 80 & 15 & 65 & 100 \\ 6 & 179 & 32 & 147 & 225 \\ 7 & 332 & 71 & 261 & 441 \\ 8 & 585 & 124 & 461 & 784 \\ 9 & 948 & 211 & 737 & 1296 \\ 10 & 1463 & 320 & 1143 & 2025 \\ 11 & 2136 & 499 & 1637 & 3025 \\ 12 & 3065 & 716 & 2349 & 4356 \\ 13 & 4216 & 999 & 3217 & 6084 \\ 14 & 5729 & 1328 & 4401 & 8281 \\ 15 & 7568 & 1799 & 5769 & 11025 \\ 16 & 9797 & 2340 & 7457 & 14400 \\ 17 & 12456 & 3023 & 9433 & 18496 \\ 18 & 15737 & 3792 & 11945 & 23409 \\ … & … & … & … & … \\ 50 & 948514 & 235680 & 712835 & 1600625 \\ … & … & … & … & … \\ 100 & 15189547 & 3794060 & 11395487 & 24502500 \end{matrix}

Table 1: The number of crossings c(n) = s(n) − s′(n) in the regular K_{n,n} pattern. The sequence of triangular numbers squared, d(n), enumerates the crossings when disregarding multiplicity.

4 Asymptotics

When disregarding multiplicity, the number of crossings in the K_{n,n} pattern is

d(n) = \binom{n}{2}\binom{n}{2} = \frac{n^{2}(n − 1)^{2}}{4} ,

the square of the nth triangular number (\underline{A000537}).

Proposition 11. For large n, c(n) ∼ \frac{9}{2π^{2}} d(n).

Proof. We write

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

with no condition of relative primality under the sums. We have

∑(n − a)(n − b) = ∑ ab = \frac{n^{2}(n − 1)^{2}}{4} = d(n).

Hence n^{2} ∑ 1 − n ∑(a + b) = 0. We now sum with the condition gcd(a, b) = 1. As the probability that two positive integers are relatively prime is \frac{6}{π^{2}} , for large n:

∑_{\begin{matrix}1≤a,b≤n−1 \\ gcd(a,b)=1 \end{matrix}} ab ∼ \frac{6}{π^{2}} d(n), and n^{2} ∑_{\begin{matrix}1≤a,b≤n−1 \\ gcd(a,b)=1 \end{matrix}} 1 − n ∑_{\begin{matrix}1≤a,b≤n−1 \\ gcd(a,b)=1 \end{matrix}}(a + b) ∼ 0.

Hence

s(n) ∼ \frac{6}{π^{2}} d(n).

Let m = ⌊\frac{n+1}{2}⌋, then

∑_{1≤a,b≤m−1}(n − 2a)(n − 2b) = n^{2}(m − 1)^{2} − 2mn(m − 1)^{2} + 4\frac{m^{2}(m − 1)^{2}}{4} .

We sum with the condition gcd(a, b) = 1. For large n, m ∼ \frac{n}{2}. As in the previous computation, the first two terms ∼ 0, and the last term s′(n) ∼ \frac{6}{π^{2}} 4d(\frac{n}{2}) ∼ \frac{6}{π^{2}} 4\frac{d(n)}{16}. We obtain

s′(n) ∼ \frac{1}{4}s(n),

and c(n) = s(n) − s′(n) ∼ \frac{9}{2π^{2}} d(n).

The equivalence c(n) ∼ \frac{9}{8π^{2}} n^{4}, deduced from Proposition 11, appears to give a better estimate of c(n). However, the approximation π ≈ \frac{3}{2} \frac{n^{2}}{\sqrt{2c(n)}} is not close; e.g., for n = 100,

the approximation is 3.1420.

5 Concluding remarks

The regular drawing of K_{n,n} can be considered an analogic device to compute the greatest common divisor of two positive integers a and b. In the drawing, take a units on the left, and b units on the right. Consider the corresponding (a, b)-crossing (i = 0, j = b). Then the multiplicity m of this crossing is the greatest common divisor of a and b (Corollary 7).

It can be noted that the abscissas of the (a, b)-crossings are Farey fractions. This suggests that number theoretical properties of the complete bipartite graph pattern deserve further exploration.

6 Acknowledgements

The referee is gratefully acknowledged for constructive suggestions that improved the manuscript.

References

[1] Athanasius Kircher, Ars Magna Sciendi, XII Libros Digesta, qua Nova et Universali Methodo per Artificiosum Combinationum Contextum de Omni Re Proposita Plurimis et Prope Infinitis Rationibus Disputari, Omniumque Summaria Quaedam Cognitio Comparari Potest, Apud Joannem Janssonium a Waesberge and Viduam Elizei Weyerstraet, Amsterdam, 1669.

[2] Umberto Ecco, Foucault’s Pendulum, Harcourt Brace Jovanovich, San Diego, 1989, p. 473.

[3] Philippe Paclet, personnal communication, February 20, 2004.

[4] Neil Sloane, The On-Line Encyclopedia of Integer Sequences,

    http://www.research.att.com/^{∼}njas/sequences.

2000 Mathematics Subject Classification: Primary 05C62; Secondary 11A05. Keywords: complete bipartite graph, greatest common divisor.

(Concerned with sequences \underline{A000537}, \underline{A115004}, and \underline{A159065}.)

Received April 20 2009; revised version received July 10 2009. Published in Journal of Integer Sequences, July 10 2009.

Return to Journal of Integer Sequences home page.