Réunion d'hiver SMC 2020

Montréal, 4 - 7 décembre 2020


Design combinatoire
Org: Peter Dukes (UVic), Karen Meagher (Regina) et Brett Stevens (Carleton)

CURTIS BRIGHT, University of Windsor
A Resolution of Lam's Problem via Satisfiability Solvers  [PDF]

Lam's problem is to determine if a projective plane of order ten exists—a long-standing question since the 1800s when finite projective geometry was first studied. Lam's problem was experimentally resolved via a huge case breakdown and exhaustive computer search in the late 1980s. Despite this fantastic achievement, the resolution relied on special-purpose search code that was never independently verified.

We provide an independent resolution of Lam's problem by reducing the problem to a satisfiability (SAT) problem in Boolean logic that we solve with a combination of SAT solvers and computer algebra systems. Our resolution provides a collection of certificates that a third party can use to verify the nonexistence of a projective plane of order ten.

ANDREA BURGESS, University of New Brunswick
On the Oberwolfach Problem for single-flip 2-factors via graceful labellings  [PDF]

The Oberwolfach problem, OP$(F)$, first posed by Ringel in 1967, asks for a decomposition of the complete graph $K_v$ into copies of a given 2-factor $F$ of order $v$. We give a solution whenever $F$ has a sufficiently large odd cycle meeting a specified lower bound and, in addition, $F$ has a single-flip automorphism (i.e. an involutory automorphism which acts as a reflection on exactly one cycle of $F$). For even orders $v$, we give analogous results for the maximum packing and minimum covering variants of the problem for single-flip 2-factors with a sufficiently large even cycle. Our methods involve applying a doubling construction to graceful labellings of 2-regular graphs with a vertex removed, and allow us to explicitly construct solutions to the Oberwolfach Problem with well-behaved automorphisms.

This is joint work with Peter Danziger and Tommaso Traetta.

PETER DANZIGER, Ryerson universtiy
Directed cycle decompositions of complete digraphs  [PDF]

We consider the problem of decomposing the complete directed graph $K_n^*$ into directed cycles of given lengths. We give general necessary conditions for a directed cycle decomposition of $K_n^*$ into $t$ directed cycles of lengths $m_1, m_2, \ldots, m_t$ to exist and provide a construction for creating such decompositions in the case where there is one 'large' cycle.

We give a complete solution in the case when there are exactly three cycles of lengths $\alpha, \beta, \gamma \neq 2$. Somewhat surprisingly, the general necessary conditions turn out not to be sufficient in this case. In particular, taking $\gamma \geq \beta \geq \alpha > 2$, we show that when $\gamma=n$, $\alpha+\beta > n+2$ and $\alpha+\beta \equiv n$ (mod 4), $K_n^*$ is not decomposable.

Joint work with A.C. Burgess and M.T. Javed

IREN DARIJANI, University of Lethbridge
Colourings of star systems  [PDF]

An $e$-star is a complete bipartite graph $K_{1,e}$. An $e$-star system of order $n>1$, $S_e(n)$, is a partition of the edges of the complete graph $K_n$ into $e$-stars. An $e$-star system is said to be $k$-colourable if its vertex set can be partitioned into $k$ sets (called colour classes) such that no $e$-star is monochromatic. The system $S_e(n)$ is $k$-chromatic if $S_e(n)$ is $k$-colourable but is not $(k-1)$-colourable. If every $k$-colouring of an $e$-star system can be obtained from some $k$-colouring $\phi$ by a permutation of the colours, we say that the system is uniquely $k$-colourable. In this talk, we will first see some results on colourings of 3-star systems. Next, we generalize these results for $e$-star systems for any $e\geq 3$. Finally, we see some other results on unique colourings of $e$-star systems that for any $e\geq 3$.

COEN DEL VALLE, University of Victoria
Block designs of dimension three  [PDF]

The dimension of a block design is the maximum positive integer $d$ such that any $d$ points are contained in a proper subdesign. \

This talk will discuss the currently known existence results of pairwise balanced designs PBD$(v,K)$ of dimension three, for the sets of block sizes $K=\{3,4\}$, and $K=\{3,5\}$. Also to be discussed is dimension three triple systems of arbitrary index, whose existence is a consequence of the existence of the aforementioned pairwise balanced designs.\

This is based on work with Peter Dukes, extending previous work by Dukes and Joanna Niezen.

TAO FENG, Beijing Jiaotong University
Nov\'{a}k's conjecture on cyclic Steiner triple systems and its generalization  [PDF]

Nov\'{a}k conjectured in 1974 that for any cyclic Steiner triple systems of order $v$ with $v\equiv 1\pmod{6}$, it is always possible to choose one block from each block orbit so that the chosen blocks are pairwise disjoint.

