Problem 32: A Communication Problem

Problem 32 - A Communication Problem

We have seen several applications of the geometries we have introduced so far. Now, we will look at a very interesting problem that is specifically applicable in a real world situation. This problem deals with telephone communication.

We will take a set of telephone users who would like to be able to speak with one another. In order for each user to speak to any other, there must be at least one switch between any two users. Every switch will be responsible for a certain number of users. The ultimate goal is to minimize the total number of switches.

Let's state some requirements for our communication system:

Any two users can be connected using just one switch.
Each switch connects at least two users.
There are at least two switches.
All switches look alike (we will assume this to mean that each switch connects the same number of users, but more qualifications will follow).

But remember that we want to try to solve this via the geometric techniques we have seen thus far. So, lets try to figure out what this means in terms of a geometry. Let's let our switches be lines and each user be a point.

So this means:

Any two points are connected by one line.
Every line contains at least two points.
There are at least two lines.
Every line is incident with the same number of points.

This should look familiar to you! Remember the axioms for a linear space.

LINEAR SPACES

1. Any line has at least two points.

2. Two points are on at most one line.

3. Any two points are on a line.

So this problem really just deals with special kinds of linear spaces. So, in order to create the best communication system, we need to find a linear space with the fewest lines possible such that all lines are incident with the same number of points.

Let's look at an example of such a communication system. We'll use the Fano plane (projective plane of order 2) to construct it. Obviously, the Fano plane satisfies all the axioms of a linear space and we know that each line is incident with the same number of points (3). In addition, provided that there must be at least two lines, under the axioms of a linear space the fewest number of lines possible is 7.

Here's a diagram:

The figure on the right is the incidence graph ( notice that each outer point corresponds to a line and each inner point is a point on the Fano plane. A line is drawn from the outer point to the inner point if in the actual geometry, the line and points are incident. In this case we have labeled the line points as the triplet of points with which they are incident. Often they are labeled 1, ..., n for n -many lines). In this application, the incidence graph is our communication system. Each outer point represents a switch and each inner point a telephone user. Notice that 2 users are able to communicate with each other if there is a switch that connects them (you can easily see that this is true - and we know that it is true by the axioms of a linear space - each point must be connected to every other via a line).

So, given these 7 users, we have a communication system with 7 switches. But is this the minimum number of switches?

Let's recall a theorem that we have seen earlier.

de Bruijn-Erdos Theorem:

Let S be a finite linear space with b > 1, where b is the number of lines and v is the number of points. Then either

(i) b > v, or

(ii) if b = v, any two lines have a point in common. In this case, either one line has v - 1 points and all others have two points, or every line has k + 1 points and every point is on k + 1 lines, with k > 2

