Flows, View-Obstructions and the Lonely Runner

Wojciech Bienia ^{1} Luis Goddyn ^{2} Pavol Gvozdjak ^{3} András Sebő ^{4} Michael Tarsi^{5}

March 21, 1997

1ENSIMAG, Laboratoire Leibniz-IMAG, France 2Simon Fraser University, Vancouver, Canada. Research supported by NSERC of Canada 3Simon Fraser University, Vancouver, Canada. 4CNRS, Laboratoire Leibniz-IMAG, France. Research supported by W. Cunningham’s grant of NSERC

of Canada 5Tel Aviv University, Israel. Research supported in part by a grant from the Israel Science Foundation.

Abstract

We prove the following result.

Let G be an undirected graph. If G has a nowhere zero flow with at most k different values, then it also has one with values from the set {1, …, k}.

When k ≥ 5, this is a trivial consequence of Seymour’s “six-flow theorem”. When k ≤ 4 our proof is based on a lovely number theoretic problem which we call the “Lonely Runner Conjecture”.

Suppose k runners having nonzero constant speeds run laps on a unit-length circular track. Then there is a time at which all runners are at least 1/(k+1) from their common starting point.

This conjecture appears to have been formulated by J. Wills (Montash. Math. 71 (1967)) and independently by T. Cusick (Aequationes Math. 9 (1973)). Fortunately for our purposes, this conjecture has been verified for k ≤ 4 by Cusick and Pomerance (J. Number Theory 19 (1984)) in a complicated argument involving exponential sums and electronic case checking. A major part of this paper is an elementary self-contained proof of the case k = 4 of the Lonely Runner Conjecture.

AMS Classifications (1991): 11J13, (05B35, 05C15, 05C50, 11J71, 11K60, 52C07, 90B10)

Keywords: Nowhere zero flow, regular matroid, diophantine approximation, view obstruction. Short title: Flows and View Obstructions

1 Introduction

Let G = (V, E) be an undirected graph. A nowhere zero flow of G is an orientation of G supplied with a vector f = (f_{e}) of positive integers indexed by E(G), such that for every v ∈ V (G) the sum of f_{e} on edges entering v is the same as that on edges leaving v. The number f_{e} is called the value of the edge e. The theory of nowhere zero flows is a major topic in combinatorics related to graph coloring and the cycle double cover conjecture; see [9, 14, 16].

The main result of this paper is the following.

Theorem 1.1 Let G be an undirected graph. If G has a nowhere zero flow with at most k distinct values, then it also has one with all values from the set {1, …, k}.

In view of the matroid duality [16, 15, 9, 11, 14] between vertex colorings and nowhere zero flows there is a cographic analogue to Theorem 1.1. A coloring of G is a function c : V (G) → ℝ, so that for all xy ∈ E, c(x) ≠ c(y).

Theorem 1.2 If G has a coloring with real numbers so that the set {|c(x) − c(y)| : xy ∈ E} has at most k distinct values, then G has a (k + 1)-coloring (and thus one where |c(x) − c(y)| ∈ {1, …, k} for all xy ∈ E.)

Theorem 1.2 is easy to prove: By orienting each edge toward the endpoint with the larger color and identifying the color classes, one obtains an acyclic digraph having maximum out-degree k. An easy greedy algorithm results in a (k + 1)-coloring of G.

Theorem 1.1 is more difficult. Our proof relies on Seymour’s six-flow theorem [13] and a number theoretic result of Cusick and Pomerance [6] to which we give a short proof. We state here the six-flow theorem. A graph is called bridgeless, if it has no bridge, where e ∈ E is a bridge if G − e has more components than G.

Theorem 1.3 Every bridgeless graph has a nowhere zero flow with values from the set {1, …, 5}.

There is a common generalization of Theorems 1.1 and 1.2 regarding flows in regular matroids (see [11, 15]) which is strongly suggested by Seymour’s regular matroid decomposition theorem [12]. A matrix is totally unimodular if every subdeterminant belongs to {0, ±1}.

Conjecture 1.4 Let A be a totally unimodular matrix and suppose that Af = 0 has a real solution f = (f_{e}) where each f_{e} is nonzero and where |{|f_{e}| : e ∈ E(G)}| ≤ k. Then there exists a solution f′ = (f′_{e}) with each |f′_{e}| ∈ {1, 2, …, k}.

