The Fractional Coloring Number of the Plane
by
Shawna L. Mahan
B.A., University of Colorado, 1988
M S., University of Colorado, 1995
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Mathematics
1995
This thesis for the Master of Science
degree by
Shawna L. Mahan
has been approved
by
Stanley Payne
73!9s
Date
II
Mahan, Shawna L. (M.S., Mathematics)
The Fractional Coloring Number of the Plane
Thesis directed by Associate Professor David C. Fisher
ABSTRACT
Let the unitdistance graph be the graph with nodes that are the points in the
plane and with edges connecting points that are exactly one unit apart. Called the
Other Four Color Problem, the coloring number of this graph is an unsolved problem
from the 1950s. Nelson and Isbell have shown the coloring number is either four, five,
six, or seven. Fisher and Ullman begin work on a related problem, the fractional
coloring number of the plane. They found it to be between 7/2 = 3.5 and
8\/3/tt =4.41064. Hochberg and ODonnell improved the upper bound to 4.35996.
We give an example of a subgraph of the unitdistance graph with a lower bound of
144/41= 3.5122 which further refines the bounds on the fractional coloring number of
the plane to 3.5122 and 4.35996.
This abstract accurately represents the content of the candidates thesis. I recommend
its publication.
Signed
David C. Fisher
in
CONTENTS
Chapter
1 Introduction 1
1.1 Definitions and Terminology 1
1.2 The Coloring Number of the UnitDistance Graph 4
1.3 Bounds on the Fractional Coloring Number of the UnitDistance
Graph 6
2 An Infinite Distance Graph 10
3 Finding the Independence Number of the UnitDistance Graph by an
Iterative Algorithm 17
3.1 Independence Ratio Definitions Concerning the UnitDistance Graph 17
3.2 Dynamic Programming and Max Plus Algebra 20
3.3 Properties of Max Plus Algebra 23
3.4 Detecting Periodicity and Finding oc(s2th) 24
3.5 Determining i(St) and Xf (<Â£4) 32
3.6 Results from the Program .39
4 Finding the Independence Ratio for S 43
5 Conclusion 45
Bibliography 47
IV
1 Introduction
Let 912 be the graph on the plane where every pair of points is joined by an
edge if the Euclidean distance between them is exactly one. This graph is called the
unitdistance graph. We examine the problem called the coloring number of the plane:
What is the coloring number of 912 ? What is the fractional coloring number of
912 ? We present the problems history and previous results. We establish upper and
lower bounds on the coloring number and the fractional coloring number using
subgraphs of the unitdistance graph. Since 912 is an infinite graph we use a result
due to Erdos which says that if a graph G has coloring number equal to k, then there
exists a finite subgraph H with coloring number equal to k [4]. We work on subgraphs
of 912.
1.1 Definitions and Terminology
Let G={V, E) be a finite graph with V(G) denoting the vertex set of G, and
E(G) denoting the edge set of G. Let n(G) be the number of vertices in G. Two
vertices are adjacent if they are connected by an edge.
1
Definition 1.1 A coloring of G is an assignment of a label to each vertex of G such
that no two adjacent vertices receive the same label. The coloring number of G,
denoted j(G), is the minimal number of labels necessary to color G.
Definition 1.2 Let an independent set be a set of nonadjacent vertices. The
independence number, a (G), is the maximum number of vertices in an independent
set.
A coloring of G can be viewed as a partition of the vertices of G into disjoint
independent sets. This, in turn, can be thought of as weights of either 0 or 1 on the
independent sets of G. A fractional coloring is an extension of this coloring definition.
Definition 1.3 A fractional coloring of a finite graph G is an assignment of
nonnegative weights on the independent sets of G such that every vertex is contained
in independent sets whose weights sum to at least one. The fractional coloring number
of G, denoted X/ (G), is the minimum (the infimum) of the weight sums over all
fractional colorings. For an infinite graph, the fractional coloring number is the
supremum over all of its finite subgraphs.
Theorem 1.1 For any finite graph G, we have % f (G) < x (G). [8]
2
Proof Since a coloring may be viewed as a fractional coloring with weights on the
independent sets of 0 or 1, the coloring number is a minimum over a more restricted
set than the fractional coloring number. Q
Theorem 1.2 For a finite graph G, Zf(G) > ~a^jy where n(Q) is the number of
nodes in G and a(G) is the maximum number of nodes in a maximal independent set
ofG. [8].
Proof: Let C be the collection of all independent sets in G and / be an independent
set in C. Then for each I, let Wj be the weight of I in a minimal fractional coloring of
G. Then
n(G)= 2 1< 2 ^a(G)^Wj = a{G)xf(G).
aeG aeGI^a JeCJsa IeC
Definition 1.4 For a finite graph G, the ratio a(G)/(G) is called the independence
ratio and is denoted /(G) We then restate Theorem 1.2 as %f{G)>\Ji{G).
3
1.2 The Coloring Number of the UnitDistance Graph
Edward Nelson (unpublished, 1950) originally examined the coloring number of
the plane. Nelson thought that x (^2)= 4, and worked with John Isbell on the proof
hi 1945, Hadwiger proved that one could tile the plane with tiles formed from seven
regular hexagons arranged so that six hexagons surround a seventh. Isbell used this
tiling to color 9?2 ( Figure 1.1) [12], Color the hexagons, including their boundaries,
with seven colors, {R, B, Y, P, G, P, and W}. A boundary point can be arbitrarily
colored with one of the seven colors. Let a be the length of the side of a hexagon.
Then points within a hexagon are at most 2a apart and hexagons of the same color are
at least ypfa apart.
Figure 1.1 Seven Coloring of the Plane.
4
If l/V7 < a <1/2, then points of the same color are never exactly one apart. This
colors the unitdistance graph with seven colors, therefore x fa2) ? [?]
In 1961 Leo and William Moser [10] found a subgraph of 5R2 that requires four
colors (Figure 1.2). Therefore,we knowx ($R2)^4. Consequently, it is established
that x fa2)= 4, 5, 6, or 7. Since 1961, no substantial improvements have been made
on these results.
1
Figure 1.2Mosers Spindle
Colored with Four Colors
5
1.3 Bounds on the Fractional Coloring Number of the UnitDistance Graph
Since the fractional coloring number is a lower bound for the coloring number,
in 1992 David Fisher and Daniel Ullman [6,7,8] varied the coloring problem slightly by
asking for the fractional coloring number of 912. Using Mosers spindle, they
found ^y(912)> 3.5 (Figure 1.3). The labels {A,B,C,D,E,F,G} depict the independent
sets of the spindle graph. Since the spindle graph has no independent sets with three
vertices, each of the seven independent sets of two vertices has a weight of 1/2. Since
Mosers spindle is a subgraph S of 912, we conclude that the lower bound on its
fractional coloring number is 3.5, that is X/fa2)^ % f(S) = 3.5. [6,7,8]
A,B
F,G
Figure 1.3The Fractional Coloring of Mosers Spindle
where the weights w, for each independent set / are
wA = Wb = wc = wp = We = up = vtp = 1/2
6
To establish upper bounds for the fractional coloring, we will cover the plane
with dense maximal independent sets and and give weights to the independent sets to
determine an upper bound on the fractional coloring of SR2.
Theorem 1.3 (Fisher, Ulltnan, 1992) WSR2)<*4.41064 [7]
71
Proof: Put circles with radius 1/2 on a regular unit triangular grid so that centers of
adjacent circles are exactly 2 units apart (Figure 1.4). Let C be the set of points within
the circles, not including a circles boundary. In C, any point is more than 1 unit apart
from any other point in other circles. There are no two points in C exactly 1 unit
apart. Therefore, we conclude that C is an independent set on SR2.
Figure 1.4  A Dense Independent Set of SR2.
7
In what follows let n be an integer with n> 9. Then for each pair (ij) of
(2i J3j)
integers with 1 < i,j < n, define the translate Cy of C by CtJ = C + ^ n J
Then
for any (x,y) e SR2, Fisher and Ullman [7] showed that (x,y) is in Cy for at least
71
d{n) = In values of i and j, with 1 < ij < n. We may define a fractional
coloring F of SR2 as follows. For each pair (ij) with 1 < i,j < n give Q the weight
1 /d(n). All other independent set of SR2 are assigned the weight 0. Therefore the sum
of the weights is n2/d(n). Since the fractional coloring number is the infimum of the
sum of weights in a fractional coloring, we have
/ 2\ ^ H
xMR ) ^ inf 77~x < inf
' ni9 d(n) nko K
n In
Syf3
n
Hochberg and ODonnell refined this result in 1993. In 1967, Croft found an
independent set which covers 22.936% of the plane [3], Unaware of Crofts work,
Hochberg and ODonnell found the same independent set, and, using an argument
similar to Fisher and Ullmans, they improved the upper bound.
8
Instead of using circles, they used the intersection of a circle and a regular
hexagon with the same center. This new shape is referred to as a roundgon (Figure
1.5). This allowed them to move the roundgons slightly closer together, thereby
increasing the density of the independent set of SR2 .[9] This gives a better bound.
Theorem 1.4 (Hochberg, ODonnell, 1993) ($R2) <4.35995. [9]
Figure 1.5A Dense Maximal Independent Set on the
Plane with Roundgons
9
2 An Infinite UnitDistance Graph
In this section we build a subgraph of the unitdistance graph using Mosers
spindle graph. We create an infinite graph with a gridlike structure. We work on a
finite subgraph of this to improve the known lower bound of the fractional coloring
number established by Fisher and Ullman.
To build the infinite graph we start by covering the plane with a regular unit
triangular grid (Figure 2.1) Each node has an edge to the six adjacent nodes that are
one unit from it.
Figure 2.1 Regular Triangular Cover of the Plane
10
Rotate the Moser spindle (Figure 2.2) and place a spindle on every vertex of
every triangle in the lattice (Figure 2.3). Next, connect the other unit distances created
(Figure 2.4). This creates the unitdistance graph on the plane.
Figure 2.2  Rotating Mosers Spindle.
Figure 2.3 Mosers Spindle on the Lattice.
11
Figure 2.4 is very complex, but it reveals all the possible edges for this
subgraph of the plane. We simplify this graph to make it easier to explore (Figure 2.5)
and call it S. Note that Â£ remains an infinite graph on the plane. We remove most of
the edges and remember the edges as connection rules. The list of connection rules
are assembled in Table 2.1. Each box shows two nodes that are adjacent. Figure 2.6
is a partial representation of the simplified graph S on 9?2.
Figure 2.4 The UnitDistance Graph on the
Plane.
12
2
2
4 4
Figure 2.5 ~ The Simplification Process Wherein the Unit
Distance Graph Becomes the Graph, S
zs A zs. Zs.
A A A A A
Z\ ZS z\ z\
A A A A A
Figure 2.6 The Simplified Representation of S
13
TABLE 2.1
THE CONNECTION RULES FOR THE GRAPH S.
Each box shows two nodes that are adjacent.
A A, A
A A A A A A>
A A A A A A
<1 A A>
<1 <3 A A A. A
<1 A A
A e A A A A
0 A a
14
Definition 2.1 Partition S into infinitely long columns. Choose g adjacent columns
and call this subgraph of S', Sg. (Figure 2.7).
 g columns 