We know that in case 2, we must have a projective plane (or a near-pencil, which won't satisfy the conditions of alikeness for the communication system).

So, from both of these theorems, we arrive at the idea that the most efficient communication systems must be modeled by projective planes (we have the least number of switches possible). But looking again at our system modeled above from the Fano plane, its appears that all of the switches don't neccessarily look "alike." We know this means (at least) that our lines must have the same incidence, but is there something beyond that? We can, be relabeling the points of the Fano plane, make our incidince graph appear much nicer, so that all of our switches look alike.

In an actual communication situation, it follows that because each of these swiches connects a user in the same way, one can use the same hardware for any switch. Certainly this is a better system than the first one.

So we have seen an example of the projective plane of order 2 that is the most ideal. How do we know which projective planes will be the ideal communication systems? Let's quickly give a definition that will help in answering this question.

Definition: If n is a positive integer, then the set D of positive integers is a difference set of order n if D has n + 1 elements and any integer {1, 2, 3, ... , n²+ n} can be written uniquely as
d - d' mod (n²+ n + 1) where d and d' are in D.

Now for a quick example. Suppose, D = {4,5,7}. Then D is of order 2, and n²+ n + 1 = 7. So, let's look at the result of d - d' mod 7 for every d, d' in D.

4 - 5 = 6 mod 7
4 - 7 = 4 mod 7
5 - 7 = 5 mod 7
7 - 5 = 2 mod 7
7 - 4 = 3 mod 7
5 - 4 = 1 mod 7.

So, you can see that we have the entire set {1,2,3,4,5,6}. So D = {4,5,7} is a difference set.

Theorem: Let D be a difference set of order n > 2. Then we will define the incidence structure, P(D) as follows for a projective plane of order n:

the points of P(D) are the integers 0,1 ,2, 3, ... , n²+ n;
the lines of P(D) are the difference sets. Given a difference set D: {d₀, ... , d_n} , it is possible to arrive at all other difference sets via D + i such that i is one of the points {0,1, 2, 3, ... , n²+ n} and D + i := {d₀ + i mod (n²+ n + 1), . . . , d_n + i mod (n²+ n + 1)}

So, it is easy to check that the example an ideal communication system shown above (with difference set: {4, 5, 7} does indeed satisfy the theorem above.

The projective planes constructed from difference sets are models of ideal communication systems!

So, now that we know that a projective plane can be constructed using these sets, one of the most important and difficult questions of projective geometry is which projective planes can be constructed in this way. It is possible to prove that all Desarguesian planes can be obtained from difference sets and it is conjectured that all sets constructed this way are Desarguesian.

Let's look at an interesting Theorem that deals with the collineations of difference sets.

Theorem: Let P = P(D) be a projective plane created from a difference set of order n. Then there exists a map f such that f: x a x + 1 mod (n²+ n + 1) that is a collineation of order n²+ n + 1 (We define the order of a permutation f to be the smallest integer t such that f ^t= id).

The group of collineations generated by f is called a Singer cycle.

A collineation of this form is often referred to as a non-fixed point automorphism with only one orbit (the length of which is n²+ n + 1).

The converse of this theorem is also true!

Theorem: Let P be a finite projective plane of order n that has a collineation f of order n²+n+1 such that the group of collineations generated by f permutes the points of P as well as the lines, in a cyclic way. Then there exists a difference set D of order n such that the projective plane P can be constructed from it.

(For proofs of each of these, see Beutelspacher and Rosenbaum, pg 87, 88).

Singer's Theorem states that any finite Desarguesian plane (all projective planes over a field) has such a mapping f. Thus, as we have already stated, any finite Desarguesian projective plane can be described using a difference set.

Let's look at an interesting approach to finding a difference set for a given plane. Let's use the Fano plane again.

We will begin by choosing a fixed-point-free automorphism of the Fano plane as labeled below:

Let the mapping be: f: 0 a 4, 1 a 0, 2 a 1, 3 a 2, 4 a 6, 5 a 3, 6 a 5. Check that this is indeed a fixed-point-free automorphism.

Now, we want to create an n²+ n + 1 - gon such that we label each of its points with the labels of our points of the Fano Plane:

Start at point 0 and give it another label: [0]. Now continue clockwise, labeling each consecutive point as the image under the automorphism f of the one before it. So, point 0 will be dually named [0] and we will then name point 1 as [4] as f: 0 a 4. Then point 2 will be labeled as [6] since f: 4 a 6. Continue this way until all points are labeled. Now, draw a line through the set of image points that correspond to a line on the Fano plane under the mapping f.

The red line above corresponds to the line (0, 4, 2). Yet if we label this set with the original point labels, we have (0, 1, 5). This is in fact a difference set for the Fano plane. If we use this as a generator and rotate it 7 times, we get the following diagram:

The set of labels that correspond to each line is a difference set of order 7! Check that for D = {0,1, 5}, D + i, i:= (0,1, 2, . . . , 6) really are difference sets.

Thus, we see an example of how given a fixed-point-free collineation, we can arrive at a difference set for the given geometry.

PROBLEM 32: (a) Create an ideal communication for a system with 13 users. Find the set of differences. Draw the figure corresponding to the system. (Hint: It is tricky to come up with with a difference set of 4 integers. Use 1, 2, 4 and one other. )

(b) (Optional - for those who loved part (a)). Do the same thing for a system with 21 users (Hint: It is tricky to come up with with a difference set of 5 integers. Use 1, 2, 5 and two others. )

Solutions

References: Beutelspacher & Rosenbaum, Polster