The analogous statement concerning group-valued flows [16, 9] is false. For example, the graph with two vertices and three parallel edges has a flow with range {1} in Z_{3}, but not in the integers.

The paper is organized as follows. In Section 2, Conjecture 1.4 is reduced to the “Lonely Runner Problem”; in particular Theorem 1.1 is reduced to the special case k ≤ 4. A general proof technique for this problem is introduced in Section 3, and applied to the case k = 4 in Section 4.

2 Runners and Flows

Let us informally state the Lonely Runner Problem: At time zero, k participants depart from the origin of a unit length circular track to run repeated laps. Each runner maintains a constant nonzero speed. Is it true that regardless of what the speeds are, there exists a time at which the k runners are simultaneously at least 1/(k + 1) units from the starting point? The term “lonely runner” reflects an equivalent formulation in which there are k + 1 runners with distinct speeds. Is there a time at which a given runner is ‘lonely’, that is, at distance at least 1/(k + 1) from the others? This poetic title (given by the second author) made its way through an internet inquiry (of the second and last author) up to the cover page of a public relation booklet for the Weissman Institute in Israel [22].

We introduce some notation. The sets of real numbers and positive integers are denoted ℝ and ℕ respectively. The residue class of a ∈ ℝ modulo 1 (called the fractional part of a) is denoted by ⟨a⟩. We view the unit-length circle C as the set {⟨a⟩ : a ∈ ℝ}, which we frequently identify with the real interval [0, 1). An instance of the lonely runner problem consists of a set of runners R := {1, 2, …, k} and a speed vector v := (v_{1}, …, v_{k}) having nonzero real entries. At time t = 0, each r ∈ R begins running on C from the point 0 maintaining the constant speed v_{r}. The position of runner r on C at time t is ⟨tv_{r}⟩. The position of R at time t is the vector ⟨tv⟩ := (⟨tv_{1}⟩, …, ⟨tv_{k}⟩) ∈ [0, 1)^{k}. A vector x = (x_{1}, …, x_{k}) ∈ [0, 1)^{k} is a position (for the speed vector v) if there exists t ∈ ℝ with x = ⟨tv⟩. The set of all positions is denoted X = X(v) ⊆ [0, 1)^{k}. The distance between two points on C is the length of the shorter of the two (arc) intervals between them. We say that r ∈ R is distant (from 0) in x ∈ X or at time t if x_{r} = ⟨tv_{r}⟩ ∈ [\frac{1}{k+1}, \frac{k}{k+1}]. A subset R′ ⊆ R is distant (in some position x) if each r ∈ R′ is distant in x. (here, k is understood by context to equal |R|, not |R′|).

The aforementioned internet inquiry led us to the following assertion, which we call the Lonely Runner Conjecture. This conjecture appears to have been introduced by J. Wills [17] and again, independently by T. Cusick [3].

Conjecture 2.1 For all k ∈ ℕ and v ∈ (ℝ − {0})^{k}, there exists a position where R is distant.

This problem appears in two different contexts. Cusick [3, 4, 5, 6] was motivated by a beautiful application in n dimensional geometry — view obstruction problems. Our statement of the problem is closer to the diophantine approximation approach of Wills [1, 17, 18, 19, 20, 21]. A more general conjecture appears in [2]. The cases k = 2, 3, 4 were first proved in [17],[1],[6] respectively.

Theorem 2.2 If k ≤ 4, then for any v ∈ (ℝ − {0})^{k} there exists a time at which R is distant.

The proof by Cusick and Pomerance [6] of the case k = 4 is not easy, and requires a computer check. In sections 3 and 4 we provide a simple self-contained proof. Section 3 also contains a very short proof for the case k = 3.

We now prove Theorem 1.1 using Theorems 2.2 and 1.3. Proof of Theorem 1.1. Let f be a nowhere zero flow with k different values. If k ≥ 5, then the result is a trivial consequence of Theorem 1.3 since any graph having a nowhere zero flow must be bridgeless. If k ≤ 4, then by Theorem 2.2 there exists t ∈ ℝ such that the fractional part of each entry of tf is in the interval [\frac{1}{k+1}, \frac{k}{k+1}]. The flow tf is a feasible flow in the edge-capacitated network (G, l, u) where l = ⌊tf⌋ and u = ⌈tf⌉ (we take floors and ceilings componentwise). But then there also exists a feasible integer-valued flow for (G, l, u) (Ford and Fulkerson [7]), in which each edge e has value either ⌊tf_{e}⌋ or ⌈tf_{e}⌉. Let us denote this flow by ⌊tf⌉. Thus tf − ⌊tf⌉ is a flow with all entries in [\frac{−k}{k+1}, \frac{−1}{k+1}] ∪ [\frac{1}{k+1}, \frac{k}{k+1}]. Multiplying this flow by k + 1 and reorienting the edges corresponding to negative entries yields a flow with values in [1, k]. Again, there also exists then an integer flow with values in [1, k]. □

