On a conjecture of Stein. (English) Zbl 1379.05115
Authors’ abstract: S. K. Stein [Pac. J. Math. 59, 567–575 (1975; Zbl 0302.05015)] proposed the following conjecture: if the edge set of \(K_{n,n}\) is partitioned into \(n\) sets, each of size \(n\), then there is a partial rainbow matching of size \(n- 1\). He proved that there is a partial rainbow matching of size \(n(1 -\frac{D_{n}} {n!} )\), where \(D_n\) is the number of derangements of [\(n\)]. This means that there is a partial rainbow matching of size about \((1- \frac{1} {e} )n\). Using a topological version of Hall’s theorem we improve this bound to \(\frac{2} {3}n\).
Reviewer: Ioan Tomescu (Bucureşti)
MSC:
| 05D05 | Extremal set theory |
| 05D15 | Transversal (matching) theory |
| 05B15 | Orthogonal arrays, Latin squares, Room squares |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
Citations:
Zbl 0302.05015References:
| [1] | Adamaszek, M., Barmak, J.A.: On a lower bound for the connectivity of the independence complex of a graph. Discrete Math. 311, 2566-2569 (2011) · Zbl 1238.05152 · doi:10.1016/j.disc.2011.06.010 |
| [2] | Aharoni, R., Alon, N., Berger, E.: Eigenvalues of \[K_{1,k}\] K1,k-free graphs and the connectivity of their independence complexes J. Graph Theory 83, 384-391 (2016) · Zbl 1350.05089 |
| [3] | Aharoni, R., Alon, N., Berger, E., Chudnovsky, M., Kotlar, D., Loebl, M., Ziv, R.: Fair representation by independent sets. Discrete Math (to appear) · Zbl 1387.05170 |
| [4] | Aharoni, R., Berger, E., Ziv, R.: Independent systems of representatives in weighted graphs. Combinatorica 27, 253-267 (2007) · Zbl 1164.05020 · doi:10.1007/s00493-007-2086-y |
| [5] | Aharoni, R., Gorelik, I., Narins, L.: A bound on the connectivity of line graphs (unpublished) · Zbl 1164.05020 |
| [6] | Aharoni, R., Haxell, P.: Hall’s theorem for hypergraphs. J. Graph Theory 35, 83-88 (2000) · Zbl 0956.05075 · doi:10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V |
| [7] | Björner, A., Lovász, L., Vrecica, S.T., Zivaljevic, R.T.: Chessboard complexes and matching complexes. J. Lond. Math. Soc. 49, 25-39 (1994) · Zbl 0790.57014 · doi:10.1112/jlms/49.1.25 |
| [8] | Brualdi, R.A., Ryser, H.J.: Combinatorial Matrix Theory. Cambridge University Press, Cambridge (1991) · Zbl 0746.05002 · doi:10.1017/CBO9781107325708 |
| [9] | Hatami, P., Shor, P.W.: A lower bound for the length of a partial transversal in a Latin square. J. Combin. Theory A 115, 1103-1113 (2008) · Zbl 1159.05303 · doi:10.1016/j.jcta.2008.01.002 |
| [10] | Haxell, P.E.: A condition for matchability in hypergraphs. Graphs Combin. 11, 245-248 (1995) · Zbl 0837.05082 · doi:10.1007/BF01793010 |
| [11] | Jin, G.P.: Complete subgraphs of r-partite graphs. Combin. Probab. Comput. 1, 241-250 (1992) · Zbl 0793.05088 · doi:10.1017/S0963548300000274 |
| [12] | Koksma, K.K.: A lower bound for the order of a partial transversal of a Latin square. J. Combin. Theory 7, 94-95 (1969) · Zbl 0172.01504 · doi:10.1016/S0021-9800(69)80009-8 |
| [13] | Meshulam, R.: The clique complex and hypergraph matching. Combinatorica 21, 89-94 (2001) · Zbl 1107.05302 · doi:10.1007/s004930170006 |
| [14] | Meshulam, R.: Domination numbers and homology. J. Combin. Theory Ser. A 102, 321-330 (2003) · Zbl 1030.05086 · doi:10.1016/S0097-3165(03)00045-1 |
| [15] | Ryser, H.J.: Neuere Probleme der Kombinatorik, pp. 69-91. Oberwolfach, Matematisches Forschungsinstitut (Oberwolfach, Germany), July, Vorträge über Kombinatorik (1967) |
| [16] | Shor, P.W.: A lower bound for the length of a partial transversal in a Latin square. J. Combin. Theory Ser. A 33, 1-8 (1982) · Zbl 0489.05012 · doi:10.1016/0097-3165(82)90074-7 |
| [17] | Shareshian, J., Wachs, M.L.: Top homology of hypergraph matching complexes, p-cycle complexes and Quillen complexes of symmetric groups. J. Algebra 322, 2253-2271 (2009) · Zbl 1188.20060 · doi:10.1016/j.jalgebra.2008.11.042 |
| [18] | Stein, S.K.: Transversals of Latin squares and their generalizations. Pac. J. Math. 59, 567-575 (1975) · Zbl 0302.05015 · doi:10.2140/pjm.1975.59.567 |
| [19] | Woolbright, D.E.: An \[n\times n\] n×n Latin square has a transversal with at least \[n-\sqrt{n}\] n-\sqrt{n} distinct elements. J. Combin. Theory Ser. A 24, 235-237 (1978) · Zbl 0368.05012 · doi:10.1016/0097-3165(78)90009-2 |
| [20] | Yuster, R.: Independent transversals in r-partite graphs. Discrete Math. 176, 255-261 (1997) · Zbl 0891.05041 · doi:10.1016/S0012-365X(96)00300-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
