Réunion d'hiver SMC 2025

Toronto, 5 - 8 decembre 2025

Théorie de la conception combinatoire
Org: Alice Lacaze-Masmonteil (University of Regina), David Pike (Memorial University of Newfoundland) et Doug Stinson (University of Waterloo)
[PDF]

MASOOMEH AKBARI, University of Ottawa A Complete Solution to the Generalized HOP with One Round Table [PDF]

The Honeymoon Oberwolfach Problem (HOP), introduced by Šajna, is a recent variant of the classic Oberwolfach Problem. This problem asks whether it is possible to seat $2m_1 + 2m_2 + \dots + 2m_t = 2n$ participants, consisting of $n$ newlywed couples, at $t$ round tables of sizes $2m_1, 2m_2, \dots, 2m_t$ for $2n - 2$ successive nights, so that each participant sits next to their spouse every night and next to every other participant exactly once. This problem is denoted by $\mathrm{HOP}(2m_1, 2m_2, \ldots, 2m_t)$. Jerade, Lepine, and Šajna have studied the HOP and resolved several important cases.

We generalized the HOP by allowing tables of size two, relaxing the previous restriction that tables must have a minimum size of four. In the generalized HOP, we aim to seat the $2n$ participants at $s$ tables of size $2$ and $t$ round tables of sizes $2m_1, 2m_2, \dots, 2m_t$, where $2n = 2s + 2m_1 + 2m_2 + \dots + 2m_t$ and $m_i \geq 2$, while preserving the adjacency conditions of the HOP. We denote this problem by $\mathrm{HOP}(2^{\langle s \rangle}, 2m_1, \ldots, 2m_t)$.

In this talk, we present a general approach to this problem and provide a solution to the generalized HOP with one round table, showing that the necessary condition for $\mathrm{HOP}(2^{\langle s \rangle}, 2m)$ to have a solution is also sufficient.

TIM ALDERSON, University of New Brunswick, Saint John Maximal Arcs and Maximal-length A$^s$MDS Codes: Existence and Obstructions [PDF]

We investigate the existence of linear codes whose parameters meet the maximum possible length for a given Singleton defect $s\ge 1$—so-called A$^s$MDS codes. We survey known existence results for maximal-length A$^s$MDS codes in small dimensions, highlighting dimensions 2 and 3, including the Barlotti condition that $s+2$ divides $q$. For higher-dimensional projective spaces maximal codes do not exist when $s > q$, while constructions exist for special cases such as $s = q - 1$ and $s = q - 2$ when $k\le 4$.

Long A$^s$MDS codes are necessarily projective and dual to AMDS codes, and we develop arithmetic conditions that restrict the possible existence of such codes. The talk concludes with a summary of bounded values of $\kappa(s, q)$ - the maximum dimension for which there (may) exist maximal-length A$^s$MDS codes and provide (and perhaps settle) conjectures.

ANDREA BURGESS, University of New Brunswick Saint John Cyclic circular external difference families [PDF]

A $(v,m,\ell,1)$-Circular External Difference Family (CEDF) is an $m$-sequence $(A_1, \ldots, A_m)$ of $\ell$-subsets of an additive group $G$ of order $v$ such that the multiset of all differences $a-a'$, with $(a,a')\in A_{i+1\pmod{m}}\times A_{i}$ for some $i \in \mathbb{Z}_m$, is equal to $G \setminus \{0\}$. When $G=\mathbb{Z}_v$, we speak of a cyclic CEDF. CEDFs are a variation of External Difference Families, and have been recently introduced as a tool to construct non-malleable threshold schemes.

Necessarily, if a $(v,m,\ell,1)$-CEDF exists, then $v=m\ell^2+1$. It is known that an $(m\ell^2+1,m,\ell,1)$-CEDF over the cyclic group exists whenever the number of subsets $m$ is even, while there cannot exist a cyclic CEDF for $m$ and $\ell$ both odd. In this talk, we consider the existence of cyclic CEDFs in the case that $m$ is odd and $\ell$ is even. In particular, we construct a cyclic $(m\ell^2+1,m,\ell,1)$-CEDF for any odd $m>1$ when $\ell=2$, and for any even $\ell \geq 2$ when $m=3$.

