Réunion d'été du 75e+1 anniversaire de la SMC
Ottawa, 7 - 11 juin 2021
- AMIN BAHMANIAN, Illinois State University
Embedding Connected Factorizations [PDF]
-
An $(r_1,\dots,r_q)$-factorization of the complete $\lambda$-fold $h$-uniform $m$-vertex hypergraph $\lambda K_m^h$ is a partition of the edges of $\lambda K_m^h$ into $F_1,\dots, F_q$ such that each color class $F_i$ is $r_i$-regular and spanning. We show that for $n\geq hm$, the obvious necessary conditions that ensure that an $(r_1,\dots,r_q)$-factorization of $\lambda K_m^h$ can be extended to a connected $(s_1,\dots,s_k)$-factorization of $\lambda K_n^h$ are also sufficient. This is joint work with Anna Johnsen (Illinois State) and Stefan Napirata (Universit\" at Ulm).
- MARCO BURATTI, Università di Perugia
Tales from cycle decompositions [PDF]
-
I would like to give a roundup of unpublished results, problems, conjectures, and autobiographic stories concerning cycle decompositions.
- NICK CAVENAGH, University of Waikato
Heffter arrays and biembeddings of cycle systems [PDF]
-
In the last 20 years biembedding pairs of designs
and cycle systems onto surfaces has been a muchresearched topic (see the 2007 survey “Designs and Topology” by Grannell and Griggs). In particular, in
a posthumous work (2015), Archdeacon showed that
biembeddings of cycle systems may be obtained via
Heffter arrays. Formally, a Heffter array $H(m,n;s,t)$
is an $m\times n$ array of integers such that:
(a) each row contains $s$ filled cells and each
column contains $t$ filled cells;
(b) the elements in every row and column sum
to $0$ in ${\mathbb Z}_{2ms+1}$; and
(c) for each integer $1 \leq x \leq ms$, either $x$ or $-x$
appears in the array.
If we can order the entries of each row and column
satisyfing two properties (compatible and simple), a
Heffter array yields an embedding of two cycle decompositions of the complete graph $K_{2ms+1}$ onto an
orientable surface. Such an embedding is face 2-colourable, where the faces of one colour give a decomposition into $s$-cycles and the faces of the other
colour gives a decomposition into $t$-cycles. Thus as a
corollary the two graph decompositions are orthogonal; that is, any two cycles share at most one edge.
Moreover, the action of addition in ${\mathbb Z}_{2ms+1}$ gives an
automorphism of the embedding. We give more detail about the above and present a new result: the existence of Heffter arrays $H(n,n;s,s)$ with compatible
and simple orderings whenever $s \equiv 3$ (mod 4) and $n\equiv 1$ (mod 4).
- PETER DANZIGER, Ryerson universtiy
The Mini-Symposium Problem [PDF]
-
Joint work with E. Mendelsohn, B. Stevens, T. Traetta.
The Oberwolfach problem was originally stated as a seating problem:
Given $v$ attendees at a conference with $t$ circular tables each of which {seats $a_i$} people $\left({\sum_{i=1}^t a_i = v}\right)$. Find a seating arrangement so that every person sits next to each other person around a table exactly once over the $r$ days of the conference.
The Oberwolfach problem thus asks for a decomposition of $K_v$ ($K_v-I$ when $v$ is even) into 2-factors consisting of cycles with lengths $a_1,\ldots, a_t$.
In this talk we introduce the related mini-symposium problem, which asks for solutions to the Oberwolfach problem on $v$ points which contains a subsystem on $m$ points. In the seating context above, the larger conference contains a mini-symposium of $m$ participants, and we also require these $m$ participants to be seated together for $\left\lfloor\frac{m-1}{2}\right\rfloor$ of the days.
We obtain a complete solution when the cycle sizes are as large as possible, $m$ and $v-m$. In addition, we provide extensive results in the case where all cycle lengths are equal, of size $k$ say, completely solving all cases when $m\mid v$, except possibly when $k$ is odd and $v$ is even. In particular, we completely solve the case when all cycles are of length $m$ ($k=m$).
- 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$.
- PETER DUKES, University of Victoria
Local balance in graph decompositions [PDF]
-
In a balanced graph decomposition, every vertex of the host graph appears in the same number of blocks. We propose the use of coloured loops as a framework for unifying various related local conditions in graph decompositions, including degree-balanced decompositions and equitable block colourings. In the basic case where a single graph with coloured loops is used as a block, an existence theory for such decompositions follows as a straightforward generalization of previous work on balanced graph decompositions. This talk is based on joint work with Flora C. Bowditch.
- SARA HERKE, The University of Queensland
Hamilton path decompositions of complete multipartite graphs [PDF]
-
If a graph with $n$ vertices and $m$ edges can be decomposed into edge-disjoint Hamilton paths, then $t=\frac{m}{n-1}$ is an integer, where $t$ is the number of Hamilton paths, and the maximum degree is at most $2t$, because each Hamilton path has maximum degree 2. We give an overview of our proof that, for complete multipartite graphs, these conditions are also sufficient. This talk is based on joint work with Darryn Bryant and Hao Chuien Hang.
- MARIE ROSE JERADE, University of Ottawa
Honeymoon Oberwolfach Problem: Small Cases [PDF]
-
You are attending a conference where attendees consist of n couples. Couples must be seated next to each other every day of the conference, but next to every other person exactly once. At our disposal, we have $t$ round tables that accommodate $m_1, m_2, ..., m_t$ attendees, respectively, such that $m_1+m_2+...+m_t=2n$ and each $m_i >2$. This problem, nicknamed the Honeymoon Oberwolfach Problem, was introduced in [D. Lepine, M. \v{S}ajna, On the Honeymoon Oberwolfach Problem, J. of Combin. Des. {\bf 27} (2019), 420—447]. The authors showed that the problem has a solution for many general cases. Most important are the instances when all table sizes are the same, as well as for all $n \le 9$.
\newline
In this talk, we present our computer-aided techniques based on the above-mentioned paper that allowed us to extend the latter result to all $n \le 20$.
This is joint work with my research supervisor, Mateja \v{S}ajna.
- HEATHER JORDON, American Mathematical Society
Directed Cycle Systems via Signed Langford Sequences [PDF]
-
For positive integers $d$ and $t$, a Langford sequence of order $t$ and defect $d$ is a sequence
${\mathcal L}_d^t = (s_{1}, \dots , s_{2t})$ of length $2t$ that satisfies
(i) for every $k \in \{d,d+1,\ldots, t+d-1\}$, there are exactly two elements $s_i, s_j \in {\mathcal L}_d^t$ such that $s_i = s_j = k$ and
(ii) if $s_i = s_j = k$ with $i<j$, then $j-i=k$. Note that (ii) could be written as $j - i-k=0$ or $i+k-j = 0$. Hence, one generalization of a Langford sequence is as follows.
For positive integers $d$ and $t$, a {\it signed} Langford sequence of order $t$ and defect $d$ is a sequence
$\pm {\mathcal L}_d^t = (s_{-2t}, s_{-2t+1}, \dots , s_{-1}, \ast, s_{1}, \dots , s_{2t})$ of length $4t+1$ that satisfies
(i) for every $k \in \pm\{d, d+1, \ldots t+d-1\}$, there are exactly two elements $s_i, s_j \in \pm {\mathcal L}_d^t$ such that $s_i = s_j = k$ and
(ii) if $s_i = s_j = k$ with $i<0 < j$, then $i+j+k=0$.
In this talk, we give necessary and sufficient conditions for the existence of a signed Langford sequence of order $t$ and defect $d$ for all positive integers $d$. We will then use these sequences to find cyclic decompositions of circulant digraphs into directed $m$-cycles for $m \ge 3$. In particular, we find a cyclic $m$-cycle decomposition of the complete symmetric digraph $K^\ast_{2m+1}$ for all $m \ge 3$.
- MELISSA KERANEN, Michigan Technological University
Decomposing Graphs into Cycles [PDF]
-
A cycle decomposition is a partitioning of a graph's edges into cycles. A decomposition of the complete graph $K_{v}$ into 2-factors where each 2-factor consists entirely of $m$-cycles is called a $C_m$-factorization. The Hamilton-Waterloo Problem, HWP$(v;m,n;\alpha,\beta)$ asks for a decomposition of $K_v$ or $K_v-I$ into $\alpha$ $C_m$ factors and $\beta$ $C_n$-factors, where $3 \leq m \leq n$. In this presentation, I will discuss a technique that can be applied to solve some of the difficult cases in which $\alpha=1$ or $\beta=1$.
- FRANCESCA MEROLA, Roma Tre University
Equitably 2-colourable cycle systems [PDF]
-
An $\ell$-cycle decomposition of a graph $G$ is said to be equitably $c$-colourable if there is a $c$-vertex-colouring of $G$ such that each colour is represented (approximately) an equal number of times on each cycle: more precisely, we ask that in each cycle $C$ of the decomposition, each colour appears on $\lfloor \ell/c \rfloor$ or $\lceil \ell/c \rceil$ of the vertices of $C$.
In this talk, we consider the case $c=2$ and present some new results on
the existence of $2$-colourable even $\ell$-cycle systems of the cocktail party graph $K_v-I$.
In particular, we determine a complete existence result for equitably $2$-colourable $\ell$-cycle decompositions of $K_v-I$, $\ell$ even, in the cases that $v\equiv 0,2 \pmod{\ell},$ or $\ell$ is a power of 2, or $\ell\in \{2q, 4q\}$ for $q$ an odd prime power, or $\ell \leq 30$.
We will also discuss some work in progress on analogous problems for cycles of odd length.
(Joint work with Andrea Burgess)
- ANITA PASOTTI, Università degli Studi di Brescia
A reduction of the spectrum problem for sun systems [PDF]
-
A $k$-cycle with a pendant edge attached to each vertex is called a $k$-sun.
When we approached the existence problem for $k$-sun systems of order $v$,
complete solutions were known only for $k=3,4,5,6,8,10,14$ and for $k=2^t$.
Here, we reduce this problem to the orders $v$ in the range $2k< v < 6k$ satisfying the obvious necessary conditions.
Thanks to this result, we provide a complete solution whenever $k$ is an odd prime, and some partial results
whenever $k$ is twice a prime.
This talk is based on joint work with Marco Buratti and Tommaso Traetta.
- ADRIAN PASTINE, Universidad Nacional de San Luis - IMASL (CONICET)
On the Hamilton-Waterloo problem with cycle lengths of distinct parities [PDF]
-
The Hamilton-Waterloo problem asks for a decomposition of the complete graph into $r$ copies of a 2-factor $F_1$ and $s$ copies of a 2-factor $F_2$ such that $r+s=\left\lfloor \frac{v-1}{2}\right\rfloor$. If $F_1$ consists of $m$-cycles and $F_2$ consists of $n$ cycles, then we call such a decomposition a $(m,n)-HWP(v;r,s)$. The goal is to find a decomposition for every possible pair $(r,s)$. This problem has been studied in great depth in the cases when $m$ and $n$ have the same parity and $1\not\in\{r,s\}$. In this work, we use dihedral groups to obtain decompositions of the form $(m,n)-HWP(v;r,s)$ when both $m$ and $n$ have different parities. We also obtain decompositions when $m$ and $n$ have the same parity and $1\in \{r,s\}$. This talk is based on joint work with Andrea Burgess, Peter Danziger and Tommaso Traetta.
- DAVID PIKE, Memorial University of Newfoundland
Perfect 1-Factorisations [PDF]
-
A matching in a graph $G$ is a subset $M \subseteq E(G)$ of the edge set of $G$ such that no two edges of $M$ share a vertex. A 1-factor of a
graph $G$ is a matching $F$ in which every vertex of $G$ is in one of the edges of $F$. If $G$ is a $\Delta$-regular graph of even order then we
can ask whether $G$ admits a 1-factorisation, namely a partition of its edge set into $\Delta$ 1-factors.
Suppose that $F_1, F_2, \ldots, F_\Delta$ are the 1-factors of a 1-factorisation $\cal F$ of a $\Delta$-regular graph $G$. If, for each $1 \leq i < j \leq \Delta$, the union $F_i \cup F_j$ is the edge set of a Hamilton cycle in $G$, then we say that $\cal F$ is a perfect 1-factorisation of $G$. We will discuss some of the history and properties of 1-factorisations, including the recent discovery of a perfect 1-factorisation of $K_{56}$.
- DOUG STINSON, University of Waterloo
On Progressive Dinner Parties and Related Combinatorial Structures [PDF]
-
Julian Regan asked if it possible to design a progressive dinner party that involves a number of couples, having each course of a three-course meal at a different person's house, with three couples at each course, every couple hosting once and no two couples meeting more than once. This problem can be generalized to a $k$ course meal with $k$ couples at each course. The number of couples, say $v$, must be divisible by $k$. We can solve this problem for almost permissible values of $v$ when $k \leq 13$. In this talk, I will discuss solution techniques, as well as connections with resolvable symmetric configurations and resolvable Golomb rulers. Part of this talk is based on joint work with Marco Buratti.
- TOMMASO TRAETTA, Università di Brescia
Highly symmetric Kirkman triple systems [PDF]
-
Kirkman triple systems (KTSs) are among the most popular combinatorial designs and their existence has been settled a long time ago. Yet,
in comparison with Steiner triple systems, little is known about their
automorphism groups. In particular, there is no known congruence class representing the orders of
a KTS with a number of automorphisms at least close to the number of points.
We fill this gap by proving that whenever $v \equiv 39$ (mod 72), or $v \equiv 4^e48 + 3$ (mod $4^e96$) and $e \geq 0$,
there exists a KTS on $v$ points having at least $v-3$ automorphisms.
To obtain these results we introduced new types of difference families and difference matrices which will be discussed in this talk.
This is joint work with S. Bonvicini, M. Buratti, M. Garonzi, and G. Rinaldi.