We are the discrete math research group in the Department of Mathematics and
Statistics at the University of
Regina. Our group meets weekly throughout the year to work on
open problems in discrete math. This is not a seminar series but
rather a working group. We are always looking for new and interesting
problems so contact us if you have a problem to suggest!

## Current Members

## Past Members

## Update on Infection in Hypergraphs

We have submitted our paper Infection in Hypergraphs to Journal of Graph Theory.
The paper is available at arXiv.
## Related Papers

Our groups has produced several papers (links are below) but there has
been recent work that continues projects started in this groups. Some
links are here; if you know of other papers that are the result of
work started in the DMRG, please let me know.
Meagher and Sciriha,
Graphs that have a weighted adjacency matrix with spectrum
$\{\lambda_i^{n-2}, \lambda_2^2\}$.

Wayne Barrett, Shaun Fallat, H.Tracy Hall, Leslie Hogben, Jephian
C.-H. Lin, Bryan L. Shader, Generalizations of the Strong
Arnold Property and the minimum number of distinct eigenvalues of a
graph

Robert F. Bailey, Andrea C. Burgess, Generalized packing designs.

## Winter 2016

This term our meeting times are Thursday 10-noon in AH 412. We are
continuing to work on "Infection in Hypergraphs". I have emailed out the working notes to everyone.
We ought to think about 2-designs and hypertrees.
## Hypergraphs

We have started a new project, generalizing zero forcing to hypergraphs. I will post notes soon.
We defined what I am called "hyperpaths" today and we are conjecturing that the infection number of a hyperpath is bounded by the zero forcing number of its host tree.
## Announcement

So it is good news or bad news?
This summer (2013) Bahman Ahmadi and Fatemeh Alinaghipour have both completed their Ph.D.s here at the Univeristy of Regina. A big congratulations to you both!
But this means they will be leaving and will be missed. Good luck and I hope that we can continue to work together!
Further, Shahla Nasserasr has moved to Fort Lauderdale where she is an assistant professor at Nove Southeastern University. I delighted for you, jealous and sad to see you go!
## Announcement

Yay! Our paper Minimum number of
distinct eigenvalues of graphs has appeared in the Electronic
Journal of Linear Algebra. We still have many open questions related
to this problem and we are hoping to return to it in January of 2014.
## New Project Update

We have made some progress on our project on covering arrays, here are
our notes . I don't think that this
project will go much further as there are currently better ways to
construct covering arrays and many of the other ideas we tested did
not work.
## New Project Jan. 2013 - Group Constructions of Covering Arrays

For the new term we are starting a new project. This project has to do
with the construction of covering arrays using groups. We are now meeting on Tuesdays from 2-4pm in ED310.
Here are the notes from Tuesday's
meeting. I also have paper that I wrote on this topic you can get it
here
and there was another paper on this topic
too.
Also we are finishing up our paper on the minimum number of distinct
eigenvalues for a graph. We will add a link here when it is done.

## Announcement

Our paper on Minimum Universal Rank has appeared! Here is the link to it:
MUR paper in LAA
## Summer 2012 Project: Minimum Number of Distinct Eigenvalues

Here are the notes from July 19.

For a graph $G$ on $n$ vertices, $S(G)$ denotes the set of all real $n \times n$
symmetric matrices with $A=[a_{ij}]$ such that $a_{ij}\neq 0$, for $i\neq j$
if and only if vertices $i$ and $j$ are connected by an edge. The minimum
number of distinct eigenvalues of $A$ when minimum is taken over all
matrices in $S(G)$ is denoted by $q(G)$. We have many questions about this
parameter $q$. For example $q(G) =1$ if and only if $G$ is the empty
graph. So for which graphs $G$ is $q(G) =2$? So far we have found far many
more than we ever expected! On the other end of the scale, $q(G)$ is
equal to the number of vertices in $G$ if and only if $G$ is a path. So
for which graphs $G$ is $q(G)$ one less than the number of vertices?

Here are notes from our meetings so far (thanks Fatemeh!).

We also have some results for cycles and complete bipartite graphs.

## New project! Fall 2011

We have selected a new project, it is the minimum number of eigenvalues for a graph.
We are ready for a new topic. Below is information on the three proposed topics, go to
topic poll
to select the topics that are intersting to you. (Vote for all if you wish, but only vote for topcis that you would be willing to work on)
### Strength-3 Sperner Set Systems

Here are my notes on strength-3 Sperner set systems , they are just my working notes so there are errors and typos!
### Minimum number of distinct eigenvalues of a graph

These are Shahla's notes on this problem .
### (3,1,1)-Generalized Packing Designs

The (first draft of) the paper on generalized packings is
here. The case of (k-2,1,1) is outlined in section 3.5;
while the case of (2,1,1) is discussed in detail in section 5.3.
Two papers on Kirkman squares are here
and here.
A paper on SOMAs is here.

## The Minimum Universal Rank of a Graph -- Summer 2011

Here is the reference for our paper:

B. Ahmadi, F. Alinaghipour, S. Fallat, Y. Fan, K. Meagher and S. Nasserasr.
__The minimum rank of universal adjacency matrices.__

Submitted to Linear Algebra and its Applications. Oct. 2011

Available at (arXiv).

### Oct 31

We are just about ready to submit our paper on the mur of graphs. The paper will be posted here
soon.
### Aug 18

Here are the notes from Aug 18 .
We have started writing up a paper on our results. Shahla is the editor on this!

