Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Common partial transversals and integral matrices


Author: R. A. Brualdi
Journal: Trans. Amer. Math. Soc. 155 (1971), 475-492
MSC: Primary 05B40; Secondary 05A05
MathSciNet review: 0313093
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Certain packing and covering problems associated with the common partial transversals of two families $ \mathfrak{A}$ and $ \mathfrak{B}$ of subsets of a set $ E$ are investigated. Under suitable finitary restrictions, necessary and sufficient conditions are obtained for there to exist pairwise disjoint sets $ {F_1}, \ldots ,{F_t}$ where each $ {F_i}$ is a partial transversal of $ \mathfrak{A}$ with defect at most $ p$ and a partial transversal of $ \mathfrak{B}$ with defect at most $ q$. We also prove that (i) $ E = \cup _{i = 1}^t{T_i}$ where each $ {T_i}$ is a common partial transversal of $ \mathfrak{A}$ and $ \mathfrak{B}$ if and only if (ii) $ E = \cup _{i = 1}^t{T_i}' $ where each $ {T_i}' $ is a partial transversal of $ \mathfrak{A}$ and (iii) $ E = \cup _{i = 1}^t{T_i}''$ where each $ {T_i}''$ is a partial transversal of $ \mathfrak{B}$. We then derive necessary and sufficient conditions for the validity of (i).

The proofs are accomplished by establishing a connection with these common partial transversal problems and representations of integral matrices (not necessarily finite or countably infinite) as sums of subpermutation matrices and then using known results about the existence of a single common partial transversal of two families. Accordingly various representation theorems for integral matrices are derived.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05B40, 05A05

Retrieve articles in all journals with MSC: 05B40, 05A05


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1971-0313093-3
PII: S 0002-9947(1971)0313093-3
Keywords: Packing problem, covering problem, partial transversal, transversal, defect of a partial transversal, common partial transversal, integral matrix, subpermutation matrix, row and column defect of a subpermutation matrix, permutation matrix, representations of an integral matrix, linking principle
Article copyright: © Copyright 1971 American Mathematical Society