Note: we may loosely denote the final flow in the proof of Theorem 1.1 as ⌊(k + 1)(f − ⌊tf⌉)⌉. We remark that this proof can be directly generalized to flows in regular matroids by applying

Hoffman’s theorem [8] in order to define f′ = ⌊(k + 1)(f − ⌊tf⌉)⌉. Thus, Conjecture 1.4 is a weak form of the Lonely Runner Conjecture.

Theorem 2.3 For any k ∈ ℕ, if the Lonely Runner Conjecture holds true for k runners, then the statement of Conjecture 1.4 holds true for that particular value of k.

The remainder of this paper is devoted to the Lonely Runner Conjecture. Wills [17] reduced the Lonely Runner Conjecture from the case of irrational speeds to the rational case. So when proving any case k ≥ 1, one can assume without loss of generality that v ∈ ℕ^{k}, whence the speeds express the number of laps the runners make in unit time. One can further assume that t ∈ [0, 1), although there is usually no advantage in doing so. Proof of Theorem 2.2 when k ≤ 2. The case k = 1 is trivial. In case k = 2 we prove a stronger statement:

Suppose v_{1}, v_{2} ∈ ℕ are relatively prime speeds. At any time t, the nearer runner has distance at most ⌊\frac{v_{1}+v_{2}}{2} ⌋ /(v_{1} + v_{2}). Moreover, this bound is achieved at time t = \frac{τ}{v_{1}+v_{2}} for some τ ∈ ℕ.

Whenever the distance from 0 to the nearer runner is maximum, we have ⟨tv_{1}⟩ = 1 − ⟨tv_{2}⟩. This equality holds if and only if t is an integer multiple of 1/(v_{1} + v_{2}). For such t, both runners are at distance a/(v_{1} + v_{2}) for some integer a ≤ ⌊\frac{v_{1}+v_{2}}{2} ⌋. Since gcd(v_{1}, v_{1} + v_{2}) = 1 we can solve the congruence v_{1}τ ≡ ⌊(v_{1} + v_{2})/2⌋ mod v_{1} + v_{2}, to obtain a time at which the bound on a is achieved, proving the statement. □

3 Pre-jumps

We state the fact that the set X of positions is closed under addition modulo 1 in a particular form suggesting a technique used by all the proofs hereafter.

(1) If x_{1}, x_{2} ∈ X and α ∈ ℤ, then the vector x = ⟨x_{1} + αx_{2}⟩ ∈ [0, 1)^{k} is also in X. If moreover, x_{1} = ⟨t_{1}v⟩, x_{2} = ⟨t_{2}v⟩, and t ≡ t_{1} + αt_{2} mod 1, then x = ⟨tv⟩.

Our use of (1) is as follows. We first note the existence of certain “key” positions in X which we call pre-jumps. In the proof of our main result, it sometimes becomes convenient to add one of these pre-jumps to a position that has already been constructed, thereby obtaining a position in which all runners are distant. Our first example of pre-jumps will be used in a short proof of the case k = 3. (Compare with the proofs in [1] and [3].)

(2) Let v ∈ ℕ^{k}, k ≥ 3. If gcd(v_{1}, …, v_{k−1}) does not divide v_{k}, then there exists a time when R is distant if and only if there exists a time when R \ {k} is distant.

Proof. Let d ≥ 2 be the greatest common divisor defined in the statement, and suppose without loss of generality that gcd(d, v_{k}) = 1. Then

⟨\frac{0}{d}v_{r}⟩ = ⟨\frac{1}{d}v_{r}⟩ = ⋯ = ⟨\frac{d−1}{d}v_{r}⟩ = 0 for r = 1, …, k − 1, whereas
\{⟨\frac{0}{d}v_{k}⟩, ⟨\frac{1}{d}v_{k}⟩, …, ⟨\frac{d−1}{d}v_{k}⟩\} = \{\frac{0}{d}, \frac{1}{d}, …, \frac{d−1}{d}\}.

