[ugrads] [Discrete-math-seminar] 2pm, Friday, 11/2

Hemanshu Kaul kaul at math.iit.edu
Fri Nov 2 00:59:35 CDT 2007

Dear Students,

We have two short talks by your fellow undergraduate students based on 
their work in REUs this summer at 2pm on Friday in the Discrete Applied 
Mathematics Seminar.

The room number is not fixed yet, but it will announced on
http://math.iit.edu/academics/sem_coll.html#RGsem .

Please try to attend the talks.

Hemanshu Kaul


Minimum Semidefinite Rank of Graphs by Jonathon Beagley
Minimum semidefinite rank (MSR) of a graph, G, is defined to be
min{rank(A), for all A in P(G)}, where P(G) is the set of PSD matrices
with corresponding graph G. New results in this topic will be described,
and a catalogue of graphs with known MSRs will be discussed. These
results, include a new proof of the vertex sum of two graphs, and a new
classification of all graphs with msr(G) =|v(G)| - 2. This last result
is done independently of Holst's classification in 2003.

Silver Cubes by Kevin Ventullo
Let I be a maximum independent set in G, the cartesian product of three
copies of the complete graph on n vertices. A silver cube is a coloring
(using 3n-2 colors) of all vertices in G such that the closed
neighborhood of every vertex in I contains every color precisely once.
The problem can be restated visually in a somewhat friendlier way,
bearing a slight resemblance to a sudoku puzzle. It is an open question
whether any silver cubes exist besides those where n =
(2^p)(3^q)(5^s)(7^t). The extension to factor 7 was discovered this past
summer using a method that will be presented in the talk.


More information about the ugrads mailing list