On (0, 1)-matrices with prescribed row and column sum vectors

AbstractGiven partitions R and S with the same weight, the Robinson-Schensted-Knuth correspondence establishes a bijection between the class A(R,S) of (0, 1)-matrices with row sum R and column sum S and pairs of Young tableaux of conjugate shapes λ and λ∗, with S≼λ≼R∗. An algorithm for constructing a matrix in A(R,S) whose insertion tableau has a prescribed shape λ, with S≼λ≼R∗, is provided. We generalize some recent constructions due to R. Brualdi for the extremal cases λ=S and λ=R∗