Let now x = ⟨tv⟩ be a position where R \ {k} is distant. Since R \ {k} is also distant in each of the d positions ⟨x + \frac{j}{d}v⟩ (j = 0, 1, …, d − 1), it suffices to show that k is distant in one of these positions. However, this follows from the fact that 1/d is at most the length 1 − 2/(k + 1) of the interval of distant positions since k ≥ 3 and d ≥ 2. □ Proof of Theorem 2.2 when k ≤ 3. We assume that the speeds v_{1}, v_{2}, v_{3} are distinct positive integers having no common factor. If all three speeds are odd, then ⟨\frac{1}{2}v⟩ = (\frac{1}{2}, \frac{1}{2}, \frac{1}{2}), so we may assume that v_{2} is even. By (2) we may further assume that v_{1} and v_{3} are odd. So ⟨\frac{1}{2}v⟩ = (\frac{1}{2}, 0, \frac{1}{2}), and this will provide our pre-jump x_{1} = ⟨t_{1}v⟩, t_{1} := \frac{1}{2}.

Consider the time interval T := [\frac{1}{4v_{2}} , \frac{3}{4v_{2}} ], during which runner 2 is for the first time in the distant region [\frac{1}{4}, \frac{3}{4}]. For r = 1, 3, let T_{r} = \{t ∈ [0, 1) : ⟨tv_{r}⟩ ∈ [\frac{1}{4}, \frac{3}{4}]\}.

If T \ (T_{1} ∪ T_{3}) ≠ ∅, then use (1) with the defined pre-jump x_{1}, an arbitrary t_{2} ∈ T \ (T_{1} ∪ T_{3}), and α = 1: ⟨(t_{1} + t_{2})v⟩ = (\frac{1}{2}, 0, \frac{1}{2}) + ⟨t_{2}v⟩. Since 2 is the only distant runner at time t_{2}, \{1, 2, 3\} is distant at time t_{1} + t_{2}.

We may now assume T ⊆ T_{1} ∪ T_{3}. Suppose that T ⊆ T_{i}, for some i ∈ {1, 3}. Then T is contained in one of the closed intervals comprising T_{i}, which implies v_{2} ≥ v_{i}. Furthermore, i first becomes distant no later than 2 does, so v_{2} ≤ v_{i} which contradicts v_{2} ≠ v_{i}.

Thus T ⊆ T_{1} ∪ T_{3}, T ∩ T_{i} ≠ ∅ (i = 1, 3). Both T ∩ T_{1} and T ∩ T_{3} consist of disjoint closed intervals and their union is T. Hence ∅ ≠ (T ∩ T_{1}) ∩ (T ∩ T_{3}) = T ∩ T_{1} ∩ T_{3}, and we are done. □

4 The case k = 4

Before completing the proof of Theorem 2.2, we set some notation and present two more pre-jump facts which hold true whenever k + 1 is prime. The notation a|b means that a evenly divides b. For fixed k ≥ 2 we partition the circle C = [0, 1) as {0} ∪ C_{1} ∪ C_{2} where

C_{1} := (0, \frac{1}{k+1}) ∪ (\frac{k}{k+1}, 1) ∪ \{\frac{1}{k+1}, \frac{2}{k+1}, …, \frac{k}{k+1}\} and
C_{2} := (\frac{1}{k+1}, \frac{2}{k+1}) ∪ (\frac{2}{k+1}, \frac{3}{k+1}) ∪ ⋯ ∪ (\frac{k−1}{k+1}, \frac{k}{k+1}).

Given a speed vector v ∈ ℕ^{k} and a position x ∈ X = X(v) we define D := {r ∈ R : (k + 1)|v_{r}} and partition the runners R as R_{0}(x) ∪ R_{1}(x) ∪ R_{2}(x) where

R_{0}(x) := D ∪ {r ∈ R : x_{r} = 0},
R_{1}(x) := {r ∈ R \ D : x_{r} ∈ C_{1}},
R_{2}(x) := {r ∈ R \ D : x_{r} ∈ C_{2}}.

(3) Let k+1 be prime, and suppose there exists x ∈ X in which D is distant, and |R_{2}(x)| < |R_{0}(x)|. Then there exists a time when R is distant.

Proof. We consider the list of k positions ⟨x + \frac{j}{k+1}v⟩ (j = 1, 2, …, k). Since k + 1 is prime, we have

