Réunion d'hiver SMC 2023

Montréal, 1 - 4 decembre 2023

Résumés        

Théorie de la conception combinatoire
Org: Andrea Burgess (UNB, Saint John), David Pike (Memorial University) et Douglas Stinson (University of Waterloo & Carleton University)
[PDF]

MASOOMEH AKBARI, University of Ottawa
The Generalized Honeymoon Oberwolfach Problem with variable small cycle lengths  [PDF]

The Honeymoon Oberwolfach Problem (HOP), introduced by Šajna, is one of the most recent variants of the classic Oberwolfach Problem. This problem asks whether it is possible to seat $2m_1+2m_2+\ldots+2m_t=2n$ participants consisting of $n$ newlywed couples at $t$ round tables of sizes $2m_1, 2m_2, \ldots, 2m_t$ for $2n-2$ successive nights so that each participant sits next to their spouse every time and next to each other participant exactly once. HOP has been studied by Jerade, Lepine and Šajna, and some significant cases of it have been solved.

We generalize HOP by allowing tables of size two, instead of a minimum size of four as previously defined in HOP. Thus, in the generalized HOP, we are aiming to seat the $2n$ participants at $s$ tables of size $2$ and $t$ round tables of sizes $2m_1, 2m_2, \ldots, 2m_t$ with the assumption that $2n = 2s + 2m_1+2m_2+\ldots+2m_t$. In this talk, we will present a general approach to this problem, and we will show that the generalized HOP has a solution whenever $m_1+m_2+\ldots+m_t\leq 10$, that is, the sum of the table sizes other than size $2$ is at most $20$.

AMIN BAHMANIAN, Illinois State University
Toward a Three-dimensional Counterpart of Cruse's Theorem  [PDF]

Completing partial latin squares is NP-complete. Motivated by Ryser's theorem for latin rectangles, in 1974, Cruse found conditions that ensure a partial symmetric latin square of order $m$ can be embedded in a symmetric latin square of order $n$. Loosely speaking, this results asserts that an $n$-coloring of the edges of the complete $m$-vertex graph $K_m$ can be embedded in a one-factorization of $K_n$ if and only if $n$ is even and the number of edges of each color is at least $m-n/2$. We establish necessary and sufficient conditions under which an edge-coloring of the complete $\lambda$-fold $m$-vertex 3-graph $\lambda K_m^3$ can be embedded in a one-factorization of $\lambda K_n^3$. In particular, we prove the first known Ryser type theorem for hypergraphs by showing that if $n\equiv 0 \pmod 3$, any edge-coloring of $\lambda K_m^3$ where the number of triples of each color is at least $m/2-n/6$, can be embedded in a one-factorization of $\lambda K_n^3$. Finally we prove an Evans type result by showing that if $n\equiv 0 \pmod 3$ and $n\geq 3m$, then any $q$-coloring of the edges of any $F\subseteq\lambda K_m^3$ can be embedded in a one-factorization of $\lambda K_n^3$ as long as $q\leq \lambda \binom{n-1}{2}-\lambda \binom{m}{3}/\lfloor{m/3\rfloor}$.

These results can be restated as results on embedding partial symmetric layer-rainbow latin cubes in partial symmetric layer-rainbow latin cubes where all diagonal entries are empty.

ANDREA BURGESS, University of New Brunswick Saint John
Equitable colourings of cycle systems  [PDF]

A $c$-colouring of a design is an assignment of $c$ colours to its points. We call such a colouring equitable if in each block, the number of points of any two given colours differ by at most one; that is, in each block, all colours appear as closely as possible to an equal number of times.

Equitable colourings of cycle systems were introduced in work by Adams, Bryant, Lefevre and Waterhouse, who considered equitably $2$- and $3$-colourable $\ell$-cycle systems of $K_v$ and $K_v-I$ for $\ell \in \{4,5,6\}$. In this talk, we discuss some constructions of equitably $2$-colourable $\ell$-cycle decompositions of $K_v$ and $K_v-I$ in the case that $v$ and $\ell$ have the same parity. In particular, we show that there is an equitably $2$-colourable $\ell$-cycle system of $K_v$ whenever $\ell$ is odd and $v \equiv 1$ or $\ell \pmod{2\ell}$.

