Réunion d'été SMC 2022
St. John's, 3 - 6 juin 2022
Théorie du design et décomposition des graphes
Org: Andrea Burgess (UNB) et David Pike (Memorial University)
[PDF]
Org: Andrea Burgess (UNB) et David Pike (Memorial University)
[PDF]
- AMANDA CHAFEE, Carleton University
Simulated Annealing on Single Change Covering Designs [PDF]
-
A single change covering design is a sequence of $b$ $k$-sets, called blocks, of a $V$-set in which exactly one element differs between consecutive blocks and every $s$-set of $V$ is in some block. Single change covering designs are useful when designing experiments where it is costly to change elements of the experiment between runs. \newline
We used a simulated annealing meta-heuristics search to find single change covering designs, experimenting with different neighbourhood selection methods. We will present efficacy and run times for these experiments.
- PETER DANZIGER, Toronto Metropolitan University
Tic-Tac-Toe on Designs [PDF]
-
The game of Tic-Tac-Toe is well known. In particular, in its classic version it is famous for neither player having a winning strategy.
While classically it is played on a $3\times 3$ grid, it is natural to consider the effect of playing the game on richer structures.
Playing the game of Tic-Tac-Toe on finite affine and projective planes has been previously studied and in this case the first player has a winning strategy for small orders, but the second player can usually force a draw.
We investigate playing Tic-Tac-Toe on Designs, particularly on BIBDs and Transversal Designs with small block size. We completely solve the case of triple systems, showing that a TS$(v,\lambda)$ is a first player win if and only if $v\geq 5$. Additionally we show that Transversal Designs with small block size are a first player win. Interestingly, we also show that in this case an obvious `score optimizing' strategy is not sufficient for the first player to win in every case.
- IREN DARIJANI, Memorial University of Newfoundland
Colourings of path systems [PDF]
-
A path system of order $n > 1$ is a partition of the edges of the complete graph $K_n$ into paths. A path system is said to be $k$-colourable if the vertex set of $K_n$ can be partitioned into $k$ sets called colour classes such that no path in the system is monochromatic. The system is $k$-chromatic if it is $k$-colourable but is not $(k-1)$-colourable. If every $k$-colouring of a path 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 see some results on $k$-colourings of path systems for all $k\geq 2$. We will also present some results on unique $2$-colourings of path systems. This is a joint work with David Pike.
- SHONDA DUECK, University of Winnipeg
Cyclic partitions of complete and almost complete uniform hypergraphs [PDF]
-
We consider cyclic partitions of the complete $k$-uniform hy\-per\-graph on a finite set $V$, minus a set of $s$ edges, $s\geq 0$. An $s$-almost $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$-subsets of $V$ minus a set of $s$ edges. Such a permutation $\theta$ is called an $s$-almost $(t,k)$-com\-ple\-ment\-ing permutation. The $s$-almost $t$-com\-ple\-ment\-ary $k$-hy\-per\-graphs are a natural generalization of the almost self-com\-ple\-ment\-ary graphs which were previously studied by Clapham, Kamble et al, and Wojda. We prove the existence of an $s$-almost $p$-com\-ple\-men\-tary $k$-hy\-per\-graph of order $n$, where $p$ is prime, $s = \prod_{i\geq 0}{{n_i}\choose {k_i}}$, and $n_i$ and $k_i$ are the entries in the base-$p$ representations of $n$ and $k$, respectively. This existence result yields a combinatorial proof of Lucas' classic 1878 theorem.
- ARAS ERZURUMLUOGLU, Trent University
Fairness and Symmetry in Graph Decompositions [PDF]
-
I plan on starting with an introduction of the technique of vertex amalgamations in graphs along with some results that pertain to various notions of fairness in decompositions of complete multipartite graphs. Then, I will review some results that I am familiar with about symmetry in graph decompositions. Finally, I will talk about how vertex amalgamations might be useful for obtaining decompositions of complete multipartite graphs with interesting symmetry properties. A work in progress.
- ALICE LACAZE-MASMONTEIL, University of Ottawa
Resolvable directed cycle decompositions of the complete symmetric digraph [PDF]
-
A $\vec{C}_m$-factorization (or resolvable $\vec{C}_m$-decomposition) of a digraph $G$ is a decomposition of $G$ into spanning subgraphs, each a disjoint union of directed cycles of length $m$. For positive integers $\alpha$ and $m$, it is conjectured that a $\vec{C}_m$-factorization of the complete symmetric digraph on $\alpha m$ vertices, denoted $K^*_{\alpha m}$, exists if and only if $(m, \alpha)\not\in \{(3,2), (4,1)\}$. This conjecture has been proven for $m\in \{3,4\}$ and for the case $m$ is even or $\alpha$ is odd. For $m\geqslant 5$ odd and $\alpha$ even, Burgess and Šajna have also shown that it suffices to find a $\vec{C}_m$-factorization of $K^*_{2m}$ to completely settle the conjecture. In this talk, we take a major step towards a resolution of this problem by showing that, if $m$ is odd and divisible by a prime congruent to 5 modulo 6, then $K^*_{2m}$ admits a $\vec{C}_m$-factorization. This is joint work with Mateja Šajna.
- TRENT MARBACH, Toronto Metropolitan University
Pursuit-Evasion Games on Latin Square Graphs [PDF]
-
Graphs based on designs have been found to be useful in the study of pursuit-evasion on graphs. We investigate various pursuit-evasion parameters on latin square graphs, including the cop number, metric dimension, and localization number. The cop number of latin square graphs is studied, and for $k$-MOLS$(n),$ bounds for the cop number are given. If $n>(k+1)^2,$ then the cop number is shown to be $k+2.$ Lower and upper bounds are provided for the metric dimension and localization number of latin square graphs. The metric dimension of back-circulant latin squares shows that the lower bound is close to tight. Recent results on covers and partial transversals of latin squares provide the upper bound of $n+O\left(\frac{\log{n}}{\log{\log{n}}}\right)$ on the localization number of a latin square graph of order $n.$
- ALYSSA SANKEY, University of New Brunswick
On strongly regular decompositions of block graphs of S($2,k,2k^2-k$) [PDF]
-
A strongly regular design is a point-block incidence structure in which strongly regular graphs are defined on both the point set $P$ and the block set $B$, and incidence satisfies certain regularity conditions. We investigate a sub-class of these with the property that a strongly regular graph $\Gamma$ with vertex set $P\cup B$ is obtained by taking adjacency to be the union of adjacency on points, adjacency on blocks, and both point-block and block-point incidence. A strongly regular decomposition is a strongly regular graph whose vertex set may be partitioned in this way, such that the induced subgraphs are strongly regular.
This talk will focus on a particular infinite family of parameters for strongly regular designs, and show that if $\Gamma$ is the block graph of the Steiner system
$S(2,k,2k^2-k)$, with $k$ congruent to $\pm2$ mod 6, these parameters are realized. When $k$ is a power of 2, the parameters of the block graphs coincide with those of the symplectic graphs. Examples are known for $k=4, 8, 16$; existence is unknown in general with the smallest unresolved cases $k=10$ and $k=14$.