Réunion d'été SMC 2023

Ottawa, 2 - 5 juin 2023


Théorie des plans et de la décomposition des graphes
Org: Andrea Burgess (University of New Brunswick), Peter Danziger (Toronto Metropolitan University) et Alice Lacaze-Masmonteil (University of Ottawa)

MASOOMEH AKBARI, University of Ottawa
On the Generalized Honeymoon Oberwolfach Problem  [PDF]

The Honeymoon Oberwolfach Problem (HOP) is one of the recent and interesting variations of the Oberwolfach Problem (OP). This problem was introduced by Sajna in 2019, and formulated as follows. We wish to make a seating arrangement for $2n$ participants consisting of $n$ newlywed couples in a room with $t$ round tables that, respectively, seat $2m_1,\ldots, 2m_t$ people so that all tables are full at each meal, that is, $2m_1+2m_2+\ldots+2m_t=2n$, and each participant sits next to their spouse every time and next to each other participant exactly once. In graph theory, a solution to HOP is equivalent to a decomposition of $K_{2n} +(2n-3)I$, the complete graph on $2n$ vertices plus $2n-3$ additional copies of a $1$-factor $I$, into $2$-factors, each consisting of disjoint $I$-alternating cycles of lengths $2m_1,\ldots, 2m_t$. A number of cases of HOP have already been solved by Lepine and Sajna; most notably, the case of uniform cycle lengths.

So far, HOP has been defined with the constraint that each table size is at least four. In this talk, I generalize the problem to allow for tables of size two. A solution to the generalized HOP with $s$ tables of size $2$ and $t$ round tables of sizes $2m_1, 2m_2, \ldots, 2m_t$ is equivalent to a decomposition of the multigraph $K_{2n} +(\gamma-1)I$, for an appropriate integer $\gamma$, into subgraphs consisting of disjoint $I$-alternating cycles of lengths $2m_1,2m_2,\ldots,2m_t$ and $s$ copies of $K_2$. I will present a general approach to this problem, and recent solutions to several cases.

MUHAMMAD TARIQ JAVED, Toronto Metropolitan University
Sequence Covering and Packing Arrays  [PDF]

A Sequence Covering Array (SeqCA) or a Sequence Packing Array (SeqPA) is a set $\mathcal{B}$ of $N$ $k$-sequences on $v$ events, where $2 \leq k \leq v$. In a SeqCA (SeqPA), every pair of events appears in at least (most) one of the sequences in $\mathcal{B}$. The number of sequences in a minimum (maximum) size SeqCA (SeqPA) is called the SeqCA (SeqPA) number, denoted by $k$-SeqCAN$(v)$ ($k$-SeqPAN$(v)$). In the literature, SeqCA (SeqPA) numbers are only known for small values of $k$, or for the case when $k=v$. For $N \in \{4,5,6,7,10,11\}$, we determined the set of pairs $\{(v,k): k$-SeqCAN$(v)=N \}$. For $N \in \{2,3,4,5\}$, we determined the set of pairs $\{(v,k): k$-SeqPAN$(v)=N \}$, and for $N \in \{7,8,9\}$ we determine the set $\{(v,k): k$-SeqPAN$(v) \leq N \}$. For $N \in \{3,4,5,6,7,8,9\}$, known bounds on SeqPA numbers were improved.

Resolution of the directed Oberwolfach problem with cycles of equal length  [PDF]

A $\vec{C}_m$-factor of a digraph is a spanning subdigraph comprised of disjoint directed cycles of length $m$ and a $\vec{C}_m$-factorization is a decomposition into $\vec{C}_m$-factors. It has been conjectured that $K^*_{\alpha m}$ admits a $\vec{C}_m$-factorization if and only if $(\alpha, m) \not \in \{(1,4), (1,6), (2, 3) \}$. This problem is known as the directed Oberwolfach problem with cycles of equal length. In this talk, we present a solution to the last outstanding case; that is, we show that $K^*_{2m}$ admits a $\vec{C}_m$-factorization for all odd $m\geqslant 11$.

LUCIA MOURA, University of Ottawa
Hypergraph-dependent Covering Arrays  [PDF]

In this talk, we discuss generalizations of cover-free families and covering arrays that use a hypergraph to specify coverage.

A $d$-CFF$(t,n)$ is a $t\times n$ array such that for each subset of $d+1$ columns, every possible weight-$1$ binary tuple occurs in at least one of the rows. CFFs are used in combinatorial group testing to determine up to $d$ defective items in a collection of $n$ items by pooling items to be tested together in $t$ tests; the defective items are deduced from the test results.

A covering array (CA) of size $N$, strength $t$, $k$ factors and alphabet size $v$ is an $N\times k$ array such that for each subset of $t$ columns, every possible $t$-tuple of the alphabet occurs in at least one of the rows. CAs give effective test suits for software testing giving a good coverage of the parameter space.

Both types of array require that ``coverage" must occur in every subset of columns of a fixed size. The number of rows/tests must be minimized and it grows as the logarithm of the number of columns. In the hypergraph-dependent versions of these problems, edges of a hypergraph specify in which columns ``coverage" is required. The hypergraph model for CAs has been studied since Meagher\&Stevens (2005). The hypergraph model for CFFs was introduced by Idalino and Moura (IWOCA2022), motivated by applications in pandemic screening, where fewer tests are needed by using knowledge about connected communities.

