Date:
Mon, 14/12/201511:00-13:00
Location:
B221 Rothberg (CS and Engineering building)
Speaker: Eli Shamir, HUJI
Title :Completing partial Latin Square[LS] using 2-sided Hall marriage theorem
Abstract:
Evans conjectured in 1960 that nxn partial LS with n-1 dictated entries
can be completed. Smetaniuk gave an inductive, complicated proof in 1981 -
it is reproduced in the "Proofs from the Book".
My proof is direct-- filling row after row using a recent 2-sided extension of Hall
marriage conditions - which will be presented.
It gives all completions and also a generalized completion claim:
Partial nxn LS with y filled rows and n-2y -1 dictated entries in the remaining rows
can be completed to a full Latin square.
The square can also be filled by diagonals, each containing a fixed element a1 a2...etc.
This has some advantages.
Title :Completing partial Latin Square[LS] using 2-sided Hall marriage theorem
Abstract:
Evans conjectured in 1960 that nxn partial LS with n-1 dictated entries
can be completed. Smetaniuk gave an inductive, complicated proof in 1981 -
it is reproduced in the "Proofs from the Book".
My proof is direct-- filling row after row using a recent 2-sided extension of Hall
marriage conditions - which will be presented.
It gives all completions and also a generalized completion claim:
Partial nxn LS with y filled rows and n-2y -1 dictated entries in the remaining rows
can be completed to a full Latin square.
The square can also be filled by diagonals, each containing a fixed element a1 a2...etc.
This has some advantages.