May 20, 2018

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