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.


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 9 (due Friday, April 25):

A) Draw the trees with Prufer encodings





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 College of Science home page.

Click here to go to the University of Notre Dame home page.

You are visitor number

since December 18, 2007.