⟨\frac{1}{k+1}v_{r}⟩ = ⋯ = ⟨\frac{k}{k+1}v_{r}⟩ = 0  if r ∈ D,
\{⟨\frac{1}{k+1}v_{r}⟩, …, ⟨\frac{k}{k+1}v_{r}⟩\} = \{\frac{1}{k+1}, …, \frac{k}{k+1}\} if r ∈ R \ D.

Using this, it is straightforward to check that, for m = 0, 1, 2, each runner in R_{m}(x) is distant in exactly k − m of the listed positions. Thus, there are at most |R_{1}(x)| + 2|R_{2}(x)| positions in the list in which R is not distant. If |R_{2}(x)| < |R_{0}(x)|, then |R_{1}(x)| + 2|R_{2}(x)| < k, so R is distant in at least one of the k listed positions. □

Here is an easy corollary.

(4) Suppose that k + 1 is prime, and the only speed which it divides is v_{2}. If there exists d ∈ ℕ dividing at least k/2 different speeds, but not dividing v_{2}, then there exists a time when R is distant.

Proof. Let R′ := {r ∈ R : d|v_{r}}. Since d ≥ 2 and 2 ∉ R′, there exists j ∈ {0, …, d − 1} such that runner 2 is distant in x := ⟨\frac{j}{d}v⟩. We have that x_{r} = 0 for each r ∈ R′, so R_{0}(x) ⊇ \{2\} ∪ R′, and therefore |R_{0}(x)| ≥ 1 + |R′| > \frac{k}{2} = |R|/2, whence |R_{0}(x)| > |R_{2}(x)|. Since D = \{2\} is distant, we are done by (3). □

Proof of Theorem 2.2. We assume k = 4, R = {1, 2, 3, 4}, all speeds are distinct and have no common prime factor. Consider the (proper) subset D = {r ∈ R : 5|v_{r}}. If |D| = 0, then R is distant at time \frac{1}{5}. Suppose 2 ≤ |D| ≤ 3. By induction on k there exists a position y where D is distant. Either we are done at y, or some runner in R \ D is not distant, whence |R_{0}(y)| + |R_{1}(y)| ≥ |D| + 1 ≥ 3, so |R_{2}(y)| ≤ 1 whereas |R_{0}(y)| ≥ |D| ≥ 2 > 1 ≥ |R_{2}(y)| and we are done by (3). We henceforth assume D = {2}, whence 2 ∈ R_{0}(x) for every position x.

If no runner is faster than 2, then at time \frac{1}{5v_{2}} , 2 is the only distant runner, whence |R_{2}(\frac{v}{5v_{2}} )| = 0, |R_{0}(\frac{v}{5v_{2}} )| = 1, and we are again done by (3). We thus assume v_{1} > v_{2}, v_{3}, v_{4}.

At least one of v_{3}, v_{4}, say v_{3}, is not equal to v_{1} − v_{2}. Since v_{2}, v_{3} are distinct and less than v_{1}, the assumptions v_{3} ≠ v_{2} and v_{3} ≠ v_{1} − v_{2} imply v_{3} ≢ ±v_{2} mod v_{1}. If d :=gcd(v_{1}, v_{3}) > 1, then if d divides v_{2}, we are done by (2); if it does not, we are done by (4).

Thus we can assume gcd(v_{1}, v_{3}) = 1. Then there exists α ∈ ℕ, αv_{3} ≡ 1 mod v_{1}. Let x be the position at time \frac{α}{v_{1}} . We have x_{1} = 0 and x_{3} = 1/v_{1} < 1/v_{2} ≤ 1/5, so 1, 2 ∈ R_{0}(x) and 3 ∈ R_{1}(x). If D = {2} is distant in x, then we are done by (3) since 1, 2 ∈ R_{0}(x) whereas 3 ∈ R_{1}(x) so |R_{2}(x)| ≤ 1. So we may assume 2 is not distant in x.

We notice two facts. First, the distance of x_{2} from 0 is at least twice that of x_{3} (this follows from v_{2} ≢ 0, ±v_{3} mod v_{1} and gcd(α, v_{1}) = 1, which implies x_{2} = ⟨\frac{α}{v_{1}} v_{2}⟩ ≠ 0, ±1/v_{1} whence x_{2} ∈ [2/v_{1}, 1 − 2/v_{1}].) Second, if a runner has distance δ ≤ 1/4 from 0 in some position z ∈ X, then it has distance 2δ in position ⟨2z⟩. Let x′ be the first position in the sequence ⟨2x⟩, ⟨4x⟩, ⟨8x⟩, … in which 2 is distant. As before, 1, 2 ∈ R_{0}(x′) whereas, by the two facts and the minimality in the choice of x′, x′_{3} ∈ (0, 1/5) so 3 ∈ R_{1}(x′), and we are again done by (3). □

