Can I read Towards a Solution of the Dinitz Problem? on EtoBox?

Towards a Solution of the Dinitz Problem? by Roland Häggkvist is a Computer Science article available to read on EtoBox.

What is Towards a Solution of the Dinitz Problem? about?

An r x n latin rectangle is an r X n array filled with m symbols, say, such that every cell contains one symbol and every symbol occurs at most once in each row and column. The purpose of this paper is to prove the following result. Theorem. Let L = (Li,i) be an r X n array of n-sets with r < $n. Then L contains an r X n Latin rectangle. This goes some way towards a positive answer to a well-known problem by J. Dinitz, who in 1978 conjectured that the theorem could hold even for r = n in place of r < $2. For background see for instance my paper written in collaboration with Amanda Chetwynd [3] and the references therein, in particular the papers by Bollobas and Harris [2] and Erd&, Rubin and Taylor [4]. Further related problems can be found in the extensive literature on the partial latin squares completion problem (see for instance [l] for some fifty references). Before proving the theorem let us give a couple of definitions and a lemma. For a graph G and subsets A, B of G, we denote by N,(A) the set of neighbours of A in G, by &(A, B) the set of edges between A and B in G and by &(A) the minimum vertex degree in G among vertices from A. If B = B(S, T) is a bipartite graph (with b

Who reads Towards a Solution of the Dinitz Problem??

Author

Roland Häggkvist

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0012-365X)

Published

1989

Language

EN

Field

Computer Science (Physical Sciences)