Some applications of linear algebra in combinatorics

• Main Authors: Co, Cherielyn A., Mitra, Lalyn V.
• Format: text
• Language: English
• Published: Animo Repository 1996
• Subjects: Algebras, Linear; Combinatorial analysis; Marriage theorem; Partitions (Mathematics)
• Online Access: https://animorepository.dlsu.edu.ph/etd_bachelors/16298
• Institution: De La Salle University

This paper presents the proofs using Linear Algebra of two Combinatorial theorems, namely the Marriage Theorem and a theorem on Biclique Partitions stated respectively:(1) The sets A1, A2, ..., An possess a system of distinct representatives if and only if, for all k = 1, 2, ..., n, any k sets A1 contain at least k elements in their union.(2) The complete graph Kn of order n cannot be partitioned into fewer than n - 1 bicliques.