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

• Author(s): Fonseca, C. M. da ; Mamede, Ricardo
• Date: 2007
• Persistent ID: http://hdl.handle.net/10316/11281
• Origin: Estudo Geral - Universidade de Coimbra
• Subject(s): (0, 1)-matrices; Partitions; Majorizationns; Young tableaux; RSK algorithm
• Document Type: Preprint
• Language: English

Description

Given 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 (P,Q) of Young tableaux of conjugate shapes and , with S 4 4 R. An algorithm for constructing a matrix in A(R, S) whose insertion tableaux has a prescribed shape with S 4 4 R, is provided. We generaliz some recent constructions due to R. Brualdi for the extremal cases = S and = R.