Réunion d'hiver SMC 2024

Vancouver/Richmond, 29 novembre - 2 decembre 2024

Conceptions combinatoires
Org: Peter Danziger (Toronto Metropolitan University) et Peter Dukes (University of Victoria)
[PDF]

MASOOMEH AKBARI, University of Ottawa The Generalized Honeymoon Oberwolfach Problem with one large table of size 2m [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 each night and next to each other participant exactly once. HOP has been studied by Jerade, Lepine, and Šajna, with some significant cases already solved.

We generalize HOP by allowing tables of size two, rather than a minimum size of four as previously defined in HOP. Thus, 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$, with the requirement that $2n = 2s + 2m_1 + 2m_2 + \dots + 2m_t$ and $m_i\geq 2$. Our current goal is to prove that the necessary condition for the HOP with $s$ tables of size 2 and one large table of size $2m$ to have a solution is sufficient. In this talk, we will present a general approach to this problem and discuss the progress we have made so far.

ANDREA BURGESS, University of New Brunswick Saint John Colourings of Kirkman triple systems [PDF]

A $\delta$-colouring of a Steiner triple system $S$ is an assignment of $\delta$ colours to its points so that no triple has all its points of the same colour. The chromatic number of $S$ is the minimum number of colours $\delta$ so that $S$ admits a $\delta$-colouring. While much is known regarding colourings of Steiner triple systems in general (in particular, there exists a $\delta$-chromatic STS$(v)$ for every sufficiently large admissible order $v$), little is known about colouring properties of resolvable triple systems.

A Kirkman triple system consists of a resolvable Steiner triple system together with a partition of its blocks into parallel classes. We show that for every integer $\delta \geq 3$, there exist infinitely many $\delta$-chromatic Kirkman triple systems. Moreover, in the case $\delta=3$, we give a complete existence result for $3$-chromatic Kirkman triple systems.

This is joint work with Nicholas Cavenagh, Peter Danziger and David Pike.

JONATHAN JEDWAB, Simon Fraser University Additive triples in groups of odd prime order [PDF]

Let $p$ be an odd prime. For nontrivial proper subsets $A,B$ of~$\mathbb{Z}_p$ of size $s,t$, respectively, we count the number $r(A,B,B)$ of \emph{additive triples}, namely elements of the form $(a, b, a+b)$ in $A \times B \times B$. For given $s,t$, what is the spectrum of possible values for $r(A,B,B)$?

In the special case $A=B$, the additive triple is called a \emph{Schur triple}. It is known that the Cauchy-Davenport Theorem gives bounds on the number $r(A,A,A)$ of Schur triples, and that the lower and upper bound can each be attained by a set $A$ that is an interval of $s$ consecutive elements of $\mathbb{Z}_p$. However, it is known that there are values of $p,s$ for which not every value from the lower bound to the upper bound is attainable.

In the case where $A,B$ can be distinct, we use Pollard's generalization of the Cauchy-Davenport Theorem to derive bounds on the possible values of the number $r(A,B,B)$ of additive triples. In contrast to the case $A=B$, we show that every value from the lower bound to the upper bound is attainable; and it is sufficient to take $B$ to be an interval of $t$ consecutive elements of~$\mathbb{Z}_p$.

This is joint work with Sophie Huczynska and Laura Johnson.

HADI KHARAGHANI, University of Lethbridge Hadamard matrices related to orthogonal arrays [PDF]

Let $n \equiv 3 \pmod 4$ be a positive integer. The following statements are equivalent:

(i) There exists an Orthogonal Array OA$(n+1, n)$ and an $n \times (n+1)$ partial Hadamard matrix.

(ii) There exists a balancedly multi-splittable $n^2 \times n(n+1)$ partial Hadamard matrix.

Additionally, the concept of balancedly multi-splittable Balanced Incomplete Block Designs will be introduced and discussed.

A joint work with Sho Suda and Yash Khobragade.

ALICE LACAZE-MASMONTEIL, University of Regina Completing the solution of the directed Oberwolfach problem with two tables [PDF]

A $(\vec{C}_{m_1},\vec{C}_{m_2})$-factor of a directed graph $G$ is a spanning subdigraph of $G$ comprised of two disjoint directed cycles of lengths $m_1$ and $m_2$. In this talk, we show that the complete symmetric digraph $K^*_n$ can be decomposed into $(\vec{C}_{m_1},\vec{C}_{m_2})$-factors when $m_1+m_2=n$, $m_1 \in \{4,6\}$, and $m_2\geqslant 8$ is even. In conjunction with recent results of Kadri and Šajna (2024+), this result completes the solution of the two-table case of the directed Oberwolfach problem. This work was done in collaboration with Daniel Horsley.

ESTHER LAMKEN, Independent Scholar Duplicated Steiner triple systems with self-orthogonal near resolutions [PDF]

A Steiner triple system, STS$(v)$, is a family of $3$-subsets (blocks) of a set of $v$ elements such that any two elements occur together in precisely one block. A collection of triples consisting of two copies of each block of an STS is called a duplicated Steiner triple system, DSTS. A resolvable (or near resolvable) DSTS is called self-orthogonal if every pair of distinct classes in the resolution has at most one block in common. We provide several methods to construct self-orthogonal near resolvable DSTS and almost completely settle the existence of such designs. At present, there is one remaining possible exception for $v$. This addresses a recent question of Bryant, Davies and Neubecker. This is joint work with Peter Dukes.

SHUXING LI, University of Delaware Intersection Distributions and Related Steiner Systems [PDF]

Given a polynomial $f$ over finite field $\mathbb{F}_q$, its intersection distribution concerns the collective behaviour of a series of polynomials $\{f(x)+cx | c \in \mathbb{F}_q \}$. We outline the ideas determining the intersection distributions of degree three and degree four polynomials, from which Steiner systems $S(2,3,3^n)$ and $S(2,4,2^n)$ can be derived.

TRENT MARBACH, Toronto Metropolitan University From Localizing Designs to Designing Detecting Hypernetworks [PDF]

Designs have been found to provide important extremal examples for pursuit-evasion graph parameters. We begin by describing our work in using designs to analyze the localization graph parameter, which is a parameter that asks for the number of distant-detecting agents that are required to locate a moving target on a graph. This work led into looking at related graphs, and we will show how studying the problem of detecting multiple signals within hypergraphs was used in this endeavour. This detectability problem is interesting in its own right and we will show an application we found of this theory, which in a pleasing turn of event has its optimal objects being well-known designs.

OPEN PROBLEM DISCUSSION

PRANGYA PARIDA, University of Ottawa Cover-free families on graphs [PDF]

A family of subsets of $[t]$ is called a $ d$-cover-free family ($d$-CFF) if no subset is contained in the union of any $d$ others. We denote by $t(d, n)$ the minimum $t$ for which there exists a $d$-CFF of $[t]$ with $n$ subsets. $t(1, n)$ is determined using Sperner's Theorem. For $d \geq 2$, we rely on bounds for $t(d, n)$. Using the probabilistic approach, Erdös, Frankl, and Füredi proved $3.106 \log(n) < t(2, n) < 5.512 \log(n)$. Porat and Rothschild provided a deterministic polynomial-time algorithm to construct $d$-CFFs achieving $t = O(d^2 \log(n))$. Some upper bounds of $t(2, n)$(in some cases exact bounds) for small $n$ were provided by Li, van Rees, and Wei.

We extend the definition of $2$-CFF to include a graph($G$), called $\overline{G}$-CFF, where the edges of $G$ specify the pair of subsets whose union must not cover any other subset. We denote by $t(G)$ as the minimum $t$ for which there exists a $\overline{G}$-CFF. Thus, $t(K_n) = t(2, n)$. We will discuss some classical results on CFFs, along with constructions of $\overline{G}$-CFFs. We prove that for a graph $G$ with $n$ vertices, $t(1, n) \leq t(G) \leq t(2, n)$ and for an infinite family of star graphs with $n$ vertices, $t(S_n) = t(1, n)$. We also provide constructions for $\overline{P_n}$-CFF and $\overline{C_n}$-CFF using a mixed-radix Gray code. This yields an upper bound for $t(P_n)$ and $t(C_n)$ that is smaller than the lower bound of $t(2, n)$ mentioned above.

Joint work with Lucia Moura.

DAVID PIKE, Memorial University of Newfoundland 2-Block-Intersection Graphs of Twofold Triple Systems [PDF]

A twofold triple system (TTS) is a combinatorial design for which every block has exactly three points, and each pair of points occurs together in precisely two blocks. The 2-block-intersection graph (2-BIG) of a TTS is the graph having the blocks of the TTS as its vertices, and vertices are adjacent if their corresponding blocks have exactly two elements in common. We discuss several properties of the 2-BIGs of TTSs, including recent observations about planarity and vertex-transitivity.

Joint work with Benjamin Stanley.

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

A covering array, denoted by CA$(N; t, k, v)$, is an $N \times k$ array over an alphabet with $v$ symbols with the property that for any $t$-set of column indices $ \lbrace c_1, \ldots, c_t \rbrace$, each $t$-tuple of the alphabet occurs at least once as a row of the sub-array indexed by $c_1, \ldots, c_t$. Here, $N$ is the size, and $t$ is the strength of the covering array.

Raaphorst, Moura, and Stevens (2014) give a construction for a CA$(2q^3-1; 3, q^2 + q + 1, q)$, for any prime power $q$. This is obtained by two projective planes $PG(2,q)$ such that any three collinear points in one is mapped to three non-collinear points in the other.

A $k$-cap of $PG(m-1, q)$ is a set of $k$ points no three of which are collinear. In $PG(3,q)$, an ovoid is a $k$-cap with maximum size of $k$. In a paper by Tzanakis, Moura, Panario, and Stevens (2016), a CA$(511; 4, 17, 4)$ is constructed, which was formed by two ovoids in $PG(3, 4)$ such that any four coplanar points in one is mapped to four non-coplanar points in the other.

In this talk, we give a construction for strength-$4$ covering arrays using three $k$-caps in $PG(3,q)$, which has been verified for all odd prime powers $q$ such that $3 \leq q \leq 101$. We conjecture that our construction is valid for any odd prime power $q$. This is joint work with Lucia Moura.

DOUG STINSON, University of Waterloo Recent results on near-factorizations of 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\}.$ We say that $(A,B)$ is a near-factorization of $G$ if $|A| \times |B| = |G|-1$ and $G \setminus \{e\} =AB$. We prove some new structural properties of near-factorizations in certain classes of groups. We also show that a "mate" $B$ of a set $A$ in a near-factorization $(A,B)$ of a finite group $G$ is unique, and we describe how to compute the mate $B$ very efficiently using an explicit formula for $B$. Then we examine all the noncyclic abelian groups of order less than 200 in a search for a possible nontrivial near-factorization. All of these possibilities are ruled out, either by theoretical criteria or by exhaustive computer searches. (In contrast, near-factorizations in cyclic or dihedral groups are known to exist by previous results.)

haut de la page