April 24, 2014

Ontario Combinatorics Workshop
Friday-Saturday, May 18-19, 2012
Hosted by the Fields Institute,
at the Bahen Centre, Room 1220, University of Toronto (map)

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.