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