 |
|
||||
Org: Peter Danziger (Ryerson), Lucia Moura (Ottawa) and Brett Stevens (Carleton)
[PDF]
- ROBERT BAILEY, University of Regina
Covering arrays and VC-dimension [PDF]
-
{\em Vapnik--Chervonenkis dimension} is a combinatorial parameter which originates in computational learning theory. Its definition is very similar to that of the strength of a binary covering array. This talk will contain some simple observations about the relationship between the two parameters, and report progress on an ongoing investigation into them.
No background in learning theory is required.
This is joint work with Karen Meagher, Pavel Semukhin and Sandra Zilles.
- ANDREA BURGESS, Ryerson University
Near factorizations of complete graphs [PDF]
-
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$; when the near 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.
Joint work with Peter Danziger.
- CHARLIE COLBOURN, Arizona State University
Strengthening Hash Families [PDF]
-
Consider an $N \times k$ array $A$ with every cell containing a symbol from an alphabet of size $v$.
When $C$ is a subset of $t$ or fewer columns, and $(C_1,\dots,C_\ell)$ is a partition of $C$, the array $A$ {\em separates} $(C_1,\dots,C_\ell)$ if there is at least one row in which two columns from $C$ contain the same entry only if the columns belong to the same class of $(C_1,\dots,C_\ell)$.
Different specifications of partitions of columns to be separated lead to well-known definitions of perfect, separating, and distributing {\em hash families}.
One motivation for studying such hash families arises from their use in `column replacement' techniques, which have been examined for the construction of covering arrays, and measurement matrices for compressive sensing.
In these applications, however, known variants of hash families construct large matrices having the same strength (value of $t$) as the smaller ingredient matrices.
This limits their applicability dramatically.
In this talk, we describe how to equip hash families with a {\em strengthening} property, which underlies column replacement techniques that increase strength.
We describe one application of these hash families, and outline methods for their construction.
This is joint work with Daniel Horsley (Monash University) and Violet Syrotiuk (Arizona State).
- PETER DANZIGER, Ryerson University
On the Oberwolfach and Hamilton-Waterloo Problem for Bipartite 2-factors [PDF]
-
The Oberwolfach problem was first introduced by Ringel in the 1960's, the problem requires one to find a factorization of $K_n$ ($K_n$ minus a $1-$factor if $n$ is even) into a specified $2-$factor $F$. An obvious generalization requires the factorization into $t$ specified $2-$factors $F_1, \ldots, F_t$. When $t=2$, this is known as the Hamilton-Waterloo problem. Both of these problems have received some attention of late.
I will present a Theorem that solves a large number of cases when $n$ is even and the $2-$factors $F_i$ are bipartite. This result completes the solution of the Oberwolfach problem for any collection of even sized cycles and in addition it settles the Hamilton-Waterloo problem for bipartite $2$-factors. This is joint work with Darryn Bryant.
- NEVENA FRANCETIC, University of Toronto
Bounds on the size of a covering array with row limit [PDF]
-
Covering arrays with row limit, $CARL$s for short, are a generalization of covering arrays which have a new parameter weight $w$ representing the number of components tested at the same time. When this parameter is fixed and we cover pairwise interactions, $CARL$s are equivalent to the group divisible covering designs and a special case of the graph covering problem. When $w$ equals the number of components $k$, then the $CARL$ is a covering array.
Here we will study some upper and lower bounds on the size of $CARL$s which have the row weight $w$ as a function of $k$. We will show that the nature of the problem splits into at least two subcases: $w=o(k)$ and $w=O(k)$, for which we present different bounds.
- RICHARD HOSHINO, National Institute of Informatics, Tokyo
Hypergraph Edge Numbering and its Application to Game Show Scheduling [PDF]
-
A year ago, I was contacted by the Executive Producer of {\it Splatalot!}, a medieval-themed TV game show for kids modeled after the hit American series {\it Wipeout}. The show featured nine ``defenders'' to ``protect the castle'', consisting of three teenagers from each of Canada, Australia, and Britain. In scheduling the $27$ episodes, two of the three defenders had to be chosen from each country to produce a six-person lineup, with the caveats that no six-person lineup could be chosen twice, and that each defender's appearances were appropriately spaced to prevent fatigue and burnout. Specifically, the producers of {\it Splatalot!} had hoped to schedule the $27$ episodes so that each defender would shoot $3$ or $4$ consecutive shows and then have a day off, but were unable to find a feasible arrangement. \
In this talk, I will explain how this scheduling optimization problem was solved by re-converting it to an equivalent problem of numbering the edges of a hypergraph so that the numbers on the edges incident to each vertex were spread out as evenly as possible. We will present the optimal schedule given to the show's Executive Producer, having the property that no defender would play four consecutive shows or sit out two consecutive shows. We conclude the talk by motivating a Ramsey-type problem for the general scenario of $m$ out of $n$ defenders chosen from each of $k$ countries, and present various combinatorial techniques to determine an optimal episode arrangement schedule for any triplet $(m, n, k)$.
- HEATHER JORDON, Illinois State University
Alspach's Problem: The Case of Hamilton Cycles and 5-Cycles [PDF]
-
In 1981, Alspach posed the following problem: Prove there exists a decomposition of $K_n$ ($n$ odd) or $K_n - I$ ($n$ even) into cycles of lengths $m_1, m_2, \ldots, m_t$ whenever $3 \le m_i \le n$
for $1 \le i \le t$ and $m_1+ m_2 + \cdots + m_t = n(n-1)/2$ (number of edges in $K_n$) or $m_1+ m_2 + \cdots + m_t = n(n-2)/2$ (the number of edges in $K_n - I$). In this talk, we settle Alspach's problem in the case of Hamilton cycles and 5-cycles. We show that for all odd integers $n\ge 5$ and all nonnegative integers $h$ and $t$ with $hn + 5t = n(n-1)/2$, the complete graph $K_n$ decomposes into $h$ Hamilton cycles and $t$ 5-cycles, and for all even integers $n \ge 6$ and all nonnegative integers $h$ and $t$ with $hn + 5t = n(n-2)/2$, the complete graph $K_n$ decomposes into $h$ Hamilton cycles, $t$ 5-cycles, and a $1$-factor.
- DAVID PIKE, Memorial University of Newfoundland
Cycle Extensions in BIBD Block-Intersection Graphs [PDF]
-
A cycle $C$ in a graph $G$ is said to be extendible if there exists a cycle $C'$ such that $V(C) \subseteq V(C')$ and $|V(C')| = |V(C)|+1$.
A graph $G$ is said to be cycle extendible if every non-Hamiltonian cycle of $G$ is cycle extendible.
A balanced incomplete block design BIBD$(v,k,\lambda)$ consists of a set of blocks, each of which is a $k$-subset of a point set $V$ of cardinality $v$, such that each pair of points occurs in precisely $\lambda$ of the blocks of the design.
The block-intersection graph of a design $D$ is the graph having the block set of $D$ as its vertex set, and in which two vertices are adjacent if and only if their corresponding blocks have non-empty intersection.
We show that the block-intersection graph of a BIBD$(v,k,1)$ is cycle-extendable.
This is joint work with Atif Abueida.
- ALEX ROSA, McMaster University
Triple metamorphosis of twofold triple systems [PDF]
-
The concept of a metamorphosis of block designs, due to Lindner, has been dealt with in many papers. Typically, for a subgraph $G'$ of $G$, each block of a $G$-design of order $n$ and index $\lambda$ is modified by deleting the edges of $G \setminus G'$, and then reassembling the totality of deleted edges into $G'$-blocks, so as to form, together with the modified blocks of the original $G$-design, a new $G'$-design of order $n$ and index $\lambda'$. One such instance is the metamorphosis of a simple twofold triple system of order $n$, TS($n,2$), into a twofold 4-cycle system of order $n$, 4C($n,2$). The spectrum for TS($n,2$) having a metamorphosis into 4C($n,2$) has previously been shown to be the set $n \equiv 0,1,4,9\ (mod\ 12)$, $n \geq 9$. Here we extend the concept of metamorphosis to that of a triple metamorphosis of a TS($n,2$) into a 4C($n,2$). We show that the necessary conditions for the existence of a triple metamorphosis of a TS($n,2$) into a 4C($n,2$) are also sufficient, with one exception ($n=9$) and one possible exception ($n=12$).
(This is joint work with Curt Lindner and Mariusz Meszka.)
- MATEJA SAJNA, University of Ottawa
On the directed Oberwolfach Problem with equal cycle length [PDF]
-
In this talk we present recent progress towards the determination of the necessary and sufficient conditions (on $m$ and $n$) for a complete symmetric digraph with $n$ vertices to admit a resolvable decomposition into directed cycles of length $m$. In the literature, these decompositions are also called {\em directed cycle systems} (with constant cycle length) and {\em Medelsohn designs} (with $\lambda=1$).
This is joint work with Andrea Burgess and Patrick Niesink.
- BRETT STEVENS, Carleton University
Asymptotic Constructibility of Covering Arrays [PDF]
-
It has long been known that the optimal asymptotic size of a strength 2 covering array, CA$(2,k,v)$ is
\[
\frac{v \log_2 k}{2} (1 + o(1))
\]
but this result is non-constructive. We present the current best asymptotic constructibility of strength 2 covering arrays. This requires a brief survey of general purpose constructions, their compatibility and one result on the distribution of primes.
