Common partial transversals and integral matrices
Author:
R. A. Brualdi
Journal:
Trans. Amer. Math. Soc. 155 (1971), 475492
MSC:
Primary 05B40; Secondary 05A05
MathSciNet review:
0313093
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Certain packing and covering problems associated with the common partial transversals of two families and of subsets of a set are investigated. Under suitable finitary restrictions, necessary and sufficient conditions are obtained for there to exist pairwise disjoint sets where each is a partial transversal of with defect at most and a partial transversal of with defect at most . We also prove that (i) where each is a common partial transversal of and if and only if (ii) where each is a partial transversal of and (iii) where each is a partial transversal of . 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.
 [1]
Richard
A. Brualdi, A very general theorem on systems of
distinct representatives, Trans. Amer. Math.
Soc. 140 (1969),
149–160. MR 0249304
(40 #2550), http://dx.doi.org/10.1090/S00029947196902493043
 [2]
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
(44 #6506)
 [3]
A.
L. Dulmage and N.
S. Mendelsohn, Some graphical properties of matrices with
nonnegative entries, Aequationes Math. 2 (1969),
150–162. MR 0253922
(40 #7135)
 [4]
Jack
Edmonds, Minimum partition of a matroid into independent
subsets, J. Res. Nat. Bur. Standards Sect. B 69B
(1965), 67–72. MR 0190025
(32 #7441)
 [5]
Jack
Edmonds and D.
R. Fulkerson, Transversals and matroid partition, J. Res. Nat.
Bur. Standards Sect. B 69B (1965), 147–153. MR 0188090
(32 #5531)
 [6]
Jon
Folkman and D.
R. Fulkerson, Flows in infinite graphs, J. Combinatorial
Theory 8 (1970), 30–44. MR 0268065
(42 #2964)
 [7]
L.
R. Ford Jr. and D.
R. Fulkerson, Network flow and systems of representatives,
Canad. J. Math. 10 (1958), 78–84. MR 0098039
(20 #4502)
 [8]
D. R. Fulkerson, Disjoint common partial transversals of two families of sets (to appear).
 [9]
P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935), 2630.
 [10]
Marshall
Hall Jr., Distinct representatives of
subsets, Bull. Amer. Math. Soc. 54 (1948), 922–926. MR 0027033
(10,238g), http://dx.doi.org/10.1090/S00029904194809098X
 [11]
P.
J. Higgins, Disjoint transversals of subsets, Canad. J. Math.
11 (1959), 280–285. MR 0104588
(21 #3341)
 [12]
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 (18,416g)
 [13]
D. König, Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe, Chelsea, New York, 1950. MR 12, 195.
 [14]
L.
Mirsky, Transversals of subsets, Quart. J. Math. Oxford Ser.
(2) 17 (1966), 58–60. MR 0202615
(34 #2477)
 [15]
, Pure and applied combinatorics, Bull. Inst. Math. Appl. 5 (1969), 24.
 [16]
Hazel
Perfect, A generalization of Rado’s theorem on independent
transversals, Proc. Cambridge Philos. Soc. 66 (1969),
513–515. MR 0244065
(39 #5382)
 [1]
 R. A. Brualdi, A very general theorem on systems of distinct representatives, Trans. Amer. Math. Soc. 140 (1969), 149160. MR 0249304 (40:2550)
 [2]
 , A general theorem concerning common transversals, Proc. Conference Combinatorial Mathematics and its Applications (Oxford, 1969), Academic Press, New York, 1971. MR 0289315 (44:6506)
 [3]
 A. L. Dulmage and N. S. Mendelsohn, Some graphical properties of matrices with nonnegative entries, Aequationes Math. 2 (1969), 150162. MR 0253922 (40:7135)
 [4]
 J. Edmonds, Minimum partition of a matroid into independent subsets, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 6772. MR 32 #7441. MR 0190025 (32:7441)
 [5]
 J. Edmonds and D. R. Fulkerson, Transversals and matroid partition, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 147153. MR 32 #5531. MR 0188090 (32:5531)
 [6]
 J. Folkman and D. R. Fulkerson, Flows in infinite graphs, J. Combinatorial Theory 8 (1970), 3044. MR 0268065 (42:2964)
 [7]
 L. R. Ford, Jr. and D. R. Fulkerson, Network flow and systems of representatives, Canad. J. Math. 10 (1958), 7884. MR 20 #4502. MR 0098039 (20:4502)
 [8]
 D. R. Fulkerson, Disjoint common partial transversals of two families of sets (to appear).
 [9]
 P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935), 2630.
 [10]
 M. Hall, Jr., Distinct representatives of subsets, Bull. Amer. Math. Soc. 54 (1948), 922926. MR 10, 238. MR 0027033 (10:238g)
 [11]
 P. J. Higgins, Disjoint transversals of subsets, Canad. J. Math. 11 (1959), 280285. MR 21 #3341. MR 0104588 (21:3341)
 [12]
 A. J. Hoffman and H. W. Kuhn, On systems of distinct representatives. Linear inequalities and related systems, Ann. of Math. Studies, no. 38, Princeton Univ. Press, Princeton, N. J., 1956, pp. 199206. MR 18, 416. MR 0081534 (18:416g)
 [13]
 D. König, Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe, Chelsea, New York, 1950. MR 12, 195.
 [14]
 L. Mirsky, Transversals of subsets, Quart. J. Math. Oxford Ser. (2) 17 (1966), 5860. MR 34 #2477. MR 0202615 (34:2477)
 [15]
 , Pure and applied combinatorics, Bull. Inst. Math. Appl. 5 (1969), 24.
 [16]
 H. Perfect, A generalization of Rado's theorem on independent transversals, Proc. Cambridge Philos. Soc. 66 (1969), 513515. MR 39 #5382. MR 0244065 (39:5382)
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/S00029947197103130933
PII:
S 00029947(1971)03130933
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
