On joint realization of (0, 1) matrices

AbstractLet R=(r1,r2,…,rm), S=(s1,s2,…,sn), R′=(r′1,r′2,… ,r′m), and S′= (s′1,s′2,s′n be nonnegative integral vectors. Denote by A(R,S) the class of (0,1) matrices with row sum vector R and column sum vector S. The three classes A(R,S), A(R′,S′), and A(R+R′,S+S′) are called jointly realizable if there exist a matrix A in A(R,S) and a matrix B in A(R′,S′) such that A+Bϵ A(R+R′,S+S′). In this paper, we prove that if A(R,S), A(R′,S′), and A(R+R′,S+S′) are nonempty but not jointly realizable, then in the first two classes there must exist a matrix having one of the following unavoidable configurations: , . A similar theorem is proved about unavoidable configurations in A(R+R′,S+S′). We also give a slight generalization of a theorem of Anstee, regarding joint realization of matrices where one of the classes has row sums differing by at most 1, along with a very short proof