Discrete Mathematics: Math 610, Spring 2008
DeBartolo 244: MWF 10:40 - 11:30
Information on grading, tests, homework, etc. (pdf version; postscript version; dvi version)
Course Syllabus
Instructor: Andrew Sommese (Hurley 291).
Email: sommese@nd.edu
Office Hours: after
class; and 12:30-1:30 Wednesday in
my office.
Handouts
A Maple 11 worksheet on Coloring Cubes: http://www.nd.edu/~sommese/math08S610/ColorCubes.mws
A Maple 11 worksheet for counting four vertex graphs: http://www.nd.edu/~sommese/math08S610/FourVertexGraphs.mws
A Maple 11 worksheet for the Petersen graph: http://www.nd.edu/~sommese/math08S610/PetersenGraph.mws
Exam Schedule
Exam 1: Monday, February 18 (take home handed out on February 15 at the end of class).
Exam 2: Monday, April 7 (take home handed out on April 4 at the end of class).
Final: Take home that will be handed out
on last day of class and will be due by 10AM ,
Friday, May 9.
Homework
Homework 9 (due Friday, April 25):
A) Draw the trees
with Prufer encodings
1234567
1111111
222
111333
B) Do a cyclic permutation
on the vertices of the graphs you have constructed, e.g.,
for the first tree above
(on the 9 vertices 1, 2, 3, 4, 5, 6, 7, 8, 9), replace 1 by 2,
2 by 3, etc. Now compute the Prufer encodings of
these permuted graphs.
C) What are the
degrees of the 36 vertices of the graph with Prufer encoding equal to 13 ones
followed by 12 twos followed
by 6 ones followed by 3 nines.
Homework 9 (due Wednesday, April 16):
Compute the chromatic
polynomial for the graphs K_n with n from 1 to 5; and
for the graphs
K_{a,b} with 
Homework 8 (due Wednesday, April 2):
For the graphs K_n
with n from 3 to 8; for K_3 + K_5
joined at one point;
and for K_4+K_4 joined at one point,
a) write down the
adjacency matrices;
b) compute the number
of edges;
c) compute the number
of walks of length 4;
d) compute the number
of triangles;
e) compute the ranks
of the adjacency matrices;
f) compute the
eigenvalues of the matrices; and
g) compute the
diameters of the graphs.
Homework 7 (due Wednesday, March 26):
Given a poset P = (X,
R) with |X| = n > 0; we have shown there is at least one
order-preserving map
to a chain of length n. For each of
the posets P on page 188,
use the zeta
functions of their associated lattices L(P) to compute the numbers of
these order
preserving maps.
Homework 7 (due Wednesday, March 19):
Problems 1 and 8 of
12.10.
Homework 6 (due Wednesday, March 12):
Problems 8 of 7.5.
Homework 5 (due Wednesday, February 27):
Problems 1 (only for
faces and for edges), 2 of 15.8.
Homework 4 (due Wednesday, February 13):
Problems 2, 3, 6, and
7 of 13.6.
A) Write the permutation in
cycle notation. This gives a
partition of 8.
B) How many different permutations give rise to the same partition?
Homework 3 (due Friday, February 8):
Problems 15b, 16 of 4.8.
Do Problems 7 and 8 of 5.6.
Homework 2 (due Friday, February 1):
Compute S(n,k)
directly for k greater than n - 3 and also for k less than 3.
Do Problems 14, 17 of
4.8.
Homework 1 (due Friday, January 25):
Do Problems 3, 8, 10,
11 of 2.8.
Click here to go to the Department of Mathematics home page.
Click here to go to the Center for Applied
Mathematics home page.
Click here to go to the
Click here to go to the
You are visitor number
since December
18, 2007.