Jonathon Beagley & Kevin Ventullo
Applied Mathematics
Illinois Institute of Technology

Two Brief Talks: Minimum Semidefinite Rank of Graphs & Silver Cubes

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.

Friday, November 2, E1 103, 2:00 pm

Last updated by jmillham_AT_math_dot_iit_DOT_edu on 10/9/07