IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Amalgamations and Hamilton Decompositions and symmetric Sudoku squares

  • April 19, 2016
  • 4:30 p.m.
  • LeConte 312

Abstract

In this talk, we will explore the use of amalgamations in the construction of graph decompositions, most often looking for hamilton cycle decompositions. This method uses graph homomorphisms to envision an "outline" of the structure of interest, then attempts to disentangle the merging of new vertices created by the homomorphism in such an outline structure. As will be shown, this method has proved to be very effective, for example, in the studying the embedding of edge-colorings of graphs into hamilton decompositions, and the existence of latin squares with holes that satisfy some fairness properties. In particular, fair holey 1-factorizations give rise to symmetric versions of Sudoku squares. The talk is full of pictures with few technical details, so is suitable for a wide audience

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC