The Discrete Mathematics group is working on Hadamard diagonalizable matrices and Hadamard diagonalizable graphs this Fall 2018.
Here are the notes and the gap code from October, 10.
Both Fatemeh and Shaun have made comprehensive notes on this project from last term in case anyone needs a review! Here they are: Shaun's notes, Fatemeh's first set of notes and Fatemeh's secend set of notes
Here is an update on the Open Problems .
Here the some Open Problems that we have compiled. We will start working on the most appealing of these Friday November 19th.
During the Fall 2010 semester, Shaun Fallat will lead this group
through the topic of the minimum rank of a graph. In general
the setting is as follows:
The minimum rank problem for a simple graph is to determine
the minimum rank among, for example, all real symmetric matrices whose
zero-nonzero pattern of off-diagonal entries is described by a given
simple graph G.
We note that the maximum rank is always the order of
G, and it is straightforward that any rank between the minimum and
full rank may be achieved.
It turns out, that the zero-nonzero pattern described by a graph has
significant influence on the minimum rank.
Example: A matrix associated with a path on n vertices is a symmetric
tridiagonal matrix (up to labeling) with nonzero sub- and
super-diagonal and thus has minimum rank n-1, whereas the complete
graph on n vertices has minimum rank 1.
The plan is to provide an introduction to this topic, including an
overview of the notation and a survey of a number of important
related results.
The goal after a few introductory lectures would be for the group
to work on some relevant open problems that are of current interest (these
will be discussed within the group).
We were able to find several eigenvalues for these graph and using these se were able to find some bounds on the sizes of small covering array. Unfortunately, the bounds we found are not the best known bounds. A summary of this work is available here. This project will likely be continued at some point. One approach would be to develop a better method to find eigenvalues with the goal of finding smaller eigenvalues that will give better bounds. We did return to the study of covering arrays. Our goal was to prove that for small covering arrays (specifically, arrays with alphabet size k and between k^2 and k^2+k columns) that the optimal arrays can be achieved using balanced covering arrays. We have an approach which involves finding a clique partition for a certain multipartite graph, namely the graph K_{k,2,2,...,2}. Unfortunately we were unable to find appropriate bounds on the size of a clique partition for this graph. If you have an ideas let use know!