### July 28

Here are the notes from July 28 .
The notes are short, (I know I was tired on Thursday!). I do now have a proof of the theorem with the condition that r is not equal to s+1. I will try to find the mur of this graph when r = s+1.

### July 7

Here are the notes from July 7 (thanks again Shahla!)
Today we were getting results like crazy - here are some highlights:

1. mur of a cycle on n vertices is n-3

2. mur of a path on n vertices is n-2. We have a proof of this but not a construction of a universal matrix that meets this bound.

3. If G has n vertices then mur(G) is no larger than n-2.

Open questions

1. What is the mur of a tree?

2. how does the mur of a graph change when an isolated vertex is added. The mur can stay the same, go up by one or two. If the graph is regular, then the mur can only go up by at most one.

3. How does adding a pendent edge to a graph change the mur?

### June 30

Here are the notes from June 30 (thanks Shahla!)
Questions of note are:

1. Is min universal rank monotone on
induced subgraphs? The answer seems to be an easy yes but Shaun
Pointed out that the degree sequences may change on an induced
graph. So this question appears to be a little tricky. It would be
interesting to find a graph that has an induced subgraph whose min
universal rank is larger than the original graph. We may need more
examples of graphs with large min universal rank before we can find
such a graph.

2. Can we find a direct proof that the only graphs with min universal
rank equal to 1 are the union of two complete graphs or the union of a
complete graph with any number of isolated vertices (or their complements)

3. Can we say anything interesting about regular graphs that have the
degree as the eigenvalue with the strictly largest multiplicity?

4. For graphs G and G can we say anything about mur (G \cup G) or (G \cup H)?

### June 23

This project is very closely related to our last project. If G is a
graph then any matrix that is a linear combination of (i) the
adjacency matrix of G, (ii) the all ones matrix (iii) the identity
matrix (iv) the diagonal matrix with the degrees of the vertices on
the diagonal is called a Universal Adjacency Matrix (UAM) of G. Our goal is
to find the minimum rank over all UAMs of G.
These matrices were defined by Willem Haemers and more information can be found in the paper
Universal Adjacency Matrices with Two Eigenvalues.

Here are the notes (thanks Shahla))
from out last meeting. Since our meeting, I have found a graph with
min universal rank equal to 1. Further, Shaun has a formula for the
minimum universal rank of a connected regular graph. Our next meeting
will focus on disconnected graphs.

## Past Project: The Minimum Rank of a Graph -- Fall 2010

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).

### A sample of applications in this area:

- - spectra of graphs and combinatorial inverse eigenvalue problems
- - singular graphs, nullity of the adjacency matrix;
- - biclique decompositions and the biclique partition number (Graham-Pollack Theorem);
- - Hermitian rank and inertia;
- - Lovasz theta function and orthonormal labellings of graphs.
- - computation complexity

### A short list of relevant references are listed below along with
linked pdf files:

#### ** Minimum Rank of Graphs **

- AIM minimum rank-special graphs work group, 2008
Zero forcing sets and the minimum rank of graphs
- Barioli and Fallat, 2004
On two conjectures regarding an inverse
eigenvalue problem for acyclic symmetric matrices
- Barioli and Fallat, 2007
On the Minimum Rank of the Join of Graphs and Decomposable Graphs
- Barioli, Fallat, and Hogben, 2004
Computation of minimal rank and path cover number for certain graphs
- Barioli, Fallat, and Hogben, 2005
On the difference between the maximum multiplicity and path cover number for tree-like graphs
- Barioli, Fallat, and Hogben, 2005
A variant on the graph parameters of Colin de
Verdiere: implications to the minimum rank of graphs
- Barrett, van der Holst, and
Loewy, 2004
Graphs whose minimal rank is two
- Berman, Friedland, Hogben, Rothblum, and Shader, 2008
An upper bound for the minimum rank of a graph
- Fallat and Hogben, 2007
The minimum rank of symmetric matrices described by a graph: a survey
- van der Holst, 2008
Three-connected graphs whose maximum corank is at most three
- van der Holst, Lovasz, and Schrijver, 1999
The Colin de Verdiere graph parameter
- Johnson and Leal Duarte, 1999
The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree

#### ** Minimum Semidefinite Rank of Graphs **

- van der Holst, 2003
Graphs whose positive semi-definite matrices have nullity at most two
- Jiang, Mitchell, Narayan, 2008
matrix digraphs and minimum semidefinite rank
- Lovasz, Saks, Schrijver, 1989
Orthogonal Representations and Connectivity of Graphs,
2000
Correction

- Narayan et al, 2008
On minimum rank of positive semi-definite matrices
with a given graph

## Past Projects

### Sample Compression

We currently studying a problem that is
motivated by a problem in theoretical computer science. The problem
has to do with sample compression and VC-Dimension. Here is an introduction to the
problem.
### Generalized Covering Designs

Here is the reference to our paper on this topic.
Generalized covering designs and clique coverings (with Andrea Burgess,
Michael Cavers and Karen Meagher),
*Journal of Combinatorial Designs* **19** (2011), 378–406; doi: 10.1002/jcd.20288 (arXiv).
### Covering Arrays

The question we asked is the following: Is it possible to get good
bounds on small covering arrays using eigenvalues of non-uniform
partition graphs?
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!

[back to home page]

Last modified: Wed Nov 11 10:55:10 EDT