Math (562419), страница 14
Текст из файла (страница 14)
SOME APPLICATIONS OF GRAPH THEORY TO OTHER PARTS OF MATHEMATICS
Source: Mathematical Intelligencer, Summer99, Vol. 21 Issue 3, p6, 6p, 7 diagrams, 1 graph, 2bw
Author(s): Bertram, Edward; Horak, Peter
Many mathematicians are now generally aware of the significance of graph theory as it is applied to other areas of science and even to societal problems. These areas include organic chemistry, solid state physics and statistical mechanics, electrical engineering (communications networks and coding theory), computer science (algorithms and computation), optimization theory, and operations research. The wide scope of these and other applications has been well documented (e.g., [4, 11]).
However, not everyone realizes that the powerful combinatorial methods found in graph theory have also been used to prove significant and well-known results in a variety of areas of pure mathematics. Perhaps the best known of these methods are related to a part of graph theory called matching theory. For example, results from this area can be used to prove Dilworth's chain decomposition theorem for finite partially ordered sets. A well-known application of matching in group theory shows that there is a common set of left and right coset representatives of a subgroup in a finite group. Also, the existence of matchings in certain infinite bipartite graphs played an important role in Laczkovich's affirmative answer to Tarski's 1925 problem of whether a circle is piecewise congruent to a square. Other applications of graph theory to pure mathematics may be found scattered throughout the literature.
Recently, a collection of examples [10] showing the application of a variety of combinatorial ideas to other areas has appeared. There, for example, matching theory is applied to give a very simple constructive proof of the existence of Haar measure on compact topological groups, but the other combinatorial applications do not focus on graph theory. The graph-theoretic applications presented here do not overlap with those in [10], and no attempt has been made at a survey. Rather, we present five examples, from set theory, number theory, algebra, and analysis, whose statements are well known or are easily understood by mathematicians who are not experts in the area.
Additional criteria for choosing these five examples were that the statement can be formulated using few definitions and that the proof can be explained in a relatively short space, without too much technical detail. The proof should exhibit the strength and elegance of graph-theoretic methods, although, in some cases, one must consult the literature in order to complete the proof.
Preliminaries
For the convenience of our readers, we recall the necessary definitions from graph theory.
An (undirected) graph G = (V, E) is a pair in which V is a set, the vertices of G, and E is a set of 2-element subsets of V, the edges of G. An edge e is an element of E is denoted by e = xy, x and y being the end vertices of e. Here, e is incident with x (and e is incident with y). The degree of a vertex v, deg(v), is the number of edges incident with v. In a directed graph, or simply digraph, G = (V, E), the (directed) edges are ordered pairs of vertices of V and are denoted by e = (x, y).
A trail of length n in a graph G (digraph G) is a sequence of vertices x[sub 0], x[sub 1], x[sub 2], ..., x[sub n] (x[sub i] is an element of V), such that for i = 0, 1, ..., n - 1, x[sub i]x[sub i + 1] is an edge of G ((x[sub i]x[sub i + 1]) is an oriented edge of G). If x[sub 0] = x[sub n], then the trail is said to be closed. When all the vertices in the sequence are distinct, the trail is called a path. A closed trail, all of whose vertices are distinct except for x[sub 0] and x[sub n], is called a cycle.
A graph G is connected if any two vertices of G are joined by a path in G. Otherwise, G is said to be disconnected. The components of G are the maximal connected subgraphs of G. A tree is a connected graph without cycles. A graph G = (V, E) is said to be bipartite if V can be partitioned into two nonempty subsets A and B such that each edge of G has one end vertex in A and one end vertex in B. Then, G is also denoted by G = (A, B; E).
If (H, Center Dot) is a group and S a set of generators of H, not necessarily minimal, the Cayley graph G(H, S), of (H, Center Dot) with respect to S, has vertices x, y, ... is an element of H, and xy is an edge if and only if either x = y Center Dot a or y = x Center Dot a for some a is an element of S.
If G is any graph and e = xy an edge of G, then by a contraction along e, we mean the graph G' which arises from G by identifying the vertices x and y (see Fig. 1).
We say that a graph G[sub 1] is contractible onto a graph G[sub 2] if there is a sequence of contractions along edges which transforms G[sub 1] to G[sub 2].
The automorphism group of a graph G is the group of all permutations p of the vertices of G with the property that p(x)p(y) is an edge of G iff xy is an edge of G. A group H of permutations acting on a set V is called semiregular if for each x is an element of V, the stabilizer H[sub x] : = {h is an element of H | x[sup h] = x} consists of the identity only, where x[sup h] denotes the image of x under h. If H is transitive and semiregular, then it is regular.
Cantor-Schroder-Bernstein Theorem
Our first example is a graph-theoretical proof of the classical result of Schroder and Bernstein. Actually, the theorem was stated by Cantor, who did not give a proof. The theorem was proved independently by Schroder (1896) and Bernstein (1905). The idea behind the proof presented here can be found in [8].
Theorem (Cantor-Schroder-Bernstein): Let A and B be sets. If there is an injective mapping f: A right arrow B and an injective mapping g: B right arrow A, then there is a bijection from A onto B, that is, A and B have the same cardinality.
Proof. Without loss of generality, we may assume that A and B are disjoint. Define a bipartite graph G = (A, B; E), where xy is an element of E if and only if either f(x) = y or g(y) = x, x is an element of A, y is an element of B. By our hypothesis, 1 </= deg v </= 2 for each vertex v of G. Therefore, each component of G is either a one-way infinite path (i.e., a path of the form x[sub 0], X[sub 1], ..., x[sub n], ...), or a two-way infinite path (of the form ... X[sub -n], x[sub -n + 1], ..., x[sub -1], x[sub 0], X[sub 1], ..., X[sub n], ...), or a cycle of even length with more than two vertices, or an edge. Note that a finite path of length >/= 2 cannot be a component of G. Hence, there is in each component a set of edges such that each vertex in the component is incident with precisely one of these edges. Hence, in each component, the subset of vertices from A is of the same cardinality as the subset of vertices from B.
Fermat's (Little) Theorem
There are many proofs of Fermat's Little Theorem, even short algebraic or number-theoretic proofs. The first known proof of the theorem was given by Euler, in his letter of 6 March 1742 to Goldbach. The idea of the graphtheoretic one presented below can be found in [5] where this method, together with some number-theoretic results, was used to prove Euler's generalization to nonprime modulus.
Theorem (Fermat): Let p be a prime such that a is not divisible by p. Then, a[sup p] - a is divisible by p.
Proof Consider the graph G = (V, E), where V is the set of all sequences (a[sub 1], a[sub 2], ..., a[sub p]) of natural numbers between 1 and a (inclusive), with a[sub i] Is not equal to a[sub j] for some i Is not equal to j. Clearly, V has a[sup p] - a elements. For any u is an element of V, u = (u[sub 1], ..., u[sub p-1], u[sub p]), let us say that uv is an element of E just in case v = (u[sub p], u[sub 1], ..., u[sub p-1]). Clearly, each vertex of G is of degree 2, so each component of G is a cycle, of length p. But then, the number of components must be (a[sup p] - a)/p, so p|a[sup p] - a.
Nielson-Schreier Theorem
Let H be a group and S be a set of generators of H. Then, a product of generators and their inverses which equals (the identity) 1 is called a trivial relation among the generators in S if 1 can be obtained from that product by repeatedly replacing xx[sup -1] or x[sup -1]x by 1, otherwise such a product is called a nontrivial relation. A group H is free if H has a set of generators such that all relations among the generators are trivial. In [1] Babai proved the Nielson-Schreier Theorem on subgroups of free groups, as well as other results in diverse areas, from his "Contraction Lemma." The particular case of this lemma when G is a tree, and its use in proving the Nielson-Schreier Theorem, was also observed by Serre [12, Chap. 1, Sec. 3]. The proof of the Contraction Lemma below is somewhat technical, although it uses only the ideas from group theory and graph theory we have already recalled, and is omitted here.
Contraction Lemma. Let H be a semiregular subgroup of the automorphism group ora connected graph G. Then, G is contractible onto some Cayley graph of H.
If H is a group and h is an element of H, consider the permutation h[sub R] of H obtained by multiplying all the elements of H on the right by h. The collection H[sub R] = {h[sub R]: h is an element of H} is a regular group of permutations (under composition) and is called the (right) regular permutation representation of H.
It is known [1] that G is a Cayley graph of the group H if and only if G is connected and H[sub R] is a subgroup of the automorphism group of G.
Corollary. If J is a subgroup of a group H, then any G(H, S) is contractible onto G(J, T) for some set T of generators of J.
Proof H[sub R], the regular representation of H, acts naturally as a regular permutation group on G(H, S), which is connected. Thus, the subgroup of H[sub R] corresponding to the elements of J is a semiregular subgroup of the automorphism group of G(H, S). Now apply the Contraction Lemma.
Theorem (Nielson-Schreier): Any subgroup of a free qroup is free.
Proof. We first show that in any group H and for any set S of generators of H, the Cayley graph G(H, S) contains a cycle of length > 2 if and only if there is a nontrivial relation among the generators in S. To show this, suppose x[sub 0], x[sub 1], ..., x[sub n] = x[sub 0] is a cycle of G(H, S). Then, there are a[sub i] is an element of S, 1 </= i </= n, such that x[subi -1]a[sup epsilon][sub i] = x[sub i], where epsilon[sub i] is an element of {1, -1}. Hence, x[sub n] = x[sub n-1]a[sup epsilon][sub n] = x[sub n-2]a[sup epsilon][sub n-1] a[sup epsilon][sub n] = ... = x[sub 0]a[sup epsilon][sub 1]a[sup epsilon][sub 2] ... a [sup epsilon][sub n], i.e., the identity 1 = a[sup epsilon][sub 1] a[sup epsilon][sub 2] ... a[sup epsilon][sub n]. If this were a trivial relation, then there would exist an integer i, 1 </= i </= n, such that a[sub i] = a[sub i-1] and epsilon[sub i] = -epsilon[sub i + 1]. However, this implies that x[sub i-1] = x[sub i + 1], a contradiction. Similarly, if a[sup epsilon][sub 1] ... a[sup epsilon][sub n] = 1 is a nontrivial relation, then x[sub 0], x[sub 1], ..., x[sub n-1], x[sub n], where x[sub i] = x[sub i-1]a[sup epsilon][sub i] 1 </= i </= n, and x[sub 0] = x[sub n], is a closed trail in G(H, S), which must contain a cycle.
Suppose now that H is a free group, S a minimal set of generators of H, and J a subgroup of H. Since there is no nontrivial relation on the elements of S, G(H, S) does not contain a cycle. Also, from the corollary above, G(H, S) is contractible onto G(J, T) for some set T of generators of J. Because any contraction of a cycle-free graph is again cycle-free, G(J, T) must be cycle-free, and, thus, there is no nontrivial relation on the elements of T. Hence, J must be a free group, freely generated by T.
In [7] the interested reader may further pursue the substantial use of elementary graph theory in giving simplified proofs of important theorems in combinatorial group theory.
Existence of a Nonmeasurable Set
The following proof of the existence of a subset of the real numbers R which is non-measurable in the Lebesgue sense is due to Thomas [15]. He wrote his paper while an undergraduate student. We realize that many readers may still prefer Vitali's proof. However, it is quite unexpected that this theorem can be reduced to the theorem below, an easily proved result in measure theory, by using only discrete mathematics.
A simple, well-known result from graph theory says that a graph (V, E) is bipartite if and only if all its cycles are of even length. For a proof, it suffices to prove it for connected graphs only. Choose any x is an element of V and define V[sub 1] = {y is an element of V: any path connecting x and y is of odd length} and V[sub 2] = {y is an element of V: any path connecting x and y is of even length}. Since there are no odd cycles in (V, E), any two paths connecting x and y are of the same parity, so V[sub 1] and V[sub 2] yield a partition of V. From the definitions of V[sub 1] and V[sub 2], it follows that no edge has both vertices in the same V[sub i], so the graph is bipartite. The second implication is obvious.
Consider now the graph T = (R, E), where xy is an element of E if and only if |x - y| = 3[sup k], with k an integer. In order to show that T is bipartite, suppose that X[sub 0], X[sub 1], x[sub 2], ..., x[sub n-1], x[sub n] = X[sub 0] is a cycle of T of length n. Then, by definition of T, x[sub n] = x[sub n-1] +/- 3[sup k][sub n] = X[sub n-2> +/- 3[sup k][sub n] +/- 3[sup k][sub n] = ... = x[sub 0] +/- 3[sup k][sub 1] +/-3[sup k][sub 2] +/- ... +/- 3[sup k][sub 3] and, thus,
Multiple line equation(s) cannot be represented in ASCII text
where {k[sub i]}[sup n][sub 1] is a set of integers. Multiplying both sides by 3[sp N], where N is an integer such that N + k[sub i] > 0, 1 </=+ i </= n, yields
Multiple line equation(s) cannot be represented in ASCII text
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
