Common partial transversals and integral matrices
HTML articles powered by AMS MathViewer
- by R. A. Brualdi PDF
- Trans. Amer. Math. Soc. 155 (1971), 475-492 Request permission
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
- Richard A. Brualdi, A very general theorem on systems of distinct representatives, Trans. Amer. Math. Soc. 140 (1969), 149–160. MR 249304, DOI 10.1090/S0002-9947-1969-0249304-3
- Richard A. Brualdi, A general theorem concerning common transversals, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) Academic Press, London, 1971, pp. 39–60. MR 0289315
- A. L. Dulmage and N. S. Mendelsohn, Some graphical properties of matrices with non-negative entries, Aequationes Math. 2 (1969), 150–162. MR 253922, DOI 10.1007/BF01817698
- Jack Edmonds, Minimum partition of a matroid into independent subsets, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 67–72. MR 190025
- Jack Edmonds and D. R. Fulkerson, Transversals and matroid partition, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 147–153. MR 188090
- Jon Folkman and D. R. Fulkerson, Flows in infinite graphs, J. Combinatorial Theory 8 (1970), 30–44. MR 268065
- L. R. Ford Jr. and D. R. Fulkerson, Network flow and systems of representatives, Canadian J. Math. 10 (1958), 78–84. MR 98039, DOI 10.4153/CJM-1958-009-1 D. R. Fulkerson, Disjoint common partial transversals of two families of sets (to appear). P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935), 26-30.
- Marshall Hall Jr., Distinct representatives of subsets, Bull. Amer. Math. Soc. 54 (1948), 922–926. MR 27033, DOI 10.1090/S0002-9904-1948-09098-X
- P. J. Higgins, Disjoint transversals of subsets, Canadian J. Math. 11 (1959), 280–285. MR 104588, DOI 10.4153/CJM-1959-030-9
- A. J. Hoffman and H. W. Kuhn, On systems of distinct representatives, Linear inequalities and related systems, Annals of Mathematics Studies, no. 38, Princeton University Press, Princeton, N.J., 1956, pp. 199–206. MR 0081534 D. König, Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe, Chelsea, New York, 1950. MR 12, 195.
- L. Mirsky, Transversals of subsets, Quart. J. Math. Oxford Ser. (2) 17 (1966), 58–60. MR 202615, DOI 10.1093/qmath/17.1.58 —, Pure and applied combinatorics, Bull. Inst. Math. Appl. 5 (1969), 2-4.
- Hazel Perfect, A generalization of Rado’s theorem on independent transversals, Proc. Cambridge Philos. Soc. 66 (1969), 513–515. MR 244065, DOI 10.1017/s0305004100045266
Additional Information
- © Copyright 1971 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 155 (1971), 475-492
- MSC: Primary 05B40; Secondary 05A05
- DOI: https://doi.org/10.1090/S0002-9947-1971-0313093-3
- MathSciNet review: 0313093