This is joint work with Francesca Merola.

AMANDA CHAFEE, Carleton University
Conditions for a Block Intersection Graph (BIG) of Packings and Coverings to be Hamiltonian & their Relationship to DCCD  [PDF]

A double change covering design (DCCD) is a sequence of $b$ $k$-sets, called blocks, of a $V$-set in which exactly two elements differ between consecutive blocks and every pair of elements in $V$ is in some block.

We determine sufficient conditions for the block intersection graph (BIG) of block size $k$ packings and block size 3 coverings to be Hamiltonian. The BIG of a packing is Hamiltonian for $k$ even if $4[|X||V \backslash X|-\partial(X)] \geq vk$ and for $k$ odd if $4k[|X||V \backslash X|-\partial(X)\geq v(k^2-1)$. The BIG of a covering is Hamiltonian if $v \geq 3$. Because of our interest in DCCD, we are also interested in Hamiltonian cycles in 1-BIG of block size 3 coverings and we discuss our progress in this case.

PETER DANZIGER, Toronto Metropolitan University
Colouring Kirkman triple systems  [PDF]

A weak $\delta$-colouring of a block design is an assignment of $\delta$ colours to the point set so that no block is monochromatic. The weak chromatic number $\chi(S)$ of a block design $S$ is the smallest integer $\delta$ such that $S$ has a weak $\delta$-colouring. It has previously been shown that any Steiner Triple System has weak chromatic number at least $3$ and that for each $v\equiv 1$ or $3\pmod{6}$ there exists a Steiner triple system on $v$ points that has weak chromatic number $3$. Moreover, for each integer $\delta \geq 3$ there exist infinitely many Steiner triple systems with weak chromatic number $\delta$.

In this talk we consider colourings of the subclass of Steiner triple systems which are resolvable, namely Kirkman Triple Systems. We show that for each $v\equiv 3\pmod{6}$ there exists a Kirkman Triple System on $v$ points with weak chromatic number $3$. We also show that for each integer $\delta \geq 3$, there exist infinitely many Kirkman triple systems with weak chromatic number $\delta$.

CALEB JONES, Memorial University of Newfoundland
Burning Steiner Triple Systems  [PDF]

We introduce a round-based model much like graph burning which applies to hypergraphs. The rules for this new model are very natural, and generalize the original model of graph burning. A second model called ``lazy burning'' is also introduced, along with a new parameter, the lazy burning number. We mostly focus on applying these models to Steiner triple systems, as they have a special significance in the context of burning. We obtain a lower bound on the burning number and an upper bound on the lazy burning number of an STS. Some additional interesting results are shown, such as the fact that there are infinitely many STSs with lazy burning number 3. Finally, we consider a ``doubling construction'' for STSs, and use it to show that for every natural number $n$ there is an STS with lazy burning number $n$.

MELISSA KERANEN, Michigan Technological University
Decomposition of complete graphs into disconnected unicyclic graphs with six edges  [PDF]

Let $G$ be a disconnected unicyclic graph with six edges. We prove that $G$ decomposes the complete graph $K_{n}$ if and only if $n \equiv 0,1,4,$ or $9 \pmod{12}$, with one exception when $n=9$. In this talk, I will discuss methods used to prove this result. This result, along with other knows results, gives a complete answer as to which complete graphs allow $G$-decompositions when $G$ is a graph with six edges.

DON KREHER, Michigan Technological University
Divisible and transverse Bussey systems  [PDF]

A set-system of order $N$ is a pair $(X,B)$, where $X$ is $N$-element set of points and $B$ is a collection of subsets of $X$ called $blocks$.

In 1852, Professor Dr. J. Steiner of Berlin, asked for which number $N$ does there exist a set system containing no pairs that has order $N$ and maximum block size $k$ satisfying

(1) no block properly contains another block, and

(2) for all $t=2,3,...,k-1$ every $t$-set that does not contain a block is contained in exactly one block of size $(t+1)$ .

W.H. Bussey from the University of Minnesota in 1914 constructed the only known solution. His construction provided for each $k\geq 5$ a set-system of order $N=2^{k-1}-1$ and maximum block size $k$ that satisfies Steiner's conditions. At the CMS 75th+1 anniversary summer meeting, I presented our investigation on this problem. See:

C.J. Colbourn, D.L. Kreher and P.R.J. Östergård, Bussey systems and Steiner's tactical problem. $Glas.$ $Mat.$ $Ser.$ $III$, web.math.pmf.unizg.hr/glasnik/forthcoming/pGM7100.pdf

Today's discussion will examine what happens when pairs are allowed as blocks. In particular we consider as blocks the edges of the complete multipartite graph $G=K_{n_1,n_2,\ldots,n_r}$ or its complement $\overline{G}$.

JEHYUN LEE, Michigan Technological University
Uniformly resolvable decompositions of $K_v-I$ into $5$-stars  [PDF]

We considered existence problem of uniformly resolvable decompositions of $K_v$ into subgraphs such that each resolution class contains only blocks isomorphic to the same graph. In this talk, I will discuss a complete solution for the case in which one resolution class is $K_2$ and the rest are $K_{1,5}$.

SHUXING LI, University of Delaware
Balanced Splittable Hadamard Matrices: Constraints and Constructions  [PDF]

The construction and analysis of Hadamard matrices have been a long standing problem in combinatorial design theory. Recently, Kharaghani and Suda introduced balanced splittable Hadamard matrices, a special type of Hadamard matrices with intriguing internal structures. These matrices have natural connections to various combinatorial objects, especially strongly regular graphs. We will outline constraints on the parameters of balanced splittable Hadamard matrices and describe a construction method using elementary abelian $2$-groups.

BILL MARTIN, Worcester Polytechnic Institute
Delsarte designs in finite groups  [PDF]

Let $G$ be a finite group with $d$ non-trivial conjugacy classes and let $\{\chi_0,\chi_1,\ldots,\chi_d\}$ be the full set of irreducible characters of $G$ where $\chi_0$ is the trivial character. For $T \subseteq \{1,\ldots,d\}$ a \emph{Delsarte $T$-design} in $G$ (or, more precisely, in the conjugacy class association scheme of $G$) is a subset $C\subseteq G$ satisfying $\sum_{x,y\in C} \chi_j\left(xy^{-1}\right) =0$ for all $j\in T$. A very interesting problem that is wide open in most cases is to characterize the $T$-designs in some standard family of finite groups and to find the most efficient (i.e., smallest) designs for various choices of $T$. In 2006, Bruce Sagan and I gave combinatorial characterizations of $T$-designs in the symmetric groups and showed that the smallest designs are typically much smaller than the smallest subgroups with the $T$-design property. In a recent preprint, Alena Ernst and Kai-Uwe Schmidt carried out a similar study for finite general linears groups, with rich results and difficult proofs. I aim to survey these results and, as time permits, give a preliminary report on the case of dihedral groups, an ongoing joint project with undergraduate students Benjaminh Brodeur and Sycamore Herlihy.

LUCIA MOURA, University of Ottawa
Cover-free families on hypergraphs  [PDF]

Cover-free families, also called superimposed codes, are widely studied combinatorial objects used in combinatorial group testing and in many applications in cryptography and communications. A $d$-CFF$(t,n)$ is a $t\times n$ incidence matrix of a set system where no set is contained in the union of up to $d$ other sets. Cover-free families are used for solving the non-adaptive group testing problem: find a set of up to $d$ defective items among $n$ items, by testing them in pre-specified groups corresponding to rows of the matrix (tests). The objective is to minimize the number $t$ of tests.

In this talk, we consider cover-free families on hypergraphs, which are generalizations of cover-free families used in applications where the possible sets of defective items are specified by the edges of a hypergraph. The traditional group testing problem is the special case where the edges of the hypergraph are all $d$-subsets of an $n$-set. We discuss recent constructions and our ongoing research on this topic.

KATE NIMEGEERS, University of Victoria
Pseudoku: A Sudoku Adjacency Algebra and Fractional Completion Threshold  [PDF]

We develop a $4$-partite graph representation, $G_P$, for a partial Sudoku, $P$. The partite sets correspond to the rows, columns, boxes, and symbols of $P$. The edges represent unfulfilled conditions in $P$ that are necessary for a completed Sudoku. For instance, if a symbol is missing from a row in $P$ then an edge is drawn between those two vertices in $G_P$. We define a tile to be a $4$-vertex subgraph of $G_P$ corresponding to a valid placement of a symbol in $P$, noting that $P$ can be completed if and only if $G_P$ permits an edge-decomposition into tiles. We then relate the existence of such a decomposition to the existence of a solution to a specific linear system using an edge-tile inclusion matrix. Through an in-depth analysis of this matrix structure, we uncover a Sudoku adjacency algebra. This algebraic framework is constructed from a coherent configuration consisting of equivalence relations among row-column, row-symbol, column-symbol, and box-symbol Sudoku conditions.\

The primary result we present is a minimum degree threshold for $G_P$ that allows for a fractional tile-decomposition and therefore implies the existence of a fractional completion of $P$. The proof employs spectral decomposition, the properties of coherent configurations, and perturbation theory to estimate a generalized inverse for the matrix representation of a partial Sudoku puzzle in order to find a solution for the relaxed linear system. Improving on this result by finding a minimum degree threshold for an exact tile-decomposition is an interesting open question in this research area.

GUILLERMO NUNEZ PONASSO, Worcester Polytechnic Institute
Maximal determinants of matrices with entries in the roots of unity  [PDF]

Hadamard's determinant inequality states that the determinant of a complex matrix $M$ of order $n$ with entries taken from the complex unit circle satisfies $|\det M|\leq n^{n/2}$ — the matrix $M$ meets this bound with equality if and only if $MM^* =nI_n$.

It is well known that when $M$ is real (having $\pm 1$ entries), then $MM^{\intercal}=nI_n$ implies that $n=1,2$ or $n$ is a multiple of $4$. Therefore, if we consider the maximal determinant of matrices with entries in the set $\{+1,-1\}$, then Hadamard's bound is not achievable at odd orders, or at orders $n\equiv 2\pmod{4}$ larger than $2$. In the literature, one can find improved upper and lower bounds for the determinant of $\pm 1$ matrices — the exact values of the maximal determinant have been determined for small values of n, and through several infinite families of examples. $\ $

In this talk, we consider the more general problem of finding the maximal determinant of matrices with entries taken from the set $\mu_m$ of $m$-th roots of unity, for some fixed value of $m$. We will present new upper and lower bounds for the determinant for a general value of $m$, and study the ternary case $m=3$, and quaternary case $m=4$ in more detail.

The maximality of the determinant sometimes imposes strong regularity conditions that make the matrices be equivalent to certain combinatorial designs. Conversely, constructions making use of designs or finite geometries, often give large values for the determinant. We will pay special attention to such connections.

MATEJA SAJNA, University of Ottawa
A recursive construction of solutions to the directed Oberwolfach problem  [PDF]

The celebrated Oberwolfach problem, over 50 years old and in general still open, asks whether $n$ participants at a conference can be seated at $k$ round tables of sizes $m_1, \ldots, m_k$ (where $m_1+ \ldots +m_k=n$) for several meals so that everybody sits next to everybody else exactly once. This problem can be modeled as a decomposition of the complete graph $K_n$ into 2-factors, each consisting of $k$ disjoint cycles of lengths $m_1, \ldots, m_k$.

In the directed version, we are interested in decomposing $K_{n}^\ast$, the complete symmetric digraph of order $n$, into spanning subdigraphs, each a disjoint union of $k$ directed cycles of lengths $m_1, \ldots, m_k$ (where $m_1+ \ldots +m_k=n$). Such a decomposition models a seating arrangement of $n$ participants at $k$ tables of sizes $m_1, \ldots, m_k$ such that everybody sits to the right of everybody else exactly once.

While the Oberwolfach problem for cycles of uniform length was solved decades ago, the solution to the directed version for uniform-length cycles was completed only in 2023, and while many infinite families of cases of the Oberwolfach problem with variable cycle lengths are known to have a solution, very little is known about the directed version with variable cycle lengths. In this talk, we present a recursive construction that generates solutions to many infinite families of cases of the directed Oberwolfach problem with variable cycle lengths. In particular, we obtain an almost-complete solution to the two-table directed Oberwolfach problem.

This is joint work with Suzan Kadri.

KIANOOSH SHOKRI, University of Ottawa
Improving upper bounds on the size of some covering arrays of strength 3  [PDF]

A Covering array CA$(N; t, k, v)$ is an $N \times k$ array over an alphabet with $v$ symbols with the property that for any $t$ arbitrary columns, all $t$-tuples from the alphabet occurs at least once as a row. The objective is to minimize $N$, which is the size of the covering array, for given $t$, $k$, and $v$. We employ CA$(2q^3-1; 3, q^2 + q + 1, q)$ constructed by Raaphorst, Moura, and Stevens (2014) based on linear feedback shift register (LFSR) sequences in finite fields as the main ingredients of the generalized “Roux-type” constructions. By using various properties of covering arrays constructed by LFSR sequences, we improve the size of some CAs of strength $3$ compared to the best-known CAs provided in the online covering array tables maintained by Colbourn. In particular, we construct CA$(2q^3 + (q-2)(2q^2-q); 3, 2(q^2 + q + 1), q)$, CA$(2q^3 + (q-2)(2q^2-q) + q^3 - q^2; 3, q(q^2 + q + 1), q)$, CA$(8q^3 - 10q^2+ 4q -1; 3, q^2(q^2 + q + 1), q)$, and CA$(8q^3 - 10q^2+ 3q; 3, (q^2 - q + 1)(q^2 + q + 1), q)$ for any prime power $q$, and CA$(8q^3 - 10q^2+ 3q; 3, q^2(q^2 + q + 1), q)$ for even prime power $q$. This is joint work with Lucia Moura.

BRETT STEVENS, Carleton University
Classification and enumeration of single change covering designs  [PDF]

Single change covering designs were initially studied in 1969 as a means to optimize magnetic tape access to fill core memory. In a series of ten papers from 1993 to 2001 By Constable, McSorley, Phillips, Preece, Van Rees, Wallis, Yucas and Zhang, the spectrum of SCCDs with block size 2 and 3 was completely solved, progress was made for block sizes 4 and higher and the investigation of ``circular'' SCCD was begun. In 2018 A. Chafee developed the first recursive construction for circular SCCD which prompted the search and enumeration of small ingredient designs. We describe a canonical augmentation search to enumerate SCCD and generalize Phillips' ``end-permutation'' and ``minor variant'' classification schemes. We report our findings so far.

DOUG STINSON, University of Waterloo
Circular external difference families, graceful labellings and cyclotomy  [PDF]

We discuss a variety of external difference families (EDFs), including strong and circular variants. The study of these combinatorial objects is motivated by applications to robust and nonmalleable threshold schemes. However, they are also of intrinsic interest, apart from applications. In this talk, we mainly discuss mathematical aspects, especially existence and nonexistence, of circular and strong circular EDFs. Two of the interesting construction techniques involve using graceful labellings to construct circular EDFs, and using classical results on cyclotomic numbers to obtain close approximations to (nonexistent) strong circular EDFs.


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