In this talk, we shall consider the generalization of this conjecture to cyclic $(v,k,\lambda)$-designs with $1 \leq \lambda \leq k-1$. Superimposing multiple copies of a cyclic symmetric design shows that the generalization cannot hold for all $v$, but we conjecture that it holds whenever $v$ is sufficiently large compared to $k$. We confirm that the generalization of the conjecture holds when $v$ is prime and $\lambda=1$ and also when $\lambda \leq (k-1)/2$ and $v$ is sufficiently large compared to $k$. As a corollary, we show that for any $k \geq 3$, with the possible exception of finitely many composite orders $v$, every cyclic $(v,k,1)$-design without short orbits is generated by a $(v,k,1)$-disjoint difference family.

This is joint work with Daniel Horsley and Xiaomiao Wang.

Approximate Steiner triple systems of large girth  [PDF]

A Steiner triple system of order $n$ is a set of triples in an $n$-set such that every pair is contained in exactly one triple. Erd\H{o}s conjectured in 1973 that for fixed g and any sufficiently large `admissible' order $n$, there exists a Steiner triple system of order $n$ with girth at least $g$, meaning that there are no $j$ points which span at least $j$-2 triples for all $3< j< g$. We motivate this notion of sparseness and discuss the state of the art of the conjecture. Our contribution is an approximate solution using probabilistic methods.

The talk is based on joint work with Daniela Kühn, Allan Lo and Deryk Osthus.

KEVIN HALASZ, Simon Fraser University
Near transversals in group-based latin squares  [PDF]

Latin squares (of order $n$) are $n \times n$ arrays in which each row and each column is a permutation of the integers $[0,n-1]$. We say a latin square $L$ is group-based if it is possible to order the elements of a group $G=\{g_0,g_1,\ldots,g_{n-1}\}$ so that $L_{i,j}=k$ if and only if $g_i \cdot g_j = g_k$.

A famous conjecture, variously attributed to Ryser, Brualdi, and Stein, asserts that in every latin square of order $n$ it is possible to find a collection of $n-1$ cells which intersects each row and column, and contains each symbol, at most once---such a collection of cells is known as a near transversal. In this talk we will outline the proof that group-based latin squares satisfy the Ryser-Brualdi-Stein conjecture. We will then explain why the resolution of this special case is far from the end of the discussion of near transversals in group-based latin squares.

DANIEL HORSLEY, Monash University
An Evans-style result for block designs  [PDF]

A now-proven conjecture of Evans states that any partial latin square with at most $n-1$ filled cells can be completed to a latin square. This is tight: there are uncompletable partial latin squares with $n$ filled cells. This talk will discuss the analogous problem for block designs.

An $(n,k,1)$-design is a collection of $k$-subsets (blocks) of a set of $n$ points such that each pair of points occur together in exactly one block. If this restriction is relaxed to require only that each pair of points occur together in at most one block we instead have a partial $(n,k,1)$-design. I will outline a proof that any partial $(n,k,1)$-design with at most $\frac{n-1}{k-1}-k+1$ blocks is completable to a $(n,k,1)$-design provided that $n$ is sufficiently large and obeys the obvious necessary conditions for an $(n,k,1)$-design to exist. This result is tight for all $k$. I will also mention some related results concerning edge decompositions of almost complete graphs into copies of $K_k$. All of this work is joint with Ajani De Vas Gunasekara.

HADI KHARAGHANI, University of Lethbridge
On Equiangular Tight Frames  [PDF]

\abstract{ A family of lines through the origin in a Euclidean space is called equiangular if the absolute value of the inner product of each pair of lines is a constant. A $d\times n$, $d<n$ matrix $F$ with real entries is a Frame if the absolute value of the off-diagonal entries of $F^TF$ is a constant. A $d\times n$ Frame is Tight if the rows are pairwise orthogonal and it is Flat if the absolute value of the entries stays the same. A new construction method makes use of Block Shapiro-Golay pairs. Applications lead to a class of Quasi-symmetric designs and Self-Complementary Codes attaining Grey-Rankin Bound. \

This is joint work with Thomas Pender and Sho Suda. }

Applications of incomplete pairwise balanced designs  [PDF]

In this talk, I will describe applications of our existence results for incomplete pairwise balanced designs, IPBD$((v;w),K)$. IPBDs provide a surprisingly powerful tool for constructing designs with substructures. We describe two basic techniques for applications: using an IPBD as a `template' in constructions and using IPBDs instead of PBDs in PBD-closure. Several examples will be given to illustrate the power of these techniques. These examples include using IPBDs to construct incomplete mutually orthogonal latin squares and resolvable designs with sub-designs. All of this work is joint work with Peter Dukes.

TRENT MARBACH, Ryerson University
The localization number of designs  [PDF]

