# Discrete Math Research Group at the University of Regina

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

 Shaun Fallat Professor Karen Meagher Assistant Professor Boting Yang Professor Ferdinand Ihringer Post Doctoral Fellow Mohammad Adm Post Doctoral Fellow Alison Purdy Post Doctoral Fellow Ryan Bergen Masters Student Adam Gore Masters Student Sam Jaques Undergraduate Student

## Past Members

 Guanglong Yu Visiting Researcher Ryan Tifenbach Post Doctoral Fellow Bahman Ahmadi Fatemeh Alinaghipour Robert Bailey Yi-Zheng Fan Chris Fisher Pavel Semukhin Michael Cavers Shahla Nasserasr

## Update on Oviods

We have submitted our paper Oviods in Generalized Quadrangles to Journal of Combinatorial Designs. The paper is available at arXiv.

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

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.

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

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

#### Minimum Semidefinite Rank of Graphs

1. van der Holst, 2003 Graphs whose positive semi-definite matrices have nullity at most two
2. Jiang, Mitchell, Narayan, 2008  matrix digraphs and minimum semidefinite rank
3. Lovasz, Saks, Schrijver, 1989 Orthogonal Representations and Connectivity of Graphs, 2000 Correction
4. 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!