From H-decompositions to transitive path decompositions

Tuesday, 17-Sep-2024 

Abstract

Let $\Gamma$ and $H$ be graphs. An $H$-decomposition of a graph $\Gamma$  is a partition of its edge set into subgraphs isomorphic to $H$. A transitive decomposition is a special kind of $H$-decomposition that is highly symmetrical in the sense that the subgraphs (copies of $H$) are preserved and transitively permuted by a group of automorphisms of  $\Gamma$. In this talk, I will explore $H$-decompositions in general, providing historical context for these decompositions. Additionally, I will delve into transitive $H$-decompositions and present our recent results on transitive path decompositions of the Cartesian product $K_n \Box K_n$  when $n$ is an odd prime. Part of the talk is joint work with Alice Devillers, UWA. Based on https://arxiv.org/abs/2308.07684. No prior knowledge is required.