Ontario Combinatorics Workshop
Friday-Saturday May 23-24, 2008
University of Waterloo, Ontario, Canada
Speaker Abstracts
Hamiltonian decompositions of complete $k$-uniform
hypergraphs
Robert Bailey, Carleton University
I'll define define the notion of a Hamiltonian decomposition
for a complete $k$-uniform hypergraph, which is a natural generalisation
of an object that has been known to exist since the 1890s. I will
then describe the considerable lack of progress that we have made
since working on this problem, and why various approaches we've
tried either haven't worked, or are not powerful enough beyond some
small cases.
(This is joint work with Brett Stevens.)
-----------------------------------------------------------------------------------------------
An overview of geometric
spanners
Prosenjit Bose, Carleton University
A geometric graph is a graph whose vertex set is a
set $P$ of points in the plane and whose edge set is a set of segments
joining pairs of vertices with each edge weighted by the length
of the segment. A $t$-spanner of a geometric graph $G$ for constant
$t>1$, is a spanning subgraph $G'$ of $G$ with the additional
property that for every pair of vertices $x,y \in P$, the length
of the shortest path from $x$ to $y$ in $G'$ is no more than $t$
times the length of the shortest path from $x$ to $y$ in $G$. In
this talk, we will review some of the main results/techniques in
this area as well as review some of our recent results.
-----------------------------------------------------------------------------------------------
Towards identifying when
a consensus exists: a study of probabistic algorithms for {\sc Consensus
Sequence}
Christina Boucher, University of Waterloo
Given a set of sequences $S$ and degeneracy parameter
$d$, the {\sc Consensus Sequence} problem asks whether there exists
a sequence that has Hamming distance at most $d$ from each sequence
in $S$. We present two probabilistic algorithms for solving {\sc
Consensus Sequence} both of which a simple local-search paradigm;
start with a given sequence $s^*$ and incrementally augment it so
that at least one sequence in $S$ has smaller Hamming distance to
$s^*$. In one algorithm, we continue this process for $O(n)$ steps;
after this time, if no consensus is found then the algorithm is
repeated. We demonstrate that for a set of sequences $S$ from alphabet
$\Gamma$ this process is repeated $\rho$ times, where $\rho$ is
a polynomal factor of $|\Gamma|^n(1 - 1/l)^n$. Secondly, we investigate
the algorithm that begins with the sequence that is the majority
vote at each position, and iteratively updates this sequence a bounded
number of times. We consider this algorithm from a probabilistic
view and demonstrate the sequences for which the algorithm performs
badly are rare.
Joint work with Dan Brown
-----------------------------------------------------------------------------------------------
Closed trail decompositions
of complete equipartite graphs
Andrea Burgess, University of Ottawa
The complete equipartite graph $K_m * \overline{K_n}$ has $mn$ vertices
partitioned into $m$ parts of size $n$, such that two vertices are
adjacent if and only if they are in different parts. In this talk,
we consider a relaxation of the problem of cycle decomposition of
$K_m * \overline{K_n}$, namely decomposition into closed trails.
We focus our attention on the case that all trails in the decomposition
have the same length and, in particular, give necessary and sufficient
conditions for the existence of a decomposition of $K_m * \overline{K_n}$
into closed trails of length $k$. This is joint work with Mateja
\v{S}ajna.
-----------------------------------------------------------------------------------------------
A Simpler 3/2-Approximation Algorithm
for the Multi-two-edge Connected Subgraph Problem
Amy Cameron, University of Ottawa
The minimum cost two-edge connected subgraph problem is an important
problem in network design, and has many practical, cost-saving applications.
In order to build a reliable network at lower cost, it is sometimes
useful to allow more than one link to be built between a pair of
centres. We call this the multi-two-edge connected subgraph problem.
This problem is known to be NP-complete. A 3/2-approximation algorithm
can be obtained by using a combination of techniques from Frederickson
and Ja’Ja’ (1982) and Goemans and Bertsimas (1993). We
present a direct approach, with a new, simpler proof using polyhedral
combinatorics.
-----------------------------------------------------------------------------------------------
Separating Number-On-Forehead Communication
Complexity Classes RP and NP
Matei David, University of Toronto
In the "number-on-forehead" communication model, k players
are presented with k n-bit inputs x_1,..,x_k to a function f, in
such a way that player i sees all the inputs except for x_i. The
goal of the players is to compute f(x_1,..,x_k) with as little communication
as possible. Separating the powers of randomized and nondeterministic
efficient communication protocols has been a long standing open
problem.
Recently, Lee and Shraibman (CCC 2008), and, independently, Chattopadhyay
and Ada (arXiv 2008), provide such a separation when the number
of players is k<loglogn. We extend this separation up to k<delta*logn
players, for any delta<1.
-----------------------------------------------------------------------------------------------
Self-complementary uniform
hypergraphs
Shonda Gosselin, University of Ottawa
For a positive integer $k\geq 2$, a {\em $k$-uniform
hypergraph}, is a pair $(V,E)$ in which $V$ is a finite set of {\em
vertices} and $E$ is a set of $k$-subsets of $V$ called {\em edges}
(a 2-hypergraph is a graph). The {\em complement} of a $k$-hypergraph
$X=(V,E)$ is the $k$-hypergraph with vertex set $V$ whose edge set
consists of the $k$-subsets of $V$ which are not in $E$, and $X$
is called {\em self-complementary} if it is isomorphic to its complement.
We discuss a method for generating self-complementary $k$-uniform
hypergraphs, and prove that the known necessary conditions on the
order of these structures are also sufficient for certain values
of $k$. In addition, for these values of $k$ we characterize the
structure of vertex-transitive self-complementary $k$-uniform hypergraphs
of prime order.
-----------------------------------------------------------------------------------------------
Independent transversals
Penny Haxell, University of Waterloo
Let $G$ be graph whose vertex set is partitioned into classes.
When does there exist a set $S$ of vertices, consisting of one vertex
from each class, such that no two vertices of $S$ are joined by
an edge of $G$? Such a set is called an {\it independent transversal}
of $G$ with respect to the given vertex partition. It turns out
that many mathematical questions can be formulated by asking whether
an independent transversal exists in a particular graph with a particular
vertex partition.
We describe a number of different conditions that guarantee the
existence of an independent transversal in a given vertex-partitioned
graph. We also outline some applications of these results in various
different contexts.
-----------------------------------------------------------------------------------------------
Fast Mixing for 3-Colourings on Bounded-Degree
Trees
Brendan Lucier, University of Toronto
In this talk I will discuss the mixing rate of the Glauber Dynamics,
a single-site update markov chain, for colourings on trees. I will
show that this chain mixes in polynomial time for 3-colourings on
a tree with maximum degree Delta. This resolves a recent open question
by Hayes, Vera, and Vigoda. Our proof eschews the now-standard coupling
approach,
and instead makes use of a decomposition technique from spectral
analysis
-----------------------------------------------------------------------------------------------
The story of $(T,M,S)$-nets
Bill Martin, Worcester Polytechnic Institute
Extending earlier ideas of Sobol' (1967), Niederreiter
(1987) introduced the following definition. A $(T,M,S)$-{\em net
in base $b$} is a subset ${\cal N}$ of the Euclidean unit cube $[0,1)^S$
of size $b^M$ enjoying the property that each {\em elementary interval}
in base $b$ $$ E = \prod_{i=1}^S \left[ \frac{a_i}{b^{d_i}} , \frac{a_i+1}{b^{d_i}}
\right), \qquad 0 \le a_i < b^{d_i}$$ of volume $b^{T-M}$ contains
exactly $b^T$ points of the net ${\cal N}$. (Note that $Vol(E) =
b^{-\sum d_i}$.)
These deterministic low-discrepancy point point sets serve as deterministic
surrogates for Monte Carlo methods in numerical integration, simulation,
and global optimization.Yet the construction is entirely combinatorial:
a fundamental theorem of Lawrence, Mullen and Schmid (1995-6) shows
that a $(T,M,S)$-net is equivalent to an {\em ordered orthogonal
array}, this being a natural extension of the orthogonal array familiar
to statisticians and combinatorial design theorists. This observation
is the launch point for a whole host of new results and for discoveries
of connections to other areas of mathematics.
Recent work in this area has used tools from coding theory, including
algebro-geometric codes, tools from the theory of association schemes
such as Delsarte's linear programming bound, and tools from finite
geometry. Connections will be mentioned, including those to quantum
codes, multivariate orthogonal polynomials, enumerative combinatorics,
partially ordered sets, and Lie algebras.
Parts of this talk area based on joint work with Doug Stinson,
Terry Visentin and Paul Terwilliger.
-----------------------------------------------------------------------------------------------
Achieving maximum chromatic index in multigraphs
Jessica McDonald, University of Waterloo
The chromatic index of a multigraph G, denoted by
$\chi'(G)$, is the minimum number of colours needed to colour the
edges of G such that such that adjacent edges receive different
colours. Shannon (1949), Vizing (1964) and Goldberg (1984) have
all established well-known upper bounds for the chromatic index
of G. In this talk we ask: when is $\chi'(G)$ maximum? That is,
when does $\chi'(G)$ achieve a particular upper bound?
Our main result in this talk is to characterize those multigraphs
which achieve Goldberg's upper bound, generalizing a 1968 result
of Vizing which characterizes those muligraphs which achieve Shannon's
upper bound. There is no known characterization for those multigraphs
which achieve Vizing's upper bound, however we will discuss some
partial results towards this, and address the issue of the complexity
of this problem.
-----------------------------------------------------------------------------------------------
Constructing Strongly Regular Graphs
Natalie Mullin, University of Waterloo
Strongly regular graphs arise in a variety of contexts including
coding theory and design theory. I will explain the basic properties
of strongly regular graphs, and then describe constructions of interesting
strongly regular graphs using both algebraic and geometric methods.
-----------------------------------------------------------------------------------------------
Some combinatorial properties
of truncated random unitary matrices
Jonathan Novak, Queens University
We consider some combinatorial properties of submatrices
of random unitary matrices. The moments of the trace of such a matrix
can may be shown to represent the solution to a generalized ballot
problem. In particular, these considerations lead to a generalization
of well known results of Rains and Gessel which relate random matrices,
lattice walks in a Weyl chamber, and determinants of Bessel functions.
-----------------------------------------------------------------------------------------------
List colouring Steiner triple
systems
Martin Pei, University of Waterloo
We discuss the problem of list-colouring Steiner Triple Systems
(STS), in relation to the (ordinary) colouring problem. The list
chromatic spectrum of some admissible order is the set of all possible
list-chromatic numbers for STS of this order. We prove that the
lower bound on the list chromatic spectrum grows with the size of
the STS. This is not true for the chromatic number as there exist
3-chromatic STS for all admissible orders. We also show that the
list-chromatic number of an STS can be no more than a log factor
times its chromatic number. Combining the two results give interesting
bounds on the list chromatic spectrum, in particular we find a tight
asymptotic range for the lower bound of the spectrum for large STS.
This is joint work with Penny Haxell.
------------------------------------------------------------------------------------------------------------------
The intersection spectrum
of Skolem sequences
Daniela Silvesan, Memorial University of Newfoundland
A Skolem sequence of order n is a sequence Sn = (s1 , s2 , .
. . , s2n ) of 2n integers containing each of the symbols 1, 2,
. . . , n exactly twice, and such that two occurrences of the integer
j {1, 2, . . . , n} are separated by exactly j - 1 symbols. We prove,
with few possible exceptions that there exists two Skolem sequences
of order n which have 0, 1, 2, . . . , n - 3, n pairs in common.
We also determine the possible number of repeated base blocks in
a cyclic twofold triple system, cyclic twofold directed triple system
and cyclic twofold Mendelsohn triple system of order v for v 1,
3(mod 6), v = 9 and the fine structure of a cyclic threefold triple
system, cyclic threefold directed triple system and cyclic threefold
Mendelsohn triple system of order v for v 1, 7(mod 24).
-----------------------------------------------------------------------------------------------
Hyperplane Arrangements with
Large Average Diameter
Feng Xie, McMaster University
The largest possible average diameter of a bounded cell of a simple
hyperplane arrangement is conjectured to be not greater than the
dimension. We prove that this conjecture holds in dimension 2, and
is asymptotically tight in fixed dimension. We give the exact value
of the largest possible average diameter for all simple arrangements
in dimension 2, for arrangements having at most the dimension plus
2 hyperplanes, and for arrangements having 6 hyperplanes in dimension
3. In dimension 3, we give lower and upper bounds
which are both asymptotically equal to the dimension. Links with
the conjecture of Hirsch, Haimovich's probabilistic analysis of
the shadow-vertex simplex algorithm, and the result of Dedieu, Malajovich
and Shub on the average total curvature of a bounded cell are also
presented.
Back to top
