Improvisations on the Hall marriage theorem: Completing Latin squares and Sudokus
Seminar
Speaker
Prof. Eli Shamir, Hebrew University, Jerusalem
Date
06/03/2016 - 13:00 - 12:00Add to Calendar
2016-03-06 12:00:00
2016-03-06 13:00:00
Improvisations on the Hall marriage theorem: Completing Latin squares and Sudokus
The key concept of our discussion is that of a perfect matching (PM) in a bipartite graph.
The expansion condition in Hall's marriage theorem can be extended to an unbiased 2-sided one.
This enables an alternative (and simpler) proof of Evans' (proven) Conjecture:
A partial nxn Latin square with n-1 dictated entries admits a completion to a full Latin square.
PMs are used to successively fill the square by rows, columns or diagonals. Latin square tables correspond to quasi-groups; the ones corresponding to groups are only a tiny fraction of them, as n grows. However, for Sudoku tables of order mnxmn, the completion (say by diagonals) usually fails, even if there are no dictated entries, unless they are conjugates of a twisted product of two groups, of orders n and m.
seminar room
אוניברסיטת בר-אילן - Department of Mathematics
mathoffice@math.biu.ac.il
Asia/Jerusalem
public
Place
seminar room
Abstract
The key concept of our discussion is that of a perfect matching (PM) in a bipartite graph.
The expansion condition in Hall's marriage theorem can be extended to an unbiased 2-sided one.
This enables an alternative (and simpler) proof of Evans' (proven) Conjecture:
A partial nxn Latin square with n-1 dictated entries admits a completion to a full Latin square.
PMs are used to successively fill the square by rows, columns or diagonals. Latin square tables correspond to quasi-groups; the ones corresponding to groups are only a tiny fraction of them, as n grows. However, for Sudoku tables of order mnxmn, the completion (say by diagonals) usually fails, even if there are no dictated entries, unless they are conjugates of a twisted product of two groups, of orders n and m.
The expansion condition in Hall's marriage theorem can be extended to an unbiased 2-sided one.
This enables an alternative (and simpler) proof of Evans' (proven) Conjecture:
A partial nxn Latin square with n-1 dictated entries admits a completion to a full Latin square.
PMs are used to successively fill the square by rows, columns or diagonals. Latin square tables correspond to quasi-groups; the ones corresponding to groups are only a tiny fraction of them, as n grows. However, for Sudoku tables of order mnxmn, the completion (say by diagonals) usually fails, even if there are no dictated entries, unless they are conjugates of a twisted product of two groups, of orders n and m.
Last Updated Date : 01/03/2016