ZS Zs zs. zs
A A A A A
/v
A A A A A
i *
i i
Figure 2.7 An Example of the Strip Graph Sg
Definition 2.2 Partition Sg into h adjacent rows. Call this finite subgraph of Sg, Sgh
(Figure 2.8). Therefore, the subgraph Sgh has g columns and h rows.
+ g columns 
A . A A A .
A . A A A . A
A A A A
A A A A A
Figure 2.8  An Example of Sgj,
h rows
15
We are now ready to work with the new graph on the plane. In the next
section, we give an iterative model which finds the independence number for different
sizes of the finite subgraph Sgh. We use the independence number to find the
independence ratio of the infinitely long strip Sg and find the lower bound on its
fractional coloring number. We choose to work on even column length strips of Sg,
since it is easier to characterize the independent set states and have a more consistant
method for devising formulas.
16
3 Finding the Independence Number of the UnitDistance Graph by
an Iterative Algorithm
We iteratively define the model we use to find the independence number for Sgj,
where g is even. We define and find the independence number of S2M S6,h, Ss,h,
Sio,h, and Si2,h We discuss the formulation of the model and introduce the Max Phis
Algebra structure.
3.1 Independence Ratio Definitions Concerning the UnitDistance Graph
Recah the definition/(G) = or(G)///(G) and the theorem2/ (G)> l//(G). We
intend to improve the unitdistance graphs fractional coloring using this bound. In the
previous section we developed the finite subgraph, Sg,h. We find the independence
ratio of the finite subgraph and use limits to extend the value to the infinite strip graph,
Sg. First we increase the number of rows of Sgj, and define the independence ratio for
the infinite strip graph, Sg. Next, we increase the number of columns of Sg and define
the independence ratio for .S'.
Definition 3.1 Let the independence ratio of Sg be /'(Â£g) = lim i(sg,h)
hHo
17
This makes sense since a(^) is a superadditive function in h and
bounded above by 1. Next, we extend the theorem about finite graphs %f(G)> 1//(G)
to the infinite column strip graph, Sg. Since the independence ratio is a finite value, the
extension is reasonable.
Theorem 3.1 For the infinite column strip graph Sg with g columns, if the
independence ratio of Sg is finite, then y f{s)> r.
i(Sg)
Proof: The fractional coloring number of the infinite graph is at least the same as the
limit of the finite subgraph Sgj's,. From Theorem 1.2 we know the finite graphs
fractional coloring number is bounded by the reciprocal of the independence ratio.
Then we know that as the row size increases, the independence ratio of the infinite Sg
is the limit of the independence ratio for the finite graph Sgj,. The result follows:
Zf(sg) ^ lim Zf(sg.h)
h>oo
1
^ lim"
h>oo i
Also, we are able to make conclusions about S from our results by increasing the
column widths of Sg, starting with , S4, S6, Sg, S!0, and concluding with Sj2
With limits we establish the independence ratio for the infinite graph S.
18
Definition 3.2 For the sequence of strip graphs Sg as g  oo, let the independence
ratio be i(S) = lim .
g>00
Once again, since the independence ratio remains finite, we can extend the
theorem (G)>l/i(G) and the Theorem 3.1 to the infinite graph, S.
Theorem 3.2 For the infinite graph S, if the independence ratio, i(S), is finite, then
Proof: The fractional coloring number of the infinite graph S is at least the same as the
limit of the finite subgraph Sg1 s. From Theorem 3.1, we know that Sgs fractional
coloring number is bounded by the reciprocal of the independence ratio of Sg. By
definition, we know that as the column size increases, the independence ratio of the
infinite S is the limit of the independence ratio for the infinite subgraph Sg, thus finite.
Then, the result follows:
Xf(S) > lim Xf[sg) Jim pr = lim ^ = ^r.
19
The independence ratio of Sg depends on the independence number of the finite
subgraph Sg>h Therefore, we find the independence number of the finite subgraph Sgh.
Since Sgh has a gridlike structure, we can build row by row. Once we have
the independence number for the finite graph Sgh, we quickly find the independence
ratio and the fractional coloring bound for Sg by applying the previous definitions and
theorems.
Building by rows is an iterative process. The nodes that are added to
the maximum independent set depend on the placement of the nodes in the previous
row and are determined by the connection rules in Table 2.1. Since we are maximizing
a parameter, this type of iterative modeling is categorized as dynamic programming.
3.2 Dynamic Programming and Max Plus Algebra
An iterative algorithm has the form x(/ + l) = f(x(t)) for t0,...n for which the
initial vector x(0) is known. The function generates a set of vectors {x(l), x(2),
x(3),..., x(n)}. An iteration is defined as a sequence of component updates so that each
vector element is updated at least once. We use a matrix called a transfer matrix to
20
generate the vectors. Therefore, Ax, = f(x(t)). Thus, we depict our canonical
iterative algorithm as following dynamic program (Equation 3.1).
xf+1=Ax, t = l,...,/i and
x0 known. (3.1)
Then A is an m x m transfer matrix and xt is an m x 1 vector. Clearly, each succeeding
vector depends on the preceding vector. The matrix A is irreducible andcyclic; that
is, Am+P = Am for the smallest possible p. [1] One of our goals is to determine this
period length, p.
Since normal matrix row and column multiplication operations do not make
much sense in this setting, instead we use Max Plus Algebra operations. Addition of
each of the matrixs row elements to the vectors column elements replaces
multiplication. Instead of adding these values, we take the maximum of these numbers
to find the successive vectors elements. Hence, the normal matrix multiplication
procedure is replaced by the Max Plus Algebras binary operations: addition and
maximization.
Let $Rmax denote the Max Plus Algebra structure; let (pronounced otimes)
represent addition in $Rmax ; and let ( pronounced oplus) represent maximum in
5Rmax From this point forward, all algebraic operations are in this algebra. If the
21
context is not clear, we use the symbols and . The properties and definitions of
$Kmax are discussed in the next section.
Let Tg be the transfer matrix for Sgih. We reformulate Equation 3.1 into
Equation 3.2. Mathematically, we transform the connection rules from Table 2.1 into
Equation 3.3 to find the elements of Tg.
x,+jTgX^ t 1,.. .,&q,. .,kQ~\~p
x, known. (3.2)
Let T
g
if
number of nodes state i adds to independent set
if it can exist under state j.
co if state / cannot exist under state j.
(3.3)
Many of the matrix elements will be oo, so we use the properties given in the
next section concerning oo to determine vector elements. Since vector elements are
decided by maximization, it is rare to get oo as a vector element. We find each
element of vector x,+i with Equation 3.4.
Let
Xf+i, =max
Ta,i +X'.T* +Xh>.T*,. +x
Si.2
,)
(3.4)
22
For the Ath iteration of the algorithm, the vector x* keeps track of the maximum
number of vertices for all the possible ending states of the maximal independent sets.
Row / of the vector indicates the stage of readiness for ending state Therefore, at
the Ath iteration, the largest number at row j in the vector x* is the maximal number of
vertices possible with ending state j for the graph Sgtk This conclusion leads us to the
following definition about finding the independence number of Sgj. Since we really
want the independence ratio of Sg, we divide the following result by the number of
nodes in Sg,k and apply Definition 3.1.
Definition 3.3 Take the maximum element from each vector Xh to find a
3.3 Properties of Max Plus Algebra
What properties do the binary operations and have? First, means
addition, that is ab = a +b Second, means the maximum of a set of numbers,
that is a @b = max (a, b). The set of numbers for 93max is the real number set
extended by oo We frequently use oo in Max Plus models, so we must understand
its behavior for and . Adding a number to oo has no effect, a  oo =
23
aHoo=oo. Under maximization,oo is the identity element, a  co = a.
Adding oo to oo has no effect, that is oo oo = oo, and when comparing two
oo s under maximization, we obtain oo, that is oo oo = oo [1]
The operation is associative, commutative, has identity element 0, inverse
element a, and distributes over . The operation is associative, commutative,
and has identity element oo Given a& oo, then a@b=b establishes a partial
ordering on $Rmax, that is if a@b=b then we can presume that a
3.4 Detecting Periodicity and Finding a (^j,)
We begin employing the model for S2. Call all the possible maximal independent
sets of S2 states. Each state (Figure 3.1) is assigned a number. The rows and columns
of T2 then represent each state of S2. For example, the first row of T2 holds the
elements for state 0, the first column holds the elements for state 0, the second row
holds the elements for state 1, etc.
24
o
0=
1= /\
2= A O
3= A
4= A
5= A
= A
7= A
Figure 3.1 Number Assignment to Maximal
Independent Sets of
To find the independence number for Szh we let g = 2 in Equation 3.2. The
matrix T2 is the 8 x 8 matrix shown in Equation 3.5. The elements of the initial vector
xi (Equation 3.6) are the sizes of the two column and one row maximal independent
sets from Figure 3.1. The elements in T? are found by Equation 3.3. The dashes in
Equation 3.5 indicate oo and mean that the state / could not exist under or next to
state j.
25
states 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1
2 1 1 1 
3 1 1 1 1 1 1 
4 1 1
5 ' 2 2
6 2
7 2  2
states 0 1 2 345 67
y[0 1 1 1 1 2 2 2]t
(3.5)
(36)
Now we exercise the iterative model, and begin finding the vectors 2,...,ko+p.
We need to determine when the system begins cycling, that is, find a vector that is only
a constant off from a previous vector. Recall that the elements of each vector are
determined by Equation 3.4. So, the vectors x2, x3, X4, X5, and x6 follow:
x2 = T2Xj = [2 3
x3 = T2x2 = [3 4
x4 = T2x3 = [4 5
x5 = T2x4 = [6 7
and x6= T2x5 = [7
2 3 2 3 2 3]r,
4 4 3 4 4 4]7 ,
5 5 5 6 5 6]T ,
6 7 6 7 6 7]r,
8 8 8 7 8 8 8]7
26
Notice that xs has the same pattern as the elements x2 and that each element
differs from the corresponding element in x2 by 4. We can say then x5 = x2 4.
Notice xe has the same pattern of elements as X3 and each corresponding element in x$
differs from X3 by 4. Similarly, x6 = x3 4. At this point, we have detected the
periodic behavior of our model Each new vectors elements will be four more than
the third preceding vectors corresponding elements, that isp=3. Looking at the
seventh vector we see that x7 = T2x6 = T2 (4 <8> x3) = 4T2x3 = 4x4 .
hi general, for k >5, we can conclude that xk = 4 x*_3 By Definition 3.3 we
choose the largest of all the elements in each x*, thereby obtaining a (?2 j ) = 2 ,
a(522)=3, a(523)=4, a(52i4)6, a(52>5)= 7 which is 4 more than a(s22),
a(s26}= 8 which is 4 more than a (s ),aad a{^2,i) = 10 which is 4 more than
a(S,2 4). Then for k>5, we can see that the independence number will also cycle in
periods of three, that is a(1S'2Jt) = yrxA =yr(xJfc_3<8>4) =a(
results, we see that the independence number goes up 4 for eveiy 3 rows, or 4 nodes
enter the maximum independent set for every 12 nodes in S2. For the number of rows
/ \ a(s2Jk) T^+Od) 1 fi'S
k, k>5, we find that m
v 4k Ak 3 \k)
27
3.1 we know /'(.S' ) = lim /(s )= Then using Theorem 3.1, we determine the
2 fc>00 2>* 3
bound on the fractional coloring number, x (^2) "7T=3
The pattern of states that give /(S2) is shown in Figure 3.3. This graph of the
maximum independent set clearly proves that 4/12=1/3 is the independence ratio for
S23. Finding the pattern of states for the larger columns widths 4, 6, 8, 10, and 12 is
extremely difficult due to the large number of possible states and possible
combinations even when the independence number and beginning state are known.
3 o A
2 A o
5 . A
3 A 0
2 o A
5 A
Figure 3.3 The Maximum Independent Set for S2,h
28
Once we detect periodicity in our vectors, we stop the iterations. The period p
is the difference between the vector numbers, and q is the difference in the maximum
elements of each vector. We use these two numbers in tandem with Theorem 3.3 and
Corollary 3.1 to find the independence ratio and the bound on the fractional coloring
number of Sg,h.
Theorem 3.3 Given an initial vector Xi, iteratively define x t+1 = A x k If there
exists a k0, p, and q such that x =q\ , then xA+ =q xk for all k>k0.
*0 + P' *0 F
Frnther, given a vector y, let ak =yT\k Then ak =A:^+0(l). [2]
Proof: For any k>k0 let k = k' + Ip for integer / and k with 0
the largest integer such that k' > k. Then k' < k + p. Then ak = yTxk
= yr(? **) = = yT(iq *) = k + a* = ^ +
( k'q^
ak'
P \ P J
kq
Hence, for all k>0, ak has only a finite number of values, so we have the result. I I
P
The ratio qj p is called the eigenvalue of the Equation 3.1 under Max Plus
Algebra [2], We notate the eigenvalue as /i(Tg) to indicate that it is associated to our
29
particular transfer matrix T?. We modify the above theorem to apply to our specific
parameter; that is, we want to find the maximum independent ratio for Sg.
Corollary 3.1 Let g be an even column width for the strip graph Sg. Then the
/ x M?g)
independence ratio for Sg is found by i\SgJ=.
Proof: Since the subgraph Sg,h has a gridlike structure, every two column and one
row subgraph contributes 4 total nodes to n(Sg,\). Given that g is the column width,
and it is even, we know for g=2 that n(S2,i) = 4, for g=4 that nfS^J = 8, and for
g = 6 that n(Se,x) = 12. Therefore, by induction n(Sgi\) = 2g. Since k is the number of
rows in the graph Sg,k, then n(Sg,\J = 2kg. The independence ratio is defined as the
ratio between the indepencence number of the finite graph and the size of the graph.
m,s
Then by applying Definition 3.1, the result follows for i(Sg).
{ \ i \ a(5*.*) 4rg)
2 kg
30
We use the dynamic programming model to find the eigenvalue, q/p. Then we
use the definition ak kqjp to find our parameter . We place these values
into Corollary 3.1 to find the independence ratio of Sg. The algorithm to find the
independence ratio of Sg follows:
STEP 1. Initialization. Find the matrix and the initial vector xi. Elements of
are determined by Equation 3.3. The elements of Xj are determined by the number
of nodes in each maximal independent set of Sg.
STEP 2. Find the Period. Apply the iterative dynamic program (Equation 3.2),
that is xA+l=TgX* for Xj known, until we find k and ka where xA = x^ +q. Let
P = kk0.
STEP 3. Find the Eigenvalue. Determine q, the difference in the maximum
elements of the beginning and ending vectors in the cycle. Then A^Tg)=q/p.
STEP 4. Find the Independence Ratio of Sg>. Apply Corollary 3.1, /(s )=.
\ S! 2g
STEP 5. Find the Fractional Coloring Numbers. Bound on Sg. Apply Theorem
3.1, that is Repeat Step 0 to Step 5 until a forced pattern of
independence sets appears, for g=2, 4, 6, ...,2j.
31
STEP 6. Find the Fractional Coloring Numbers Bound on S. Apply Theorem 3.2,
XfWzi/M. j.
We now apply this model to the remaining strip graphs of S. In the next section,
we develop the solution for S4. We show the matrix T4 and the first nineteen vectors
generated by the dynamic program. We then find its eigenvalue, the independence
ratio, and the fractional coloring number bound.
3.5 Determining /( S4) and Xf{$4)
As stated previously, we find the independence ratio for the even column strip
graphs. Since Â£4 could be considered to be two strips of S2 side by side, then an S4
state number is made from two S2 state numbers, which produces a two digit octal
number. For example, the octal number 17 (Figure 3.3) represents a three node
maximal independent set of S4. But not all 64 states of S4 are valid. The fifteen
connection rules laid out in Table 2.1 rule out some combinations. Consequently, only
39 out of the 64 possible states are valid and are supplied in Table 3.1. For example,
the octal number 26 (Figure 3.4) is not a valid state because two adjacent upper
32
triangle nodes are erroneously placed into an independent set. We could put these
states into T4 and fill their rows and columns with 00, or we could leave them out
since it is unlikely that 00 would he the maximum independent number for any
iteration.
We choose to work with the 39 x 39 matrix, denoted T4 and shown in Table
3.2. The elements of the initial vector xi given in Table 3.3 are the possible
contributions of the ordered two digit octal numbers of the 39 valid states to the
independent set. For example, state 17 (Figure 3.3) contributes 3 nodes to the
independent set, so element ( =3 since state 17 is in the fourteenth row. In the
matrix T4 (Table 3.2), the element T4u = 3 since row state 17 can exist under the
column state 02, and row state 17 contributes 3 nodes to an independent set. The
O
Figure 3.3 State 17
Figure 3.4 State 26
33
matrix element T, = oo since row state 27 cannot exist under column state 32.
420,24
Notice both states share the number 2. States with the same number; states with
similar pattern of 1 and 5, 2 and 6, 3 and 7; and states 4 and 5, 4 and 6, and 4 and 7
cannot exist under each other nor can they exist side by side.
Table 3.3 lists vectors Xi through X19. The first element of each vector has
been subtracted from all the other elements in the same vector. This procedure
exposes the pattern of elements in each vector. This facilitates our ability to find the
cycle length between the vectors. We see that vector 13 and vector 19 have the same
pattern of elements and that their maximum elements differ by 14.
34
TABLE 3.1
THE 39 VALID STATES FOR S4.
00 10 20 30 40 50 60 70
01 12 21 31 41 52 61 71
02 13 23 32 42 53 63 72
03 14 24 34 43
04 16 25 35
05 17 27 36
06
07
35
TABLE 3.2
The Matrix T4
00 01 02 03 04 05 06 07 10 12 13 14 16 17 20 21 23 24 25 27 30 31 32 34 35 36 40 41 42 43 50 52 53 60 61 63 70 71 72
00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
01 1  1 1 1 1 1  1 1 1  1 1  1 1  1 1  1 1    1  1 1  1
02 1 1  1  1  1       1     1 1  1 1  1    1 1 
03 1 1 1  1 1 1  1 1 1 1  1 1  1 1       1 1 1  I 1  1 1    
04 1  1    1 1   1     1  1    1  1  1 1  1   1  1
05 2  2            2    2  2    2  2     2   2  2
06 2        2        2    2    2      2  
07 2  2      2  2    ' 2           2  2  2  2      
10 1 1 1 1 1 1 1 1       1. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1    1 1 1 1
12 2 2  2 2 2     2 2  2       2 2 
13 2 2  2 2 2 2 2  2 2       2 2 2     2 2    
14 2  2            2     2  2    2  2     2   2  2
16 3 3 3 3
17 3  3            3           3  3     3     
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1      1 1 1 1 1 1
21 2  2 2 2  2 2 2  2 2  2
23 24 2 2 2 2 2 ' 2 2 2  2 2 2 2 2 2 2 2
25 3  3 3 3
27 3  3
30 1 1 1 1 1 1 1 1 1 1 1 1 i 1 1 1 1 1 1 1       1 1 1 1 1 1 1 1 1 1  
31 2  2 2 2  2 2       2  2 2  2       2  2 2    2  2   
32 2 2  2     2 2 2 2  2 2  2     
34 2  2      2 2     2            2 2  2 2  2     
35 3  3            3            3  3     3  
36 3
40 1 1 1 1 1 1 1
41 2  2 2
42 2 2 2
43 2 2 2
50 2 2 2 2 2 2
52 3 3  3 2 2 2
53 3 3 3
60 2 2 2 2
61 3  3 3
63 3 3 3
70 2 2 2 2 2 2 2
71 3  3 3
72 3 3  3
TABLE 3.3
THE VECTORS Xi THROUGH xw FOR SA.
The first element of each vector is subtracted from all other elements in the vector.
Vector 13 and vector 19 are exactly the same.
Xl x7 x^ X4 xs X
00 0 3 5 8 10 13 15 17 Subtracted elements 20 22 24 27 29 31 34 36 38 41 43
00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
01 1 1 1 1 1 1 1 1 0 1 1 l l 1 1 1 1 1 1
02 1 1 1 1 1 0 1 1 0 1 1 0 l 1 0 1 1 1 1
03 1 1 1 1 1 1 1 1 0 1 1 1 l 1 1 1 1 1 1
04 1 0 1 0 1 0 0 1 0 0 1 0 l 1 0 0 1 0 1
05 2 1 2 1 ,2 1 1 2 1 1 2 1 2 2 1 1 2 1 2
06 2 0 2 0 2 0 1 1 1 1 2 0 1 1 1 1 2 0 1
07 2 1 2 1 ,2 1 1 2 1 1 2 1 2 2 1 1 2 1 2
10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
12 2 2 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2
13 2 2 2 2 2. 2 2 2 1 2 2 2 2 2 2 2 2 2 2
14 2 1 2 1 2 1 1 2 1 1 2 1 2 2 1 1 2 1 2
16 3 1 3 1 3 1 2 2 2 2 3 1 2 2 2 2 3 1 2
17 3 2 2 2 2 2 2 3 1 2 2 2 2 3 2 2 2 2 2
20 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1
21 2 2 2 1 1 1 1 2 1 1 2 1 1 . 2 1 2 2 1 1
23 2 2 2 1 1 1 1 2 1 1 2 1 1 2 1 2 2 . 1 1
24 2 0 2 0 . 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1
25 3 1 3 1 2 1 2 2 2 2 2 1 2 2 2 2 2 1 2
27 3 1 3 1 2 1 2 2 2 2 2 1 2 2 2  2 2 1 2
30 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
31 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2
32 2 2 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2
34 2 1 2 1 2 1 1 2 1 1 2 1 2 2 1 1 2 1 2
35 3 2 2 2 . 2 2 2 3 1 2 2 2 2 3 2 2 2 2 2
36 3 1 3 1 3 1 2 2 2 2 3 1 2 2 2 2 3 1 2
40 1 1 1 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0
41 2 2 2 2 1 1 1 2 1 2 1 1 1 2 1 2 2 1 1
42 2 1 1 1 1 0 1 1 0 1 I 1 1 I 0 1 1 1 1
43 2 2 2 2 1 1 1 2 1 2 1 1 1 2 1 2 2 1 1
50 2 2 2 2 1 1 1 2 1 2 1 1 1 2 1 2 2 1 1
52 3 2 2 2 2 1 2 2 1 2 2 2 2 2 1 2 2 2 2
53 3 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2
60 2 1 1 1 1 1 1 1 0 1 1 1 1 2 0 1 1 1 1
61 3 2 2 2 2 2 2 2 1 2 2 2 2 3 1 2 2 2 2
63 3 2 2 2 2 2 2 2 1 2 2 2 2 3 1 2 2 2 2
70 2 2 2 2 1 1 1 2 1 2 1 1 1 2 1 2 2 1 1
71 3 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2
72 3 2 2 2 2 1 2 2 1 2 2 2 2 2 1 2 2 2 2
37
The vectors xi3 and X19 are 6 iterations apart with a difference of 14 in their
maximum elements. Therefore, from Theorem 3.1 and Corollary 3.1, p = 6 and q =
14. Then i(S4)=a(t4 )flg= 7/24, and we conclude that
%'f(s4)> 24/7=3.4285. The states of Â£4,6 that result in the cyclic independent sets are
shown in Figure 3.5
61 <1 0 <
30 i> 0 O 0
16 0 A
23 > 0 J> 0
52 /V 0 ^
07 A 0 A
61 t> 0 >
Figure 3.5 Periodic Independent Sets States of S4
with its Two Digit Octal State Number
The next even column strip graph is S6. The number of possible combinations of
states is 83 = 512. Out of the 512 combinations, only 215 states are valid. Even so,
38
the matrix T6 is too large to do by hand. We wrote a program to perform the Max
Plus Algebra, to detect the periodicity, and to find the periodic pattern of the
independent set states for Sa, S6, Sg, S\0, and Sn The matrix Tu is too large and the
program works too slowly for the VAX computer to be able to detect periodicity.
3.6 Results from the Program
For S(,, the vectors become cyclic at X28 with a period of 10. The difference in
the maximum elements of xio and x28 is 62. Therefore, /?=18 and # 62. Now we can
compute the independence ratio for S6, i(S6)=A(T6)/2g= =31/108 and
conclude that (iS^j^lOS/Sl^ASSS. The pattern of states for the independent set
of iSlS'io is shown in Figure 3.6.
The number of possible states for Ss is 84 = 4096. Only 1136 states of the
possible 4096 combinations are valid. The vectors begin cycling at xi9 with a period of
10. The difference in the maximum element of the vectors X19 and x9 is 46. The
independence ratio for S$ is i(ss)=/L(T8)/2g=
46/10
= 23/80, and the fractional
2 8
39
coloring numbers bound is % f (^s) 80/23=3.4782. The pattern of states for the
independence ratio of Sg,io is shown in Figure 3.7.
143 A Z\ Z^p o
232 o A <3 0 0
705 A o A
123 O o o /\
271 A o A A
502 A 0 > 0
061 A o A o
532 A o A
325 o A A
143 o Z\ o z^
Figure 3.6 Periodic Independent Set for S6 with its Three
Digit Octal State Number.
40
0170 o A 0 t> i> 0 >
6306 A. Â£> 0 D> 0 O
1271 ^ 0 > i> 0 i>
2312 A o o O o
5235 A 0 0 0 Â£> t>
0710 0 < A o A o
6036 A <
1721 O > 0 t> 0
2132 o A 0 T> 0 0 0
5325 ^ /\ o o
0170 o A <1 0
Figure 3.7 Periodic Independent Set for S$ with its Four
Digit Octal State Number
The number of possible states for 50 is 85 = 32768. Only 6097 states of the
possible 32,768 combinations are valid. The vectors begin cycling at x3i with a period
of 7. The difference in the maximum elements of the vectors x3i and x24 is 40. The
41
independence ratio for Â£10 is /(^10)=^T10)/2g= ^=2/7, and the fractional
coloring numbers bound is (^10) 7/2=3..5.
The number of possible states for Sy2 is 86 = 262,144. Only 32,529 states of
the possible 262,144 combinations are valid. The vectors begin cycling at x2i with a
period of 6. The difference in the maximum elements of the vectors x2i and X15 is 41.
The independence ratio for Sn is i{sn)=^Tn)/2g= ^ =41/144, and the
Zi *
fractional coloring numbers bound is Xf (^12) 144/41=3.5122.
42
4 Finding the Independence Ratio for S
Is there a forced pattern in any of the patterns of states in the independent
sets of Sg,h? If we look at the states for the independent set of Sg, we find a pattern
that is forced (Figure 4.1). This pattern is three columns wide and ten rows long and
results in an independence ratio of 17/60. From Definition 3.2 which states that
i(S) = lim z(iSr_) and from Theorem 3.2 which states that % f (S) > 1Ji(S), we can
gxn Sl
theorize that the fractional coloring number is at most 60/17 = 3.5294.
43
0170 i O o A o Z\>
6306 A A A O
1271 o o A A A
2312 A o AA O O
5235 A o A A*A
0710 A o A* A o A o
6036 .A o /S A A
1721 O A A o A o
2132 o A A A
5325 tCs A A O
0170 o A o A 0 >
Figure 4.1 The Three Columns and Ten Rows Forced Pattern
Found in the Independent Set of Sg.
44
5 Conclusion
Although we increase the known lower bound on the fractional coloring
number of the unitdistance graph, the gain is slight. It is conjectured that by using an
even more complex graph like S but with two more rotated Moser spindles, the
increase in the lower bound will be more substantial (Figure 5.1 and Figure 5.2).
The model and algorithm to solve this would be similar to the one developed in
Section 3.4. Generate states and state numbers corresponding to maximal independent
sets from the smallest meaningful strip of the infinite simplified graph (Figure 5.2).
The transfer matrix would be considerably larger and the program would need more
time to solve the iterative system for periodicity.
This modeling procedure may be generalized and adapted to find similar
parameters of a graph such as the coloring number of a graph, the fractional coloring
number of a graph, the domination number of a graph, the independence domination
number of a graph, and the 2packing number of a graph.
45
Figure 5.1 Placing Mosers Spindle Graph in Three
Directions on the Regular Triangle Cover of the Plane.
Figure 5.2 The Simplified Graph with Removed Edges.
46
Bibliography
[1] Baccelli, Francois, Guy Cohen, Geert J. Olsder, and JeanPierre Quandrant.
Synchronization and Linearity: An Algebra for Discrete Event Systems. John Wiley
and Sons, Chicester, 1992.
[2] Chung, Misoo. Eigenvalues and Eigenvectors of the Max Plus Algebra.
thesis, University of Colorado, Denver, 1995.
M.S.
Croft, Hallard. Incidence Incidents. Eureka: The Archimedeans Journal 30
1967): 2226.
[4] De Bruiin, N.G. and Paul Erdos. A Color Problem for Infinite Graphs and a
Problem in the Theory of Relations. Nederl. Akad Wetensch. Proc., Series A 54
(1951): 371373.
[5] Fisher, David, Melanie Marchant, and Jennifer Ryan. A Column Generating
Algorithm for Finding Fractional Colorings of Random Graphs. Congressus
Numerantium 89 (1992): 245253.
[6] Fisher, David and Daniel Ullman. Bounds on the Fuzzy Chromatic Number of
the Plane preprint
0
The Fractional Chromatic Number of the Plane. Geombinatorics 2
1992): 812.
[8] ____. The Fuzzy Chromatic Number of the Plane preprint.
[91 Hochberg, Robert and Paul ODonnell. A Large Independent Set in the Unit
Distance Graph. Geombinatorics 3 (1993): 8384.
[10] Moser, Leo and William Moser. Problems for Solution. Canadian Bulletin of
Mathematics 4 (1961): 187189.
[11] Soifer, Alexander. Colorado Mathematical Olympiad: the First 10 Years and
Further Explorations. Center for Excellence in Mathematical Education, Colorado
Springs, 1994.
47
Chromatic Number of the Plane: A Historical Essay Geombinatorics 1
1315.
48

PAGE 1
The Fractional Coloring Number of the Plane by Shawna L. Mahan B.A., University of Colorado, 1988 M.S., University of Colorado, 1995 A thesis submitted to the Faculty of the Graduate School of the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Mathematics 1995
PAGE 2
This thesis for the Master of Science degree by Shawna L. Mahan has been approved by David C. Fisher Stanley Payne arvey Greenberg / 13/9.sDate ii
PAGE 3
Mahan, Shawna L. (M.S., Mathematics) The Fractional Coloring Number of the Plane Thesis directed by Associate Professor David C. Fisher ABSTRACT Let the unitdistance graph be the graph with nodes that are the points in the plane and with edges connecting points that are exactly one unit apart. Called the Other Four Color Problem, the coloring number of this graph is an unsolved problem from the 1950s. Nelson and Isbell have shown the coloring number is either four, five, six, or seven. Fisher and Ullman begin work on a related problem, the fractional coloring number of the plane. They found it to be between 7/2 = 3.5 and s.f3/tr =4.41064. Hochberg and O'Donnell improved the upper bound to 4.35996. We give an example of a sub graph of the unitdistance graph with a lower bound of 144/41= 3.5122 which further refines the bounds on the fractional coloring number of the plane to 3.5122 and 4.35996. This abstract accurately represents the content of the candidate's thesis. I reco=end its publication. Signed David C. Fisher iii
PAGE 4
CONTENTS Chapter 1 Introduction 1 1.1 Definitions and Terminology 1 1.2 The Coloring Number of the UnitDistance Graph 4 1.3 Bounds on the Fractional Coloring Number of the UnitDistance Graph 6 2 An Infinite Distance Graph 10 3 Finding the Independence Number of the UnitDistance Graph by an Iterative Algorithm 17 3.1 Independence Ratio Definitions Concerning the UnitDistance Graph 17 3.2 Dynamic Programming and Max Plus Algebra 3.3 Properties of Max Plus Algebra 3.4 Detecting Periodicity and Finding a(Sz,h) 3.5 Determiningi(S.J and x1 (S4) 3.6 Results from the Program 4 Finding the Independence Ratio for S 5 Conclusion Bibliography iv 20 23 24 32 39 43 45 47
PAGE 5
1 Introduction Let 9t 2 be the graph on the plane where every pair of points is joined by an edge if the Euclidean distance between them is exactly one. This graph is called th.e unitdistance graph. We examine the problem called the coloring number of the plane: What is the coloring number of 9\2 ? What is the fractional coloring number of 9{2 ? We present the problem's history and previous results. We establish upper and lower bounds on the coloring number and the fiactional coloring number using subgraphs of the unitdistance graph. Since 9\2 is an infinite graph we use a result due to Erdos which says that if a graph G has coloring number equal to k, then there exists a finite sub graph H with coloring number equal to k [ 4]. We work on sub graphs of 9\2 1.1 Definitions and Terminology Let G= {V,E} be a finite graph with V(G) denoting the vertex set ofG, and E(G) denoting the edge set of G. Let n(G) be the number of vertices in G. Two vertices are adjacent if they are connected by an edge. 1
PAGE 6
Defmition 1.1 A coloring of G is an assignment of a label to each vertex of G such that no two adjacent vertices receive the same label The coloring number of G, denoted X (G), is the minimal number oflabels necessary to color G. Definition 1.2 Let an independent set be a set of nonadjacent vertices. The independence number, a (G), is the maximum number of vertices in an independent set. A coloring of G can be viewed as a partition of the vertices of G into disjoint independent sets. This, in tum, can be thought of as weights of either 0 or 1 on the independent sets of G. A fractional coloring is an extension of this coloring definition. Definition 1.3 A fractional coloring of a finite graph G is an assignment of nmmegative weights on the independent sets of G such that every vertex is contained in independent sets whose weights sum to at least one. The fractional coloring number ofG, denoted x1(G), is the minimum (the infimum) of the weight sums over all fractional colorings. For an infinite graph, the fractional coloring number is the supremum over all of its finite sub graphs. Theorem 1.1 For any finite graph G, we have x 1(G) :s; x (G). [8] 2
PAGE 7
Proof: Since a coloring may be viewed as a fractional coloring with weights on the independent sets ofO or 1, the coloring number is a minimum over a more restricted set than the fractional coloring number. D Theorem 1.2 For a finite graph G, x f (G) :2: where n(G) is the number of nodes in G and a( G) is the maximum number of nodes in a maximal independent set ofG. [8]. Proof Let C be the collection of all independent sets in G and I be an independent set in C. Then for each I, let WJ be the weight of I in a minimal fractional coloring of G. Then n(G)= L 1:<> L LW1=LLw1 :<>a(G)Lw1 = a(G)x1(G). aeG aeGl:'JO: leC/;,a JeC Definition 1.4 For a finite graph G, the ratio a(G)jn(G) is called the independence ratio and is denoted i(G). We then restate Theorem 1.2 as xf(G):2:1/i(G). 3
PAGE 8
1.2 The Coloring Number of the UnitDistance Graph Edward Nelson (unpublished, 1950) originally examined the coloring number of the plane. Nelson thought that x ( 912 ) = 4, and worked with John Isbell on the proof In 1945, Hadwiger proved that one could tile the plane with tiles formed from seven regular hexagons arranged so that six hexagons surround a seventh. Isbell used this tiling to color 912 (Figure 1.1) [12]. Color the hexagons, including their boundaries, with seven colors, {R, B, Y, P, G, P, and W}. A boundary point can be arbitrarily colored with one of the seven colors. Let a be the length of the side of a hexagon. Then points within a hexagon are at most 2a apart and hexagons of the same color are at least J?a apart. Figure 1.1 Seven Coloring of the Plane. 4
PAGE 9
If 1/ .J7 1/2, then points of the same color are never exactly one apart. This colors the unitdistance graph with seven colors, therefore x ( \R2 ) 7 [7]. In 1961 Leo and William Moser [10] found a subgraph of \R2 that requires four colors (Figure 1.2). Therefore, we know x Consequently, it is established thatx (!R2)= 4, 5, 6, or 7. Since 1961, no substantial improvements have been made on these results. 2 1 Figure 1.2Moser's Spindle Colored with Four Colors 5 2
PAGE 10
1.3 Bounds on the Fractional Coloring Number of the UnitDistance Graph Since the fractional coloring number is a lower bound for the coloring number, in 1992 David Fisher and Daniel Ullman [6, 7 ,8] varied the coloring problem slightly by asking for the fractional coloring number of ll\2 Using Moser's spindle, they foundxf(ll\2);::3.5 (Figure 1.3). Th.elabels {A,B,C,D,E,F,G} depict the independent sets of the spindle graph. Since the spindle graph has no independent sets with. three vertices, each of the seven independent sets of two vertices has a weight of 1/2. Since Moser's spindle is a snbgraph S of ll\2 we conclude that the lower bound on its fractional coloring numberis 3.5, th.at is x f(llt2 );:: X f(S) =3.5. [6,7,8] A,B C,D F,G A,G B,C Figure 1.3The Fractional Coloring ofMoser' s Spindle where the weights w, for each independent set I are WA =wB =We =wo =WE =WF =we;= 1/2 6
PAGE 11
To establish upper bounds for the fractional coloring, we will cover the plane with dense maximal independent sets and and give weights to the independent sets to determine an upper bound on the fractional coloring of \R2 Proof Put circles with radius 112 on a regular unit triangular grid so that centers of adjacent circles are exactly 2 units apart (Figure 1. 4 ). Let C be the set of points within the circles, not including a circle's boundary. InC, any point is more than 1 unit apart from any other point in other circles. There are no two points in C exactly 1 unit apart. Therefore, we conclude that C is an independent set on \R 2 0000 0 000 0 0000 Figure 1.4 A Dense Independent Set of \R 2 7
PAGE 12
In what follows let n be an integer with n ;o: 9. Then for each pair ( i ,j) of ( 2i .f3 I integers with 1::;:, i,j::;:, n, define the translate Cij ofC by Cu = C + l;, nl J Then for any ( x,y) E W2 Fisher and Ullman [7] showed that ( x ,y) is in C ij for at least d(n) = sJJ n2 2n values ofi and}, with 1::;:, i,j::;:, n. We may define a fractional coloring Fn of WZ as follows. For each pair (i,.i) with I::;:, i,j::;:, n give Cij the weight 1/d(n). All other independent set of W2 are assigned the weight 0. Therefore the sum of the weights is n2/d(n). Since the fractional coloring number is the infimum of the sum of weights in a fractional coloring, we have D Hochberg and O'Donnell refined this result in 1993. In 1967, Croft found an independent set which covers 22.936% ofthe plane [3]. Unaware of Croft's work, Hochberg and O'Donnell found the same independent set, and, using an argument similar to Fisher and Ullman's, they improved the upper bound. 8
PAGE 13
Instead of using circles, they used the intersection of a circle and a regular hexagon with the same center. This new shape is referred to as a roundgon (Figure 1.5). This allowed them to move the roundgons slightly closer together, thereby increasing the density of the independent set of 912 [9] This gives a better bound. Theorem 1.4 (Hochberg, O'Donnell, 1993) x(\112)::;4.35995. [9] Figure 1.5A Dense Maximal Independent Set on the Plane with Rmmdgous 9
PAGE 14
2 An Infinite UnitDistance Graph In this section we build a subgraph of the unitdistance graph using Moser's spindle graph. We create an infinite graph with a gridlike structure. We work on a finite sub graph of this to improve the known lower bound of the fractional coloring number established by Fisher and Ullman. To build the infinite graph we start by covering the plane with a regular unit triangular grid (Figure 2.1) Each node has an edge to the six adjacent nodes that are one unit from it. Figure 2.1 Regular Triangular Cover of the Plane 10
PAGE 15
Rotate the Moser spindle (Figure 2.2) and place a spindle on every vertex of every triangle in the lattice (Figure 2.3). Next, com1ect the other unit distances created (Figure 2.4). This creates the unitdistance graph on the plane . Figure 2.2 Rotating Moser's Spin.dle. Figure 2.3 Moser's Spindle on the Lattice. 11
PAGE 16
Figure 2.4 is very complex, but it reveals all the possible edges for this sub graph of the plane. We simpli:fY this graph to make it easier to explore (Figure 2.5) and call itS. Note that S remains an infinite graph on the plaue. We remove most of the edges and "remember" the edges as connection rules. The list of connection rules are assembled in Table 2.1. Each box shows two nodes that are adjacent. Figure 2.6 is a partial representation of the simplified graphS on iR2 Figure 2.4 The UnitDistance Graph on the Plane. 12
PAGE 17
4 2 1 ===t7 ,3 5 6 4 Figure 2.5 The Simplification Process Wherein the Unit Distance Graph Becomes the Graph, S .6.6.6 6.6.6 .6.6.6.6. Figure 2.6 The Simplified Representation of S 13
PAGE 18
TABLE2.1 TIIE CONNECTION RULES FOR THE GRAPHS. Each box shows two nodes that are adjacent. c{:; 4 ., !':, !':,..!':, i">i"> 4 .8,.1'::, i"> !),.!':, .8, ""' I 4 !'::,.!':,. L::,.vf':, !':, ./':.) 6. "" . 4 !':,@!':, t::,.,t::, @L::o.e @ 6. 6,. 14
PAGE 19
Definition 2.1 Partition S into infinitely long columns. Choose g adjacent columns aud call this sub graph of S, Sg. (Figure 2. 7). g column.s .6.66 6.6.6.6 .6.6.6.6 Figure 2.7An Example of the Strip Graph Sg Definition 2.2 Partition Sg into h adjacent rows. Call this finite subgraph of Sg, Sg.h (Figure 2.8). Therefore, the subgraph Sg.h has g columns aud h rows. gcolumns 6.6.6 r hrows .6.6.6.6. j 6 Figure 2.8 An Example of Sg,h 15
PAGE 20
We are now ready to work with the new graph on the plane. In the next section, we give an iterative model which finds the independence number for different sizes of the finite subgraph Sg.h We use the independence number to find the independence ratio of the infinitely long strip Sg and find the lower bound on its fractional coloring number. We choose to work on even column length strips of Sg, since it is easier to characterize the independent set states and have a more consistant method for devising formulas. 16
PAGE 21
3 Finding the Independence Number of the UnitDistance Graph by an Iterative Algorithm We iteratively define the model we use to find the independence number for Sg,h where g is even. We define and find the independence number of S2,h, S4,h, S6.h, Ss,h, S10,h, and S12.h. We discuss the formulation of the model and introduce the Max Plus Algebra structure. 3.1 Independence Ratio Definitions Concerning the UnitDistance Graph Recall the definition i(G)=a(G)/n(G) andthetheoremx1(G)<::l/t(G). We intend to improve the unitdistance graph's fractional coloring using this bound. 1n the previous section we developed the finite subgraph, Sg.h We find the independence ratio of the finite sub graph and use limits to extend the value to the infinite strip graph, Sg. First we increase the number of rows of Sg.h and define the independence ratio for the infinite strip graph, Sg. Next, we increase the number of coluums of S, and define the independence ratio for S. Definition 3.1 Let the independence ratio of Sg be t( S g) = lim t( S g,h) h'>oo 17
PAGE 22
This makes sense since a( sg,h) is a superadditive fimction in h and i( sg,h) is bounded above by L Next, we extend the theorem about :finite graphsx f(G):?: 1/i(G) to the infinite column strip graph, Sg. Since the independence ratio is a finite value, the extension is reasonable. Theorem 3.1 For the infinite column strip graphs. with g columns, if the independence ratio of Sg is :finite, then x f { S g) 2: :( 1 ) z sg Proof The fractional coloring number of the infinite graph is at least the same as the limit of the finite subgraph From Theorem 1.2 we know the :finite graph's fractional coloring number is bounded by the reciprocal of the independence ratio. Then we know that as the row size increases, the independence ratio of the infinite Sg is the limit of the independence ratio for the finite graph Sg.h The result follows: 1 i(s8 ) D Also, we are able to make conclusions about S from our results by increasing the column widths of Sg starting with S2 S4 S6 S8 S10 and concluding with S12 With limits we establish the independence ratio for the infinite graph S. 18
PAGE 23
Definition 3.2 For the sequence of strip graphs Sg as g + oo, let the independence ratio be i(S) = lim i(Sg). g+oo Once again, since the independence ratio remains finite, we can extend the theorem X 1 ( G)2: 1/i( G) and the Theorem 3.1 to the infinite graph, S. Theorem 3.2 For the infinite graphS, if the independence ratio, i(S), is finite, then Proof: The fractional coloring number of the infinite graph Sis at least the same as the limit of the finite subgraph Sg's. From Theorem 3.1, we know that Sg's fractional coloring number is bounded by the reciprocal of the independence ratio of Sg. By definition, we know that as the column size increases, the independence ratio of the infinite Sis the limit of the independence ratio for the infinite sub graph Sg, thus finite. Then, the result follows: Xt(S) 2: lim xAsg) 2: lim{ 1 ) = lim (1) = g+oo g+ooj S g+ooi S g 19 1 i(S) D
PAGE 24
The independence ratio of Sg depends on the independence number of the finite subgraph Sg,h Therefore, we find the independence number of the finite subgraph Sg,h Since Sg,h has a gridlike structure, we can build a ( S g ,h) row by row. Once we have the independence number for the finite graph Sg.h, we quickly find the independence ratio and the fractional coloring bound for Sg by applying the previous definitions and theorems. Building a(sg,h) by rows is an iterative process. The nodes that are added to the maximum independent set depend on the placement of the nodes in the previous row and are determined by the counection rules in Table 2. L Since we are maximizing a parameter, tl:tis type of iterative modeling is categorized as dynamic programming. 3.2 Dynamic Programming and Max Plus Algebra An iterative algorithm has the form x(t+ 1) = J(x(t)) fort= O, ... n for which the initial vector x(O) is known. The function generates a set of vectors {x(I), x(2), x(3), ... x(n)}. An iteration is defined as a sequence of component updates so that each vector element is updated at least once. We use a matrix called a transfer matrix to 20
PAGE 25
generate the vectors. Therefore, Ax, = f(x(t)). Thus, we depict our canonical iterative algorithm as following dynamic program (Equation 3.1). x,+1 =Ax1 t = l, ... ,n and x0 known. (3.1) Then A is an m x m transfer matrix and x, is an m x 1 vector. Clearly, each succeeding vector depends on the preceding vector. Th.e matrix A is irreducible and pcyclic; that is, A m+r =Am for the smallest possible p. [1] One of our goals is to determine this period length, p. Since normal matrix row and column multiplication operations do not make much sense in this setting, instead we use Max Plus Algebra operations. Addition of each of the matrix's row elements to the vector's column elements replaces multiplication. Instead of adding these values, we take the maximum of these numbers to find the successive vector's elements. Hence, the normal matrix multiplication procedure is replaced by the Max Plus Algebra's binary operations: addition and maximization. Let Wmax denote the Max Plus Algebra structure; let 0 (pronounced otimes) represent addition in wmax ; and let EEl ( pronounced oplus) represent maximum in Wmax From this point forward, all algebraic operations are in this algebra. If the 21
PAGE 26
context is not clear, we use the symbols 0 and EB. The properties and definitions of 91max are discussed in the next section. Let Tg be the transfer matrix for Sg.h We reformulate Equation 3.1 into Equation 3.2. Mathematically, we transform the connection rules from Table 2.1 into Equation 3.3 to find the elements ofT g. LetT g v t = l, ... ,k0 ,k0+ p (3.2) r nodes state i adds to independent set = if 1t can extSt 1Uider state j. loo if state i cannot exist 1llldet state j. (3.3) Many of the matrix elements will be oo, so we use the properties given in the next section concerning oo to determine vector elements. Since vector elements are decided by maximization, it is rare to get oo as a vector element. We find each element of vector xt+1 with Equation 3.4. Let x,+1 =max(Tg. +x, Tg +x, ... T +x, ) t 1,1 1 1,2 2 gl,n n (3.4) 22
PAGE 27
For the kth iteration of the algorithm, the vector xk keeps track of the maximum number of vertices for all the possible ending states of the maximal independent sets. Row i of the vector indicates the stage of readiness for ending state i. Therefore, at the kth iteration, the largest number at row j in the vector xk is the maximal number of vertices possible with ending state j for the graph Sg.k This conclusion leads us to the following definition about finding the independence number of Sg,k Since we really want the indep.endence ratio of s., we divide the following result by the number of nodes in Sg,k and apply Definition 3 .1. Definition 3.3 Take the maximum element from each vector Xh to find a(sg,h}. Thus, we have a(sg,h)=yr xh where y=O. 3.3 Properties of Max Plus Algebra What properties do the binary operations 0 and EB have? First, 0 means addition, that is a 0b = a +b Second, EB means the maximum of a set of numbers, that is aEBb=max(a,b). The set of numbers for lltmax is the real number set extended by oo We frequently use oo in Max Plus models, so we must understand its behavior for EB and 0. Adding a number to oo has no effect, a 0oo 23
PAGE 28
a+oo=oo. Under maximization, oo is the identity element, a $oo = a. Adding oo to oo has no effect, that is oo 0 oo = oo and when comparing two oo sunder maximization, we obtain oo that is oo $oo = oo [1] The operation 0 is associative, commutative, has identity element 0, inverse element a, and distributes over Etl The operation Etl is associative, commutative, and has identity element oo Given a*oo then a EBb= b establishes a partial ordering on Wmax, that is if aEtlb=b then we can presume that a :5.b .[1] 3.4 Detecting Periodicity and Finding a ( S2.) We begin employing the model for S2 Call all the possible maximal independent sets of S2 states. Each state (Figure 3. 1) is assigned a number. The rows and columns ofT2 then represent each state of S2 For example, the first row ofT2 holds the elements for state 0, the first column holds the elements for state 0, the second row holds the elements for state 1, etc. 24
PAGE 29
0= D 0 1= D 0 2= L 0 3= 0 4= D 5= b 6= D. 7= Figure 3.1 Number Assignment to Maximal Independent Sets of Sz. To find the independence number for S2,h we let g = 2 in Equation 3.2. The matrix T 2 is the 8 x 8 matrix shown in Equation 3. 5. The elements of the initial vector x1 (Equation 3.6) are the sizes of the two column and one row maximal independent sets from Figure 3.1. The elements in. T2 are found by Equation 3.3. The dashes in Equation 3. 5 indicate oo and mean that the state i could not exist under or next to state}. 25
PAGE 30
states 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 1 1 1 l I 1 2 l 1 l T= 3 l l l l 1 1 (3.5) 2 4 l 1 5 2 2 6 l2 7 12 2 states 0 1 2 3 4 5 6 7 XI= (0 1 1 1 1 2 2 2f (3.6) Now we exercise the iterative model, and begin finding the vectors 2, ... ,ko+p. We need to determine when the system begins cycling, that is, find a vector that is only a constant off from a previous vector. Recall that the elements of each vector are determined by Equation 3.4. So, the vectors x2, x 3 x.., x 5 and X6 follow: T and x6 = T2x5 = [ 7 8 8 8 7 8 8 s] 26
PAGE 31
, Notice that x5 has the same pattern as the elements x, and that each element differs from the corresponding element in x2 by 4. We can say then x, = x, @4. Notice x6 has the same pattern of elements as x3 and each corresponding element in XG differs from x3 by 4. Similarly, x6 = x3 @4. At this point, we have detected the periodic behavior of our model. Each new vector's elements will be four more than the third preceding vector's corresponding elements, that is p=3. Looking at the seventh vector we see that x7 =T2x6 = T,(4 @x,) = 4 @T2x3 4 @x4 In general, for k?. 5, we can conclude that xk = 4@ x kJ By Definition 3.3 we choose the largest of all the elements in each xk, thereby obtaining a(s,J= 2, a(s,,,)= 3, a(s,J= 4, a(s2 4)= 6, a(s,,s)= 7 whichis4morethan a(S,,2), a(S,,6)= 8 which is 4 more than a(s,,J, and a(S2 7 ) 10 which is 4 more than a( S2,4) Then for k?. 5, we can see that the independence number will also cycle in periods of three, that is a(s,,k)=yT xk =yT(xk_3 04) a(S2,k_3)04. With these results, we see that the independence number goes up 4 for every 3 rows, or 4 nodes enter the maximum independent set for every 12 nodes in S2 For the number of rows ( ) a(s,k) k, k?.5, we find that i S2 k = 4k 4 Jk+O(l) 4k 27 1 ji) .. and fromDefimtwn
PAGE 32
3.1 we know i(S )= lim i(S )=.!.Then using Theorem 3.1, we determine the 2 k > 00 2,k 3 1 bound on the fractional coloring number, x ( S ) :2: :( ) = 3 f 2 l s 2 The pattern of states that give i( S2 ) is shown in Figure 3. 3. This graph of the maximum independent set clearly proves that 4/12= 1/3 is the independence ratio for Finding the pattern of states for the larger columns widths 4, 6, 8, 10, and 12 is extremely difficult due to the large number of possible states and possible combinations even when the independence number and beginning state are known. 3 o,6 2 6 0 5 .6 3 0 2 0 L, 5 Figure 3.3 The Maximum Independent Set for Sz.h 28
PAGE 33
Once we detect periodicity in our vectors, we stop the iterations. The pe.riod p is the difference between the vector numbers, and q is the difference in the maximum elements of each vector. We use these two numbers in tandem with Theorem 3.3 and Corollary 3.1 to find the independence ratio and the bound on the fractional coloring number of Sg,h Theorem 3.3 Given an initial vector x1 iteratively define x k+l = Ax k If there existsako,p,andqsuchthatx =q0x ,then xk+p=q0xkforall k?.k0 ko + P ko Further, given a vector y, let ak =yT xk Then ak =k_q:_+O(l). [2] p Proof For any k '2. k0 let k = k' + lp for integer i and k with 0 ::s; k' ::s; p where lis the largest integer such that k' '2. k. Then k' < k + p. Then a, = yr x, ( ) kk' kq ( k'q) =yr q0x,_P ==yr(lq0x,,) =lq+a,,=q+a,,=+ a,,. p p p kq Hence, for all k>O, a, has only a finite number of values, so we have the result. O p The ratio q / p is called the eigenvalue of the Equation 3.1 under Max Plus Algebra [2]. We notate the eigenvalue as ..1.( Tg) to indicate that it is associated to our 29
PAGE 34
particular transfer matrix T g We modifY the above theorem to apply to our specific parameter; that is, we want to find the maximum independent ratio for Sg. Corollary 3.1 Let g be an even column width for the strip graph Sg. Then the ( ) A(Tg) independence ratio for Sg is found by i S g 2g Proof: Since the sub graph Sg.h has a gridlike structure, every two column and one row sub graph contributes 4 total nodes to n(Sg, J. Given that g is the column width, and it is even, we know for g=2 that n(S2.J = 4, for g=4 that n(S4,J = 8, and for g = 6 that n(S6.J = 12. Therefore, by induction n(Sg.J = 2g. Since k is the number of rows in the graph Sg,k, then n(Sg,;} = 2kg. The independence ratio is defined as the ratio between the indepencence number of the finite graph and the size of the graph. kC Thus, i(sg.k)= Then by applying Definition 3.1, the result follows for i(Sg). (s ) 1 {s ) li a ( s g .k) l g = lill l g,k = ill ( ) k>oo n s g,k 30 lim "P:k>oo 2kg D
PAGE 35
We use the dynamic programming model to find the eigenvalue, qlp. Then we use the definition a k = k q / p to find our parameter a ( S 8 ,k) We place these values into Corollary 3.1 to find the independence ratio of Sg. The algorithm to find the independence ratio of Sg follows: STEP 1. Initialization. Find the matrix T8 and the initial vector x, Elements of Tz are determined by Equation 3.3. The elements ofx1 are determined by the number of nodes in each maximal independent set of S8 STEP 2. Find the Period. Apply the iterative dynamic program (Equation 3.2), p=kk0 STEP 3. Find the Eigenvalue. Determine q, the difference in the maximum elements of the beginning and ending vectors in the cycle. ThenA,(T8)=q/ p. STEP4. Find the Independence Ratio of Sg, Apply Corollary 3.1, i(S8 )= STEP 5. Find the Fractional Coloring Number's. Bound on S8 Apply Theorem 3.1, that is X A sg ):::rji(Sg). Repeat Step 0 to Step 5 until a forced pattern of independence sets appears, for g=2, 4, 6, ... ,2). 31
PAGE 36
STEP 6. Find the Fractional Coloring Number's Bound on S. Apply Theorem 3.2, x1(S)?.l/i(S). 0 We now apply this model to the remaining strip graphs of S. In the next section, we develop the solution for S4 We show th.e matrix T 4 and the first nineteen vectors generated by the dynamic program. We then find its eigenvalue, the independence ratio, and the fractional coloring number bound. As stated previously, we find the independence ratio for the even column strip graphs. Since S4 could be considered to be two strips of Sz side by side, then an S4 state number is made from two S2 state numbers, which produces a two digit octal number. For example, the octal number 17 (Figure 3.3) represents a three node maximal independent set of S4 But not all 64 states of S4 are valid. The fifteen counection rules laid out in Table 2.1 rule out some combinations. Consequently, only 39 out of the 64 possible states are valid and are supplied in Table 3.1. For example, the octal number 26 (Figure 3.4) is not a valid state because two adjacent upper 32
PAGE 37
triangle nodes are erroneously placed into an independent set. We could put these states into T 4 and fill their rows and columns with oo, or we could leave them out since it is unlikely that oo would be the maximum independent number for any iteration. Figure 3.3 State 17 Figure 3.4 State 26 We choose to work with the 39 x 39 matrix, denoted T4 and shown in Table 3.2. The elements of the initial vector x1 given in Table 3.3 are the possible contributions of the ordered two digit octal munbers of the 39 valid states to the independent set. For example, state 17 (Figure 3.3) contributes 3 nodes to the independent set, so element x1 = 3 since state 17 is in the fourteenth row. In the 14,1 matrix T4 (Table 3.2), the element T4 = 3 since row state 17 can exist under the 14,3 column state 02, and row state 17 contributes 3 nodes to an independent The 33
PAGE 38
matrix element T4 = oo since row state 27 cannot exist under column state 32. 20,24 Notice both states share the number 2. States with the same number; states with similar pattern of 1 and 5, 2 and 6, 3 and 7; and states 4 and 5, 4 and 6, and 4 and 7 cannot exist under each other nor can they exist side by side. Table 3.3 lists vectors x1 through x19 The first element of each vector has been subtracted from all the other elements in the same vector. This procedure exposes the pattern of elements in each vector. This facilitates our ability to find the cycle length between the vectors. We see that vector 13 and vector 19 have the same pattern of elements and that their maximum elements differ by 14. 34
PAGE 39
TABLE 3.1 Tiffi 39 VALID STATES FOR S4. 00 10 20 30 40 50 60 70 01 12 21 31 41 52 61 71 02 13 23 32 42 53 63 72 03 14 24 34 43 04 16 25 35 05 17 27 36 06 07 35
PAGE 40
TABLE 3.2 The Matrix T4 i 00 01 02 OJ 04 05 06 07 10 12 13 14 16 1 7 20 21 23 24 25 27 30 31 32 34 35 36 40 41 42 43 50 52 53 60 61 63 70 71 72 0010 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 I 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 02 I 03' I 04 I 05 2 2 06 2 07 2 2 10 1 1 l 1 12 2 2 2 13 2 2 2 2 2 14 2 2 16 3 17 3 3 20 1 l 1 21 2 2 2 2 2 2 2 2 23222 222 22 24 2 2 25 3 3 27 3 3 30 1 1 1 l 31 2 2 2 2 32 2 2 2 34 2 2 35 3 3 36 40 41 2 2 2 42 2 2 2 43 2 2 2 So 2 2 2 2 52 3 3 3 53 3 3 3 602222 61 3 3 3 63 3 3 70 2 2 2 2 71 3 3 3 72 3 3 3 1 2 2 2 2 2 2 2 2 3 2 2 2 3 2 2 2 2 2 2 2 1 2 2 2 2 3 1 2 2 2 2 2 2 2 2 2 2 3 3 1 2 2 2 2 2 2 2 3 2 2 3 2 1 2 2 2 1 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 2 2 2 2 2 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 2 2 2 1 2 2 2 2 2
PAGE 41
r= TABLE 3.3 THE VECTORS x, THROUGH x,o FOR S4. The first element of each vector is subtracted from all other elements in the vector. Vector 13 and vector 19 are exactly the same. 00 0 3 5 8 10 13 15 17 Subtracted elements 20 22 24 27 29 00 0 01 I 02 1 0 I I 0 I 0 1 I 0 0 0 0 0 0 0 0 1 1 I I I I 0 I I 031111111 041010100 05 2 I 2 1 2 l 1 062020201 07 2 I 2 1 2 I 1 101111 11 12 2 2 2 I 2 I 2 13 2 2 2 2 2 2 2 14 2 I 2 l 2 I 1 16 3 I 3 I 3 I 2 17 3 2 2 2 2 2 2 201110101 21 2 2 2 l l l 1 I I 0 I 0 0 2 1 1 I I 1 2 I I 1 1 1 2 l 1 2 1 2 2 1 1 2 2 2 3 1 2 1 I 0 2 l 0 I 1 1 2 2 2 1 2 2 2 3 2 I 2 0 1 0 1 0 I 0 I l I 2 I I 2 0 l 23 2 2 2 11121121 0 1 1 1 I 2 1 2 1 2 2 2 2 2 I I 1 242020101111 I 0 I 253131212222 2 I 2 27 3 1 3 1 2 I 2 2 2 2 2 l 2 30 I 1 I 1 1 I I l 1 1 I l 1 31 2 2 2 2 2 2 2 2 32 2 2 2 1 2 I 2 34 2 1 2 I 2 1 I 35 3 2 2 2 2 2 2 36 3 3 I 3 I 2 401111000 41 2 2 2 2 1 I I 42 2 I 1 1 1 0 1 43 2 2 2 2 l I I 50 2 2 2 2 I I I 52 3 2 2 2 2 1 2 53 3 2 3 2 2 2 2 602111111 61 3 2 2 2 2 2 2 63 3 2 2 2 2 2 2 70 2 2 2 2 1 I 1 71 3 2 3 2 2 2 2 72 3 2 2 2 2 I 2 2 2 3 1 2 2 I 0 2 I I 0 2 I 2 l 2 I 2 2 I 0 2 1 2 I 2 I 2 2 2 I 2 2 2 2 1 2 2 I 2 I 2 2 2 2 I 2 2 2 2 2 2 2 2 3 0 1 I 1 1 2 2 1 2 2 I 2 2 37 I I 2 I 0 I 1 1 I 2 2 I 2 2 1 2 2 2 2 2 2 0 l 1 I 2 2 I 2 2 I 2 2 31 34 36 38 41 43 0 0 0 0 0 0 I 1 l I 1 1 I 0 1 I I I 1 I 2 I 2 2 2 2 2 3 I 2 0 I I I I 2 I 2 2 I 1 I 0 I I I I 2 I 2 2 I 2 I I 2 2 2 2 2 2 3 2 2 I 0 I 0 1 I I 2 I I 2 0 I 2 I 2 2 I I 2 I 2 I 2 2 2 2 2 I 1 1 1 I 1 0 I 2 2 2 2 I 2 2 2 2 2 1 2 I l 1 I 1 I 2 2 2 2 2 2 2 2 3 2 1 2 1 2 2 2 2 2 3 3 2 2 2 I I 2 2 0 I 0 l 1 I 2 0 I I I 2 I I 1 2 2 1 2 1 2 2 2 2 1 2 2 2 2 2 2 I 2 I 2 2 3 I I 0 2 I I I 2 1 2 2 2 3 2 I 1 2 2 2 2 2 I 3' 2 2 2 2 2 2 2 0 I 1 2 2 I 2 2 I 2 2
PAGE 42
The vectors x13 and x19 are 6 iterations apart with a difference of 14 in their maximum elements. Therefore, from Theorem 3.1 and Corollary 3 .1, p = 6 and q = 14/6 14. Then i(S4)=A(T4)j2g= 2 4 =7/24, and we conclude that x 1(s4)<:24/7 = 3.4285. The states of S4.6 that result in the cyclic independent sets ru shown in Figure 3.5 61 Do0 30 6oD 0 16 L 23 Do6o 52 DoL 07 Do6 61 L 0 Figure 3.5 Periodic Independent Sets States of S4 with its Two Digit Octal State Number The next even column strip graph is S6 The number of possible combinations of states is 83 = 512. Out of the 512 combinations, only 215 states are valid. Even so, 38
PAGE 43
the matrix T 6 is too large to do by hand. We wrote a program to perform the Max Plus Algebra, to detect the periodicity, and to find the periodic pattern of the independent set states for S4 S6 S8 S10 and S12 Th.e matrix T 14 is too large and the program works too slowly for the VAX computer to be able to detect periodicity. 3.6 Results from the Program For S6 the vectors become cyclic at x28 with a period of 10. The difference in the maximum elements ofx10 and x28 is 62. Therefore, p=18 and q = 62. Now we can 62/18 compute the independence ratio for S6 i(S6)=A(T6)j2g= =31/108 and 2 conclude that X 1 (S6 ) 2:108/31=3.4838. The pattern of states for the independent set of S6 10 is shown in Figure 3.6. The number of possible states for S8 is 84 = 4096. Only 1136 states of the possible 4096 combinations are valid. The vectors begin cycling at x19 with a period of 10. The difference in the maximum element of the vectors x19 and x9 is 46. The . ( 46/10 mdependence ratio for Ss1s i(S8)= AT8)j2g= =23/80, and the fractiOnal 2 39
PAGE 44
coloring number's bound is x 1 (S8 ) :2: 80/23= 3.4782. The pattern of states for the independence ratio of S8 10 is shown in Figure 3. 7. 143 0 De 4o 232 705 123 0 Q 271 0 0 502 061 6 0 0 532 0 4 0 325 143 .6 0 4 Figure 3.6 Periodic Independent Set for S6 with its Three Digit Octal State Number. 40
PAGE 45
0170 6306 1271 2312 5235 0710 6036 1721 2132 5325 0170 ,6.o4eLo,6.o Figure 3.7Periodic lndependent Set for S8 with its Four Digit Octal State Number The number of possible states for S10 is 85 = 32768. Only 6097 states of the possible 32,768 combinations are valid. The vectors begin cycling at x31 with a period of7. The difference in the maximum elements of the vectors X31 and x24 is 40. The 41
PAGE 46
independence ratio for S10 is i{S10)=2{T10)/2g= 4017 =2/7, and the fractional 2 coloring nnmber's bom1d is x 1(s10)2:7/2=3 .. 5. The number of possible states for sl2 is 86 = 262,144. Only 32,529 states of the possible 262,144 combinations are valid. The vectors begin cycling at x21 with a period of6. The difference in the maximnm elements of the vectors x21 and X1s is 41. . ( ) ( )/ 41/6 The mdependence ratio for S121s 1 S12 =2 T12 2g= =41/144, and the 2 fractional coloring nnmber's boillld is x 1(S12) 2: 144/41= 3.5122. 42
PAGE 47
4 Finding the Independence Ratio for S Is there a forced pattern in any of the patterns of states in the independent sets of Sg,h? If we look at the states for the independent set of Ss, we find a pattern that is forced (Figure 4.1 ). This pattern is three columns wide and ten rows long and results in an independence ratio of 17/60. From Definition 3.2 which states that i(S)= lim i(Sg) and from Theorem 3.2 which states that x 1 (S)?:l/i(S), we can g>oo theorize that the fractional coloring number is at most 60/17 = 3.5294. 43
PAGE 48
0170 oQ 0 4oQ 6306 oD 0 1271 2312 op o L o 5235 0 0710 Do 4 0 6 0 6036 0 6 1721 0 0 2132 oL 0 0 5325 Leo 0170 oO 4o6 Figure 4.1 The Three Columns and Ten Rows Forced Pattern Found in the Independent Set of S,. 44
PAGE 49
5 Conclusion Although we increase the known lower bound on the fractional coloring number of the unitdistance graph, the gain is slight. It is conjectured that by using an even more complex graph like S but with two more rotated Moser spindles, the increase in the lower bound will be more substantial (Figure 5.1 and Figure 5.2). The model and algorithm to solve this would be similar to the one developed in Section 3.4. Generate states and state numbers corresponding to maximal independent sets from the smallest meaningful strip of the infinite simplified graph (Figure 5.2). The transfer matrix would be considerably larger and the program would need more time to solve the iterative system for periodicity. This modeling procedure may be generalized and adapted to find similar parameters of a graph such as the coloring number of a graph, the fractional coloring number of a graph, the domination number of a graph, the independence domination number of a graph, and the 2packing number of a graph. 45
PAGE 50
"" Figure 5.1 Placing Moser's Spindle Graph in Three Directions on the Regular Triangle Cover of the Plane Figure 5.2 The Simplified Graph with Removed Edges. 46
PAGE 51
Bibliography [l] Baccelli, Francois, Guy Cohen, Geert J. Olsder, and JeanPierre Quandrant. Synchronization and Linearity: An Algebra for Discrete Event Systems. John Wiley and Sons, Chicester, 1992. [2] Chung, Misoo. "Eigenvalues and Eigenvectors of the Max Plus Algebra." M.S. thesis, Umversity of Colorado, Denver, 1995. [3] Croft, Hallard. "Incidence Incidents." Eureka: The Archimedean 's Journal30 (1967): 2226. [4] De Brnijn, N.G. and Paul Erdos. "A Color Problem for Infinite Graphs and a Problem in the Theory ofRelations." Nederl. Akad Wetensch. Proc., Series A 54 (1951): 371373. f5l Fisher, David, Melanie Marchant, and Jennifer Ryan. "A Column Generating Afgorithm for Finding Fractional Colorings of Random Graphs." Congressus Numerantium 89 (1992): 245253. [6] Fisher, David and Daniel Ullman. "Bounds on the Fuzzy Chromatic Number of the Plane" preprint. [7] __ "The Fractional Chromatic Number of the Plane." Geombinatorics 2 (1992): 812. [8] __ "The Fuzzy Chromatic Number of the Plane" preprint. [9J Hochberg, Robert and Paul O'Donnell. "A Large Independent Set in the Unit Distance Graph." Geombinatorics 3 (1993): 8384. [10] Moser, Leo and William Moser. "Problems for Solution." Canadian Bulletin of Mathematics 4 (1961): 187189. [11] Soifer, Alexan.der. Colorado Mathematical Olympiad: the First 10 Years and Further Explorations. Center for Excellence in Mathematical Education; Colorado Springs, 1994. 47
PAGE 52
[12] __ "Chromatic Number of the Plane: A Historical Essay" Geombinatorics 1 (1991): 1315. 48