We study the localization number of incidence graphs of designs. In the localization game played on a graph, the cops attempt to determine the location of an invisible robber via distance probes. The localization number of a graph $G$, written $\zeta(G)$, is the minimum number of cops needed to ensure the robber's capture. We present work giving bounds and exact values for the incidence graphs of a number of classes of designs.

MAHSA NASROLLAHI, University of Regina
The Erdős-Ko-Rado theorem for 2-intersecting families of perfect matchings  [PDF]

The \emph{Erd\H{o}s-Ko-Rado} (EKR) theorem is a classical result in extremal combinatorics. It states that if $n$ and $k$ are such that $n\geq 2k$, then any intersecting family $\mathcal{F}$ of $k$-subsets of $[n] = \{ 1,2,\ldots,n\}$ has size at most $\binom{n-1}{k-1}$. Moreover, if $n>2k$, then equality holds if and only if $\mathcal{F}$ is a \emph{canonical} intersecting family; that is, $\bigcap_{A\in \mathcal{F}}A = \{i\}$, for some $i\in [n]$.

The EKR theorem can be extended to various combinatorial objects. In this presentation, I will talk about an extension of the EKR theorem to $2$-intersecting families of perfect matchings. In particular, I prove that any $2$-intersecting family of perfect matchings of $K_{2k}$ has size at most $(2k-5)\times (2k-7) \times \ldots 3\times 1$, for any $k\geq 3$.

KIRSTEN NELSON, Carleton University
Interleaved Sequences  [PDF]

A covering array CA$(N; t, k, v)$ is a $N \times k$ array over an alphabet of $v$ elements such that for any $t$-set of columns, each possible arrangement of $t$ alphabet elements occurs at least once in a row. Finding the smallest number of rows $N$ in the array is a central problem, with many good bounds and construction methods for some, but not all, sets of parameters. Covering arrays can be made by taking a sequence with a coverage property and circulating it into a matrix. In this talk we examine interleaved sequences, created by combining a base sequence of period $s$ with nice coverage properties and a shift sequence $e$ of length $T$, consisting of elements from $Z(q) \cup \infty$ . We will discuss what properties are inherited from the base sequence, and under which conditions this is possible. Finally we demonstrate the potential for interleaved sequences to create $\epsilon$-almost covering arrays, where all but $\epsilon {k \choose t}$ of tuples are covered for a ‘small’ $\epsilon$.

JOANNA NIEZEN, University of Victoria
Sarvate-Beam Group Divisible Designs  [PDF]

The existence of Sarvate-Beam designs is explored, named after its founders D.G. Sarvate and W. Beam. In an adesign, the number of times a specified pair of points occurs together in a block is called the pair frequency. A Sarvate-Beam design is an adesign where the set of pair frequencies cover an interval of distinct nonnegative integers. The main result of this work is to completely settle the existence of uniform Sarvate-Beam group divisible designs with blocks of size three where the smallest pair frequency is zero. Higher starting frequencies are also considered and mostly settled. A case of special interest are Sarvate-Beam group divisible designs with three uniform groups, which has a nice geometric interpretation. This work is joint with Dr. Peter Dukes.

DAVID PIKE, Memorial University of Newfoundland
Colourings of Group Divisible Designs  [PDF]

A group divisible design (GDD) consists of a set $V$ of points, a set ${\cal G}$ of subsets of $V$ called groups that partition $V$, and a set ${\cal B}$ of subsets of $V$ called blocks such that each pair of points that does not occur together in a group occurs together in exactly one block. A colouring of a design is a labelling of its points with colours so that no block is monochromatic; i.e., it is a function $f:V \rightarrow C$ where $C$ is a set of elements called colours, such that $|\{ f(x) : x \in B \}| \geqslant 2$ for each $B \in {\cal B}$. The chromatic number of a design is the least number of colours for which the design admits such a colouring. We will discuss colourings of GDDs, particularly those for which each group has the same size $g$ and each block has the same size $k$.

This is joint work with A.C. Burgess, P. Danziger, J.H. Dinitz and D.M. Donovan.

MATEJA SAJNA, University of Ottawa
Bipartite 2-factorizations of complete multigraphs via layering  [PDF]

Layering is in principle a simple method that allows us to obtain a type-specific 2-factorization of a complete multigraph (or complete multigraph minus a 1-factor) from existing 2-factorizations of complete multigraphs and complete multigraphs minus a 1-factor. This technique is particularly effective when constructing bipartite 2-factorizations; that is, 2-factorizations with all cycles of even length.

In this talk, we shall give a thorough introduction to layering, and then describe new bipartite 2-factorizations of complete multigraphs obtained by layering. In particular, for complete multigraphs and bipartite 2-factors with no 2-cycles, we obtain a complete solution to the Oberwolfach Problem and an almost complete solution to the Hamilton-Waterloo Problem.

This is joint work with Amin Bahmanian.

© Société mathématique du Canada : http://www.smc.math.ca/