On Latin Squares and the Facial Structure of Related Polytopes

Euler, Reinhardt and Burkard, Rainer E. and Grommes, R. (1986) On Latin Squares and the Facial Structure of Related Polytopes.
Published in: Discrete mathematics Vol. 62 (2). pp. 155-181.


By identifying all latin squares of order n with certain n²-element subsets of an n³-element ground set En a clutter Bn is obtained, which induces an independence system (En,In) in a natural way. Starting from Ryser's conditions for the completion of latin rectangles, cf. L. Mirsky [Transversal Theory, Academic Press (1971)], we present special cases of circuits of (En,In) and extend Ryser's conditions slightly. Latin squares of order n correspond to the solutions of planar 3-dimensional assignment problems and, in view of its solution via linear programming techniques, we present some first classes of facet-defining inequalities for P(In) resp. P(In), the convex hull of all those 0-1 vectors, which correspond to members of In resp. Bn.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr84-004
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 09 Jan 2012 11:36
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/4