Edge colourings and Latin-like squares: Combinatorial structures arising from alternating sign matrices
View/ Open
Date
2020-04-09Author
O'Brien, Cian
Metadata
Show full item recordUsage
This item's downloads: 108 (view details)
Abstract
An alternating sign matrix is a (0, 1, −1)-matrix in which the nonzero entries of each row and column alternate in sign, starting and ending with 1. An alternating signed bipartite graph (ASBG) is a bipartite graph G whose edges are coloured blue and red such that there is some ordering on the vertices of G for which the edges incident with each vertex of G alternate in colour, starting and ending with blue. We define a difference-1 colouring to be a 2-edge colouring of a graph such that each vertex is incident with one more blue edge than red. We call this colouring configurable if the resulting graph is an ASBG. This thesis investigates ASBGs by identifying a full set of necessary and sufficient conditions for a graph to have a difference-1 colouring, and necessary conditions for configurability.
The relationship between distinct difference-1 colourings of a particular graph is characterised, and classes of graphs for which all difference-1 colourings are configurable are identified. One result of this research extends Hall’s Matching Theorem by describing a necessary and sufficient condition for the existence of a subgraph H of a bipartite graph in which each vertex v of H has some prescribed degree r(v). The more general idea of a difference-k colouring is also explored.
The concept of a Latin square was generalised by Brualdi and Dahl in 2018 by replacing permutation matrices in the decomposition of a Latin square with an alternating sign hypermatrix (ASHM). The resulting object is an alternating sign hypermatrix Latin-like square (ASHL). This thesis addresses some problems posed in Brualdi and Dahl’s paper. The relationship between ASHMs with the same corresponding ASHL is characterised, and a construction is given for an n×n ASHL with the same entry occurring ⌊(n^2+4n−19)/2⌋ times. This improves on the previous best construction, which achieved the same entry occuring 2n times.