current date April 7
On a more accessible level, the answers for the two problems
I mentioned in class are the same for the projective plane as
for the sphere since the two versions of Euler's formula are
the same except with 2 replaced by 1. In the calculaations,
you get terms involving p-2 for the planar/spherical case and
they are replaced by terms with p-1 in the projective-planar
case. Dividing by p and rounding down to the nearest integer
gives the same answers.
In addition to a question similar to the one
below, the exam may ask you some basic question
about topological spaces - I'll remind you of
the definition.
A topology tau on a non-empty set X is any
family of subsets of X such that:
(i) X and the empty set are in tau
(ii) the union of any subset of tau is in tau
(iii) the intersection of any two members of
tau is in tau
An element of tau is called an _open_ set.
Ok, here are practice problems for the midterm
next Wed. April 11 at 7pm:
0. Can property (iii) be extended to intersections
of infinite families of open sets?
If yes, give a proof. If not,
give an example of X a non-empty set, tau some
topology on X, and A_1, A_2, ..., A_n, ... a
countable sequence of open sets such that
intersection of A_n (1 <= n < oo) is not open.
Let G be a simple graph embedded in S(-1) the
surface of Euler characteristic equal to -1.
1. Find an upper bound for the minimum degree of G.
2. Repeat the exercise when G is known to have an
average of at least 7 edges in the boundary of
a face - i.e., alpha = 2q/r >= 7.
Assume for both problems that (1) G is connected,
(2) each edge lies on the boundary of exactly two
regions, (3) each region is bounded by a cycle,
(4) G is not a tree.
Let G have p vertices and q edges. If G is in
S(-1), then p - q + r = -1 is the correct form
for Euler's formula. The characteristic of S_k,
the surface with k handles is 2 - 2*k, so S(-1)
is not an orientable surface. (In fact, it is
obtained from a torus by cutting out a disk and
sewing in a Mobius band gluing it in along the
bounding circle - i.e., S(-1) is obtained by
attaching a cross-cap to the torus.)
Ok, now the exercise begins ...
... after you've tried it sufficiently, look
below for the answer ...
Answer for #0: No. Can't extend the property.
Answer for #1: delta(G) <= 6
Answer for #2: delta(G) <= 3
See below for the reasoning - after you've tried on your own.
... and here are the solutions:
0. Take X = (-oo,oo) (the real line), with the
usual topology (arbitrary unions of the usual
open intervals); let A_n = (-1/n,1/n). Then
the intersection of all the A_n is the singleton
{0} which is not open.
1 and 2.
As G is simple, 3*r <= alpha*r, where alpha is
the average number of edges in the boundary of a
region. But then 2*q = alpha * r >= 3*r, so
r <= (2/3)*q. So -1 = p - q + r <= p - (1/3)*q,
and hence q <= 3(p + 1). But if d = avg degree
of G, then d*p = 2*q <= 6(p+1), so d <= 6 + 6/p.
If p >= 7, then d < 7, so delta(G) <= 6 in this
case. Otherwise, p <= 6 so no vertex has degree
more than 5.
If alpha is at least 7, then arguing as above
(or as a corollary to the general argument I gave
once in class), q <= (7/5)(p+1). Hence,
dp = 2q <= (14/5)(p+1), so d <= (14/5) + 14/5p.
If p >=5, then d <= 14/5 + 14/25 = 84/25, so
delta(G) <= 3. Otherwise, p <= 4, so delta(G) is
at most 3 in this case also.
my index page: index page
The course will roughly parallel a paper I wrote in 1973, Recent results in topological graph theory, pp. 76--108 in Graphs and Combinatorics, R. Bari and F. Harary, Eds., Springer Lecture Notes in Mathematics, #406, Proc. of the Capital Conference on Graph Theory and Combinatorics, at the George Washington University, June 18--22, 1973, Springer-Verlag, Berlin, 1974. Students will get a copy of the original paper, supplemented by lecture notes.
There are no formal prerequisites aside from "mathematical maturity".
Here is a rough outline of what we will cover.
Enrollment will be limited and by permission only. The tutorial will carry 3 hours credit and will meet on Wed. evening from 7:00 to 8:30 pm in St. Mary's. There will also be a ``practicum'' on Sundays from 4 to 5 where students will present material. As it is on a Sunday, I will not expect everyone to attend each time but I do expect that you will attend with reasonable frequency. This way, I will be able to determine how well you are understanding the material.
Students will be expected to produce a research paper or computer program. There will be two midterm exams.
Back to the index page .