Andrea Burgess (Ryerson University)
Near-factorizations of the complete graph
A $w$-near $k$-factor of a graph $G$ on $n$ vertices is a spanning
subgraph of $G$ with $w$ vertices of degree 0 and $n-w$ vertices
of degree $k$. In this talk, we introduce the concept of a $w$-near
$k$-factorization of a graph $G$, which is a decomposition of
$G$ into $w$-near $k$-factors. Thus, for example, a $k$-factorization
is equivalent to a 0-near $k$-factorization, and a near 1-factorization
is equivalent to a 1-near 1-factorization. We focus on $w$-near
2-factorizations of $K_n$ and $K_n-I$; in the case that the partial
2-factors are required to be pairwise isomorphic, this may be
viewed as a generalization of the Oberwolfach problem. We discuss
some constructions of $w$-near 2-factorizations in which all cycles
in the near-factors have the same length. This is joint work with
Peter Danziger.
Xiaoxia (Fiona) Fan, University of Waterloo
Quantum State Transfer on Double Star Graphs
Given a graph X with adjacency matrix A, we define the transition
matrix U(t) =exp(iAt). This function determines what is called
a continuous quantum walk.
We say there is perfect state transfer if the uv-entry of U(t)
has norm 1.
Similarly, we say there is pretty good state transfer if the uv-entry
gets arbitrarly close to 1.
In this talk, we characterize pretty good state transfer and strong
copectral vertices. In particular, we show that perfect state
transfer does not occur on double star graphs.
Finally, we give a sufficient condition for pretty good state
transfer on double star graphs.
This is joint work with Chris Godsil.
Jan Foniok (Queen's University and
Swiss National Science Foundation Research Fellow)
Homomorphism Dualities
I will talk about homomorphisms of digraphs, or more generally,
relational structures. They have very natural uses in category
theory, order theory, constraint satisfaction (artificial intelligence),
etc. A homomorphism duality is a situation where the nonexistence
of a homomorphism from some F is equivalent to the existence of
a homomorphism to some D (vaguely said; I'll make it precise in
the talk). I will show how (surprisingly) they correspond (1)
to finite maximal antichains in some partial order, (2) to first-order
definable constraint satisfaction problems. If time permits, I
will also show an application of adjoint functors.
Nevena Francetic, University of
Toronto
Covering Arrays with Row Limit: bounds and constructions
Covering arrays with row limit, $CARL$s for short, are a natural
generalization of covering arrays which have a new parameter row
limit, $w$, representing the number of non-empty cells in a row.
When $w$ equals the number of columns $k$, then a $CARL$ is a
covering array. We present some upper and lower bounds on the
size of $CARL$s which have the
row limit $w(k)$ as a function of $k$. We show that the nature
of the problem splits into at least two subcases: $w(k)={\rm o}(k)$
and $w(k)={\rm \Theta}(k)$, for which
the asymptotic growth of $CARL$s differs. We also discuss two
construction methods of
$CARL$s which we apply to obtain a number of families of objects
for which the size is
within the bounds.
Zoltán Füredi (University
of Illinois at Urbana-Champaign)
Huge Superimposed codes (.pdf
of abstract)
There are many instances in Coding Theory when codewords must
be restored from partial information, like defected data (error
correcting codes), or some superposition of the strings. These
lead to superimposed codes, a close relative of group testing
problems. There are lots of versions and related problems, like
Sidon sets, sum-free sets, union-free families, locally thin families,
cover-free codes and families, etc. We discuss two cases cancellative
and union-free codes.
A family of sets $\mathcal F$ (and the corresponding code of 0-1
vectors) is called {\bf union-free} if $A\cup B\neq C\cup D$ and
$A,B,C,D\in \mathcal F$ imply $\{ A,B\}=\{ C, D \}$.$\mathcal
F$ is called $t$-{\bf cancellative} if for all distict $t+2$ members
$A_1, \dots, A_t$ and $B,C\in \mathcal F$$$A_1\cup\dots \cup A_t\cup
B \neq A_1\cup \dots A_t \cup C.$$Let $c_t(n)$ be the size of
the largest $t$-cancellative code on $n$ elements. We significantly
improve the previous upper bounds of K\"orner and Sinaimeri,
e.g., we show $c_2(n)\leq 2^{0.322n}$ (for $n> n_0$).
Majid Karimi, Brock University
Graph Powers and Graph Roots
Graph $G$ is the square ($k^{\mbox{th}}$ power) of graph $H$,
if two vertices $x, y$ have an edge in $G$ if and only if $x,
y$ are of distance at most two ($k$) in $H$. Given $H$ it is easy
to compute its square $H^2$ . Determining if a given graph $G$
is the square of some graph is NP-complete in general.
{\em Root} and {\em root finding} are concepts familiar to most
branches of mathematics. Graph power is a basic operation with
a number of results about its properties in the literature.
The main motivation for studying the complexity of checking
if a given graph is a certain power (square specifically) of another
graph comes from distributed computing. The $r^{\mbox{th}}$ power
of graph $H$ represents the possible flow of information in $r$
round of communication in a distributed network of processors
organized according to $G$.
We are interested in the characterization and recognition problems
of square root graphs. This recognition problem has an almost
complete di- chotomy theorem in terms of the girth of square root
graph. Indeed when girth of graph is at most 4 the recognition
problem is NP-Complete and when girth is at least 6 there are
algorithms to find the unique (up to iso-
morphism) square root. However this problem is still open in square
root of graphs with girth five.
We present partial structures that by excluding them, the recognition
prob- lem has a polynomial-time answer. We also present graphs
with exponential number of non-isomorphic square roots.
Avery Miller (University of Toronto)
Thick Cover-Free Families with Applications to Wireless Radio
Networks
An r-cover-free family is a family of sets such that no set in
the family is contained in the union of at most r other sets in
the family. We introduce a new generalization of such families
that takes into account how many times a set is covered. Namely,
an r-cover-free family of thickness b is a family of sets such
that no set in the family is contained b times in the multiset
union of at most r other sets in the family. Extending a result
by Füredi (1996), we are able to prove an upper bound on
the size of these families. Finally, we show how this upper bound
leads to new lower bounds for neighbourhood discovery algorithms
in wireless radio networks.
Natalie Mullin, University of Waterloo
Uniform Mixing and Association Schemes
Continuous-time quantum walks on graphs are quantum analogues
of classical random walks on graphs. In recent years quantum walks
have been studied for their potential applications in quantum
algorithms. We say that a graph admits uniform mixing if the probability
distribution visited by the continuous-time quantum walk is uniform
at a particular time. In this talk we use the framework of association
schemes to determine whether certain graphs admit uniform mixing
David Roberson, University of Waterloo
Cores of Vertex Transitive Graphs
A graph homomorphism is an adjacency preserving map between
the vertex sets of two graphs. An endomorphism is a homomorphism
from a graph to itself. The core of a graph is its smallest
endomorphic image. If $Y$ is the core of a vertex transitive
graph $X$, then any homomorphism from $X$ to $Y$ maps the same
number of vertices to every vertex of $Y$ and therefore $|V(Y)|$
divides $V(X)$. Using this result we will describe the structure
of vertex transitive graphs which have cores of half their size.
We will see that this description does not generalize to vertex
transitive graphs with cores of less than half their size, but
that it can be partially extended to Normal Cayley graphs
Mateja Sajna (University of Ottawa)
Cycle Systems: A Neverending Fascination
This talk begins with an account of the fascinating history
of combinatorial designs and cycle systems. We then introduce
some of the basic problems involving cycle systems: cycle decomposition
of complete (and nearly complete) graphs, and the Oberwolfach
problem, both in its directed and undirected variant. We briefly
sketch some of the proofs of the solved problems, and give an
update on the status of the open ones. Finally, we discuss the
author’s progress (joint work with Andrea Burgess and Patrick
Niesink) on the directed Oberwolfach problem with constant cycle
lengths.
Yoshio Sano (National Institute of Informatics,
Japan) (abstract.pdf)
Fat Hoffman graphs with smallest eigenvalue at least $-1-\tau$
In the field of Spectral Graph Theory, one of the important
research problem is to characterize graphs with bounded smallest
eigenvalue. P. J. Cameron, J. M. Goethals, J. J. Seidel, and
E. E. Shult (1976) characterized graphs whose adjacency matrices
have smallest eigenvalue at least $-2$ by using root systems.
Their results revealed that graphs with smallest eigenvalue
at least $-2$ are generalized line graphs, except a finite number
of graphs represented by the root system $E_8$. A. J. Hoffman
(1977) studied graphs whose adjacency matrices have smallest
eigenvalue at least $-1-\sqrt{2}$ by using a technique of adding
cliques to graphs. R. Woo and A. Neumaier (1995) formulated
Hoffman's idea
by introducing the notion of Hoffman graphs and generalizations
of line graphs.
In this talk, we show that all fat Hoffman graphs with smallest
eigenvalue at least $-1-\tau$, where $\tau$ is the golden ratio,
can be described by a finite set of fat $(-1-\tau)$-irreducible
Hoffman graphs. In the terminology of Woo and Neumaier, we mean
that every fat Hoffman graph with smallest eigenvalue at least
$-1-\tau$ is an $\mathcal{H}$-line graph, where $\mathcal{H}$
is the set of isomorphism classes of maximal fat $(-1-\tau)$-irreducible
Hoffman graphs. It turns out that there are $37$ fat $(-1-\tau)$-irreducible
Hoffman graphs, up to isomorphism.
(This is joint work with Akihiro Munemasa and Tetsuji Taniguchi.)
Jihyeon Jessie Yang (University of Toronto)
Parameter space of curves constructed from a polygon
Given a lattice polygon, we construct a parameter space of algebraic
curves. Some attributes of this parameter space are purely combinatorial,
such as dimension and degree. This idea can be generalized to
many directions. For example, we can consider a subdivision
of the polygon into subpolygons which appear naturally in tropical
geometry and is related to a very classical object in algebraic
geometry called Severi variety.
Also, instead of a polygon we can consider higher dimensional
polytope and construct a parameter space of hypersurfaces. I
will present the combinatorial aspect of this idea.
Top