Acknowledgement. The authors would like to thank Andrew Odlyzko, for directing them to the papers of Jüng Wills and Thomas Cusick; and they thank Martin Loebl, for helpful discussions. The fourth author would like to thank the stimulating environment of the University of Waterloo.

References

[1] U. Betke, J. M. Wills, Untere Schranken für zwei diophantische Approximations-Funktionen, Monatsch. Math. 76 (1972), 214–217.

[2] Y. G. Chen, On a conjecture about diophantine approximations.I. (Chinese), Acta Math. Sinica 33 (1990), 712–717.

[3] T. W. Cusick, View-obstruction problems, Aequationes Math. 9 (1973), 165–170.

[4] T. W. Cusick, View-obstruction problems in n-dimensional geometry, J. Combin. Theory Ser. A 16 (1974), 1–11.

[5] T. W. Cusick, View-obstruction problems. II, Proc. Amer. Math. Soc. 84 (1982) 25–28.

[6] T. W. Cusick, C. Pomerance, View-obstruction problems. III, J. Number Theory 19 (1984) 131–139.

[7] L. R. Ford, D. R. Fulkerson, Network flow and systems of representatives, Canad. J. Math. 10 (1958), 78–84.

[8] A. J. Hoffman, Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, Proc. Sympos. Appl. Math., Vol. 10, R. Bellman, M. Hall Jr., eds., American Mathematical Society, Providence, RI 1960, pp. 113-127.

[9] F. Jaeger, Nowhere-zero flow problems, Selected Topics in Graph Theory 3 (1988), 71–95, L. W. Beineke and R. Wilson, eds., Academic Press, San Diego, CA, 1988.

[10] F. Jaeger, Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B 26 (1979), 205–216.

[11] James G. Oxley, Matroid Theory, Oxford University Press, Oxford, 1992.

[12] P. D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B 28 (1980), 305–359.

[13] P. D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory Ser. B 30 (1981), 130–135.

[14] P. D. Seymour, Nowhere-zero flows. Appendix: Colouring, stable sets and perfect graphs. Handbook of Combinatorics, Vol. 1, R. Graham, M. Grötschel, L. Lovász, eds., Elsevier, Amsterdam, 1995, pp. 289–299.

[15] M. Tarsi, Nowhere zero flow and circuit covering in regular matroids, J. Combin. Theory Ser. B 39 (1985), 346–352.

[16] W.T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954), 80–91.

[17] J. M. Wills, Zwei Sätze über inhomogene diophantische Approximation von Irrationalzahlen. Monatsch. Math. 71 (1967) 263–269.

[18] J. M. Wills, Zur simultanen homogenen diophantischen Approximation. I, Monatsch. Math. 72 (1968) 254–263.

[19] J. M. Wills, Zur simultanen homogenen diophantischen Approximation. II, Monatsch. Math. 72 (1968) 268–281.

[20] J. M. Wills, Zur simultanen homogenen diophantischen Approximation. III, Monatsch. Math. 74 (1970) 166–171.

[21] J. M. Wills, Zur simultanen diophantischen Approximation., Zahlentheorie (Tagung, Math. Forschungsinst. Oberwolfach, 1970) Ber. Math. Forschungsinst., Oberwolfach, No. 5, Bibliographisches Inst., Mannheim, 1971, pp. 223–227.

[22] Weissman Institute public relations booklet, 1994.

Contact addresses:

Luis Goddyn or Pavol Gvozdjak Dept. of Math. and Stats. Simon Fraser University Burnaby BC V5A 1S6 CANADA

goddyn@math.sfu.ca
gvozdjak@math.sfu.ca

Wojtech Bienia or András Sebő Laboratoire Leibniz-IMAG Université Fourier, BP 53 38041 Grenoble, Cedex 09 FRANCE

                                 bienia@imag.fr
                                 sebo@imag.fr

Michael Tarsi

School of Mathematical Sciences, Department of Computer Science, Tel-Aviv University Tel-Aviv 69978 ISRAEL

                  tarsi@math.tau.ac.il