Transversals in Latin squares and rainbow matchings

L'obiettivo di questa tesi è quello di discutere e analizzare la struttura e le proprietà dei quadrati latini e dei quadrati latini mutualmente ortogonali. Si discuterà dell'esistenza di un quadrato latino e della possibilità di completare un quadrato latino parziale. Verrà discussa brevemente la relazione che intercorre tra i quadrati latini e la teoria dei gruppi. Nello specifico si evidenzierà la connessione tra i quadrati latini e le tavole di Cayley dei gruppi. Si approfondirà il concetto di trasversale in un quadrato latino. In modo particolare si cercherà di fornire dei bound sulla grandezza di un trasversale parziale studiando la grandezza del rainbow matching ottenuto a partire dal quadrato latino dal quale si estrae il trasversale. Verrà discusso brevemente l'esempio più famoso di quadrato latino, il Sudoku. In particolare, si cercherà di enumerare i Sudoku e di discutere il problema del numero minimo di clue necessari per avere una soluzione univoca. Infine si dimostrerà che in un cammino con colorazione degli archi, sotto determinate condizioni sulla frequenza dei colori, esiste sempre un full rainbow matching