This is joint work with Francesca Merola and Tommaso Traetta.

AMANDA CHAFEE, Carleton University Hamiltonian Cycles on Coverings [PDF]

A covering design is a $v$-set $V$ and a list $B$ of $b$ blocks of size $k$ where every pair from $V$ must occur in at least one block. A 1-block intersection graph (1-BIG) is a graph $G=(B,E)$, where $b\in B$ and $(b,b') \in E$ if $|b\cap b'|=1$ for $b,b' \in B$. This talk will go over what independence sets look like in a 1-BIG based on coverings with $k=3$. We prove that optimal $k=3$ coverings $v\equiv 5\pmod{3}$ have a Hamiltonian cycle and show why this proof fails for even $v$.

PETER DANZIGER, Toronto Metropolitan University Packing designs with large block size [PDF]

Given positive integers $v,k,t$ and $\lambda$ with $v \geq k \geq t$, a packing design PD$_{\lambda}(v,k,t)$ is a pair $(V,{\cal B})$, where $V$ is a $v$-set and ${\cal B}$ is a collection of $k$-subsets of $V$ such that each $t$-subset of $V$ appears in at most $\lambda$ elements of $\cal B$. When $\lambda=1$, a PD$_1(v,k,t)$ is equivalent to a binary code with length $v$, minimum distance $2(k-t+1)$ and constant weight $k$. The maximum size of a PD$_{\lambda}(v,k,t)$ is called the packing number, denoted PDN$_{\lambda}(v,k,t)$.

We consider packing designs with $k$ large relative to $v$. In this case, we extend the second Johnson bound to arbitrary $\lambda$ and show that this bound is tight. Specifically, we prove that for a positive integer $n$, PDN$_{\lambda}(v,k,t) = n$ whenever $nk-(t-1)\binom{n}{\lambda+1} \leq \lambda v < (n+1)k-(t-1)\binom{n+1}{\lambda+1}$. For fixed $t$ and $\lambda$, this determines the value of PDN$_{\lambda}(v,k,t)$ when $k$ is large with respect to $v$. We also extend this result to directed packings, by showing that if no point appears in more than three blocks, then the blocks of a PD$_2(v,k,2)$ can be directed so that no ordered pair occurs more than once.

Joint work with Andrea Burgess, Daniel Horsley and Muhammad Tariq Javed

SHONDA DUECK, University of Winnipeg Cyclic partitions of complete hypergraphs and large sets of combinatorial designs [PDF]

We consider cyclic partitions of the complete $k$-uniform hy\-per\-graph on a finite set $V$, and their relationship to combinatorial designs. A $t$-com\-ple\-ment\-ary $k$-hy\-per\-graph is a $k$-uniform hy\-per\-graph with vertex set $V$ and edge set $E$ for which there exists a permutation $\theta\in Sym(V)$ such that the sets $E, E^\theta, E^{\theta^2}, \ldots, E^{\theta^{t-1}}$ partition the set of all $k$-element subsets of $V$. Such a permutation $\theta$ is called a $(t,k)$-com\-ple\-ment\-ing permutation. The $t$-com\-ple\-ment\-ary $k$-hy\-per\-graphs are a natural generalization of the almost self-com\-ple\-ment\-ary graphs, since the associated $(t,k)$-complementing permutation $\theta$ decomposes the complete $k$-uniform hypergraph into $t$ isomorphic $k$-hypergraphs, which are permuted cyclically by $\theta$. When these $t$-complementary $k$-hypergraphs in the decomposition are also regular, then they form a large set of $t$ isomorphic combinatorial designs. We will look at some algebraic constructions for large sets of combinatorial designs that arise from these cyclic decompositions, including one which generalizes the well know Paley graph construction.

ALENA ERNST, Worcester Polytechnic Institute Designs in finite general linear groups [PDF]

In his monumental Thesis in 1973, Delsarte introduced so-called $T$-designs, which generalise classical combinatorial designs by using a purely algebraic definition. In fact, a combinatorial design is equal to a $T$-design in the Johnson association scheme. Despite their purely algebraic definition, in the literature many $T$-designs have nice combinatorial characterisations. This confirms Delsarte's insight that this is indeed a general phenomenon, in his own words: “[...] $T$-designs will often have interesting properties.” In this talk, we elaborate on this insight and discuss results on $T$-designs in finite general linear groups $\operatorname{GL}(n,q)$. These designs turn out to be subsets acting transitively on flag-like structures, which are common generalisations of $t$-dimensional subspaces of $\mathbb{F}_q^n$ and bases of $t$-dimensional subspaces of $\mathbb{F}_q^n$. These results can be interpreted as $q$-analogues of corresponding results for the symmetric group. This is joint work with Kai-Uwe Schmidt.

CALEB JONES, Toronto Metropolitan University Current Trends in Hypergraph Burning [PDF]

Hypergraph burning is a relatively new model for the spread of influence throughout a complex network. We introduce the concept of a cover sequence in a hypergraph, and use it to analyze the ``lazy hypergraph burning'' model. In particular, we show that a lazy burning set and a cover sequence are equal and opposite concepts, and hence obtain a new characterization of lazy hypergraph burning. Using this new methodology, we improve several of the best known bounds on the lazy burning number of a hypergraph. Finally, we make use of a common dual construction to solve lazy hypergraph burning for all 2-regular hypergraphs.

WILLIAM KELLOUGH, Memorial University of Newfoundland BIBDs That Almost Have Locally Equitable Colourings [PDF]

In this talk, we analyze $\ell$-colourings of $(v,k,\lambda)$-BIBDs where within each block, one colour is absent and the rest appear $\frac{k}{\ell-1}$ times. We give necessary conditions for such colourings to exist. We show how Hadamard matrices, affine planes, and twin prime powers can be used to construct such coloured BIBDs.

DONALD KREHER, Michigan Technological University Factorization of finite groups [PDF]

Let $(G,\cdot)$ be a finite multiplicative group with identity $e$. For $A,B \subseteq G$, define \[AB = \{ gh \colon g \in A, h \in B\}\] and note that $AB$ is a multi-set. We say that $(A,B)$ is a $(\lambda,\mu)$-\emph{factorization of $G$} if in the product $AB$ each non-identity element appears $\lambda$ times and the identity occurs $\mu$ times. In the group ring $\mathbb{Z}[G]$ we write \[ AB = \lambda(|G|-e)+\mu e \] Given a subset $A \subseteq G$, if $B \subseteq G$ satisfies this group ring equation, then we say that $B$ is a $(\lambda,\mu)$-mate of $A$. A $\lambda$-mate with $\mu = 0$ and is simply called a $\lambda$-mate and if $\lambda=1$ and $\mu=0$, then it is called a mate.

A $(1,0)$-factorization of $G$ is called a a near-factorization of $G$ and is where my story begins. However a $(1,1)$-factorization $AB$ of $G$ when neither $A$ nor $B$ are subgroups of $G$ has perhaps received the most attention by investigators and will likely be where my story will end. Between these two events we have explored factorizations when $\lambda > 1$.

If there is a $(\lambda,\mu)$-factorization $(A,B)$ of $G$, with $\lambda\not=\mu$, then there is an explicit formula for $B$ in terms of $A$. This leads to a direct method for computing a $(\lambda,\mu)$-mates when they exist. Surprisingly it appears that it is more efficient to compute $(\lambda,\mu)$-mates using sophisticated backtracking tools.

ALICE LACAZE-MASMONTEIL, University of Regina On the directed Oberwolfach problem with tables of even lengths and $n \equiv 2 \ ( \textrm{mod}\ 4)$ guests [PDF]

A $(\vec{C}_{m_1},\vec{C}_{m_2},\ldots, \vec{C}_{m_t})$-factor of a directed graph $G$ is a spanning subdigraph of $G$ comprised of $t$ disjoint directed cycles of lengths $m_1, m_2, \ldots,$ $m_t$, where $m_i \geqslant 2$. In this talk, we will be constructing a decomposition of the complete symmetric digraph $K^*_{2n}$ into $(\vec{C}_{m_1},\vec{C}_{m_2},\ldots, \vec{C}_{m_t})$-factors when $m_1+m_2+\cdots+m_t=2n$, $t \geqslant 3$, and $n$ is odd. The existence of this decomposition implies a complete solution to the directed Oberwolfach problem with $t$ tables of even lengths and $2n$ guests such that $n$ is odd. This is joint work with Andrea Burgess and Peter Danziger.

SUMIN LEEM, University of Calgary Categorical design for encoding rule-based text [PDF]

Rule-based documents such as building codes contain intricate cross-references and logical conditions that can be organized into a mathematical structure. In this talk, we present a category-theoretic model for representing such texts. We begin by representing their reference network as a knowledge graph and then formalize the logical relations using ologs (ontology logs), a category-theoretic construction introduced by David Spivak. Within this setting, conjunctions and disjunctions correspond to pullbacks (limits) and pushouts (colimits), allowing logical composition to be expressed diagrammatically. This model provides a rigorous basis for rule logic and supports downstream integration with satisfiability modulo theories (SMT) solvers and large language models for automated reasoning tasks.

SHUXING LI, University of Delaware Perfect Sequence Covering Arrays: A Group-Based Approach [PDF]

Consider a set $P$ of permutations of $[n]=\{1,2,\ldots,n\}$, viewed as a set of ordered $n$-tuples. Assume that every ordered $k$-subsequence of distinct elements from $[n]$ appears exactly $\lambda$ times across the permutations in $P$. What is the minimum possible size of $P$? This natural question connects to directed $t$-designs, perfect deletion-correction codes, $k$-rankwise independent families of permutations, and a recent resurgence motivated by the introduction of perfect sequence covering arrays by Raphael Yuster. This talk presents resent progress on this problem, with an emphasis on a common group-based structure observed in certain perfect sequence covering arrays identified through sophisticated computer search.

This talk is based on joint work with Jonathan Jedwab and Jingzhou Na (Simon Fraser University).

TRENT MARBACH, Toronto Metropolitan University

WILLIAM MARTIN, Worcester Polytechnic Institute Hitting all the n-tuples from a distance [PDF]

For given integers $n,q \ge 2$, we seek the smallest size of a set $S$ of $q$-ary $n$-tuples with the property that every $q$-ary $n$-tuple differs from some member of $S$ in every coordinate. This is equivalent to computing the total domination number of a certain graph, namely the graph having $\mathbb{Z}_q^n$ as its vertex set and two vertices joined by an edge whenever they are at maximum Hamming distance $n$. This talk is based on joint work with Sam Adriaensen (VUB), Ferdinand Ihringer (SUSTech), and Ralihe Villagran (WPI).

SHAHRIYAR POURAKBAR SAFFAR, Memorial University of Newfoundland Constructing uniquely 2-colourable 4-cycle decompositions [PDF]

A cycle system of order $n$ is a decomposition of the edges of the complete graph $K_n$ into cycles of a fixed length. A cycle system is said to be $k$-colourable if we can assign $k$ colours to its vertices so that no cycle is monochromatic. If a cycle system is $k$-colourable but not $(k-1)$-colourable, it is called $k$-chromatic. A $k$-colourable cycle system is uniquely $k$-colourable if its colouring is unique up to the permutation of colour classes.

The study of colouring cycle systems has been explored in various settings. In particular, Horsley and Pike have examined the existence of $k$-chromatic $m$-cycle systems for any integers $m>2$ and $k>1$. While Forbes has investigated $3$-cycle systems with unique $3$-colourability, the existence of uniquely $k$-colourable $m$-cycle systems in general remains an open problem.

In this talk, we mainly focus on the construction of an infinite family of uniquely $2$-colourable $4$-cycle systems and also a uniquely $2$-colourable $4$-cycle decomposition of $K_n - I$, for infinitely many integers $n \geq 2$. These constructions contribute to the broader study of uniquely colourable cycle systems and open new directions for future research.

MATEJA SAJNA, University of Ottawa From Spouse-Avoiding to Spouse-Loving: Transforming Solutions to the Oberwolfach Problem [PDF]

The Oberwolfach problem $OP(F)$, for a 2-factor $F$ of $K_n$, asks whether there exists a 2-factorization of $K_n$ (if $n$ is odd) or $K_n-I$ (if $n$ is even) where each 2-factor is isomorphic to $F$. Here, $I$ denotes any 1-factor of $K_n$. For even $n$, the problem OP$(F)$ may also be denoted OP$^-(F)$, and has been nicknamed the spouse-avoiding variant. Similarly, the spouse-loving variant is denoted OP$^+(F)$ and asks for a 2-factorization of $K_n+I$ (the complete graph with the edges of a 1-factor $I$ duplicated, rather than deleted) in which each 2-factor is isomorphic to $F$. To date, many more infinite families of cases of OP and OP$^-$ have been solved than of OP$^+(F)$. In this talk, we show how certain solutions to OP$^-$ can be used to construct solutions to OP$^+(F)$; in particular, when the number of odd cycles in $F$ is not too large. Our technique of setups also allows us to completely solve the two-table OP$^+$; that is, OP$^+(F)$ where $F$ has exactly two components.

This is joint work with Maru\v{s}a Lek\v{s}e.

KIANOOSH SHOKRI, University of Ottawa A recursive construction of strength-$4$ covering arrays using an ovoid in $PG(3,q)$ [PDF]

A strength-$t$ covering array $\mathrm{CA}(N; t, k, v)$, is an $N \times k$ array over a $v$-set such that in any $t$-set of columns, each $t$-tuple occurs at least once in a row. We employ an ovoid (maximum-sized $k$-cap with $k = q^2 + 1$) in $PG(3,q)$ and its plane sections, called Möbius planes, to build new strength-$4$ covering arrays. For odd $q$, we identify three truncated Möbius planes such that for any choice of circles from each plane, their intersection size is at most three. From this, we construct a strength-$4$ covering array $\mathrm{CA}(3q^4 - 2; 4, \frac{q^2 + 1}{2}, q)$. By extending one of these truncated Möbius planes to a full one and applying a recursive construction, we further obtain a $\mathrm{CA}(3q^4 + (q - 2)(2q^3 - q); 4, q^2 + 1, q)$. For $q \geq 11$, these covering arrays improve the size of the best-known covering arrays with the same parameters.

This is joint work with Lucia Moura and Brett Stevens.

BRETT STEVENS, Carleton University Linear and non-linear 1-intersecting pencils of conics [PDF]

In a Desarguesian projective plane of odd order, the sets of conics through three points, tangent to three lines, and in which a fixed triangle is self-polar all form a bundle of conics; the circumscribed, inscribed and self-polar bundles respectively. The pencil of conics in the first and third that contain a fixed point are a linearly parameterized pencil. The corresponding pencil in the second is non-linearly parameterized. Let $\phi$ and $\chi$ be two non-degenerate conics which intersect at a single point and are not tangent there. The bundles described show they appear together in exactly one linear pencil and together in a non-linear pencil. The linear pencil can be embedded in two different bundles and the non-linear pencil in at least one. We prove that a similar result holds in projective planes of even order. We discuss the stabilizer subgroups of these pencils.

DOUG STINSON, University of Waterloo Block designs and protocols for local differential privacy [PDF]

There has been considerable recent interest in using block designs in the design of protocols for local differential privacy. The goal is to provide privacy for people reporting possibly sensitive data while still enabling an underlying probability distribution to be accurately estimated. The basic idea goes back to the "randomized response" method proposed by Warner in 1965, where each participant reports a correct yes-no response with some prespecified probability $\theta > 1/2$ and an incorrect response with probability $1 - \theta$. In this talk, I will review recent research by a variety of authors that employs BIBDs as a randomization mechanism when data having multiple possible values is being aggregated. This research is joint work with Maura Paterson.

AMY WIEBE, University of British Columbia Okanagan Counting transversals in group-based Latin squares [PDF]

Finding the exact number of transversals in a Latin square is a long-studied and difficult problem. Even in the simple setting of the Cayley table of the group $\mathbb{Z}_n$, estimating the number of transversals theoretically is a challenge. For groups of order $n\leq 16$ and cyclic groups of order $n\leq 21$, Shieh et. al [2000] enumerated transversals computationally. Further study by McKay, McLeod, and Wanless [2006] revealed many interesting patterns in these transversal counts. Notably, they ask whether the Cayley table of every $2$-group of order $n$ has a number of transversals divisible by $2^{n-1}$. In this talk, we introduce a ``contract-and-lift" method for approaching this question.

This is joint work with Jim Davis and Jonathan Jedwab.

haut de la page