We will overview known results and future work on hypergraph-dependent covering arrays.

AMIN SAEIDI, University of Limpopo
Designs constructed from 2-transitive groups  [PDF]

In this talk, we will explore the Key-Moori Method, a powerful technique for constructing designs that are invariant under finite primitive groups, with a focus on 2-transitive groups. We will apply this method to several families of finite simple groups, as well as the affine group $AGL(n, q)$.

For an affine group $G$, we will demonstrate how the structure of the conjugacy classes of the general linear group $GL(n, q)$ can be used to obtain the parameters of the $G$-invariant designs constructed by this method, and we will explicitly compute the parameters for small values of $n$. We will also demonstrate how fixed-points of primitive groups can be used to find designs and obtain what we call "reduced designs" which enable us to determine the automorphism groups of the designs in many cases.

MATEJA SAJNA, University of Ottawa
On the directed Oberwolfach problem for complete symmetric equipartite digraphs  [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 $t_1, t_2,\ldots, t_k$ for several meals so that each participant sits next to every other participant at exactly one meal, assuming that $t_1+t_2+ \ldots +t_k=n$. 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 $t_1, t_2,\ldots, t_k$.

In this talk, we discuss the directed version for complete symmetric equipartite digraphs. Thus, we are interested in decomposing $K_{n[m]}^\ast$, the complete symmetric equipartite digraph with $n$ parts of size $m$, into spanning subdigraphs, each a disjoint union of $k$ directed cycles of lengths $t_1, t_2,\ldots, t_k$ (where $t_1+t_2+ \ldots +t_k=mn$). Such a decomposition models a seating arrangement of $mn$ participants, consisting of $n$ delegations of $m$ participants each, at $k$ tables of sizes $t_1, t_2,\ldots, t_k$ so that each participant sits to the right of each participant from a different delegation exactly once. Recent solutions to extensive cases of this problem for uniform cycle lengths will be presented.

This is joint work with Nevena Franceti\'{c}.

ALYSSA SANKEY, University of New Brunswick
A family of regular weights on the folded Johnson scheme J(2n,n)  [PDF]

The Odd graph is a distance-regular graph that generates the Johnson J(2m+1,m) association scheme. Its vertices are the $m$-subsets of a $(2m+1)$-set, and are adjacent if and only if disjoint. It is well known that the union of this graph and its distance 2 graph is isomorphic to a folded Johnson graph. In this talk we describe how the union of graphs extends to a fusion of the full association scheme. Using the fusion, we define a certain edge weight on the folded graph and obtain the scheme J(2m+2,m+1) as a double covering configuration of the folded graph.

This family of examples illustrates two concepts that we shall attempt to convince the audience are interesting: Firstly, an infinite family of regular weights with so-called minimal closure; secondly the explicit covering schemes derived from these weights that coincide with the well known double covers of folded distance-regular graphs.

If time permits, we will show that the Hamming scheme H(n-1,2) lends itself to a similar construction involving the folded $n$-cube.

BRETT STEVENS, Carleton University
Non-linearly parameterized pencils of conics in even projective planes  [PDF]

In a Desarguesian projective plane, the set of conics through three or four points form a linearly parameterized net of pencil of conics, respectively. In an odd plane, the set of conics tangent to three lines forms a dual net which might not be linearly parameterized. The subset of these through a fixed point is a non-linearly parameterized pencil. In even planes all the tangent lines of a conic intersect in a common point, the nucleus, so set of conics tangent to three lines is equivalent to the set of conics which share a common nucleus and the same construction is not possible. We show that there does exists non-linearly parameterized pencils of conics in even planes and explore their structure and combinatorics. We demonstrate a connection between these pencils and the construction of mutually orthogoval affine planes and covering arrays.

TOMMASO TRAETTA, Università degli Studi di Brescia
Generalized Heffter arrays and near alternating sign matrices  [PDF]

In this talk, we present a generalization of Heffter arrays [1] by allowing that:

$\bullet$ the number of nonzero entries in each row (resp. column) of the array be not constant, and

$\bullet$ the entries of the array, in absolute value, belong to an arbitrarily chosen subset $S$ of a group $G$, not necessarily abelian.

We show that generalized Heffter arrays (GHA) can be used to construct orthogonal path or cycle decompositions and biembeddings of Cayley graphs onto orientable surfaces. The structural properties of the latter depend on the sum of the entries in each row and column of the GHA (with respect to a given ordering). Preferable are those satisfying the further strong property of being simple: for each row and each column, the partial sums (of the non-zero entries) are pairwise distinct, and only the total sum is possibly zero. We show that simple GHAs over cyclic groups can be easily built by means of near alternating sign matrices [2]. Further results and future works will be discussed.

This is joint work with Lorenzo Mella. \newline

References \newline [1] L. Mella and T. Traetta. Constructing generalized Heffter arrays via near alternating sign matrices, submitted. \newline [2] R.A. Brualdi and H.K. Kim. A Generalization of Alternating Sign Matrices, J. Combin. Des. 23 (2015), 204-215.

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