No CrossRef data available.
Article contents
Rainbow Perfect Matchings in Complete Bipartite Graphs: Existence and Counting
Published online by Cambridge University Press: 09 July 2013
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
A perfect matching M in an edge-coloured complete bipartite graph Kn,n is rainbow if no pair of edges in M have the same colour. We obtain asymptotic enumeration results for the number of rainbow perfect matchings in terms of the maximum number of occurrences of each colour. We also consider two natural models of random edge-colourings of Kn,n and show that if the number of colours is at least n, then there is with high probability a rainbow perfect matching. This in particular shows that almost every square matrix of order n in which every entry appears n times has a Latin transversal.
Information
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2013
References
[1]Alon, N., Jiang, T., Miller, Z. and Pritikin, D. (2003) Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints. Random Struct. Alg. 23 409–433.CrossRefGoogle Scholar
[2]Arsovski, B. (2011) A proof of Snevily's conjecture. Israel J. Math. 182 505–508.CrossRefGoogle Scholar
[3]Cavenagh, N. J., Greenhill, C. and Wanless, I. M. (2008) The cycle structure of two rows in a random Latin square. Random Struct. Alg. 33 286–309.CrossRefGoogle Scholar
[4]Cooper, C., Gilchrist, R., Kovalenko, I. N. and Novakovic, D. (1999) Deriving the number of ‘good’ permutations, with applications to cryptography. Kibernet. Sistem. Anal. 5 10–16.Google Scholar
[5]Erdős, P. and Spencer, J. (1991) Lopsided Lovász local lemma and Latin transversals. Discrete Appl. Math. 30 151–154.CrossRefGoogle Scholar
[6]Frieze, A. and Krivelevich, M. (2008) On rainbow trees and cycles. Electron. J. Combin. 15 #R59.CrossRefGoogle Scholar
[7]Hatami, P. and Shor, P. W. (2008) A lower bound for the length of a partial transversal in a Latin square. J. Combin. Theory Ser. A 115 1103–1113.CrossRefGoogle Scholar
[8]Jacobson, M. T. and Matthews, P. (1996) Generating uniformly distributed random Latin squares. J. Combin. Designs 4 405–437.3.0.CO;2-J>CrossRefGoogle Scholar
[9]Janson, S. and Wormald, N. (2007) Rainbow Hamilton cycles in random regular graphs. Random Struct. Alg. 30 35–49.CrossRefGoogle Scholar
[10]Kano, M. and Li, X. (2008) Monochromatic and heterochromatic subgraphs in edge-colored graphs: A survey. Graphs Combin. 24 237–263.CrossRefGoogle Scholar
[11]LeSaulnier, T. D., Stocker, C., Wenger, P. S. and West, D. B. (2010) Rainbow matching in edge-colored graphs. Electron. J. Combin. 17 #N26.CrossRefGoogle Scholar
[12]Lu, L. and Szekely, L. A. (2009) A new asymptotic enumeration technique: the Lovasz Local Lemma. ArXiv e-prints.Google Scholar
[13]McKay, B. D. and Wanless, I. M. (1999) Most Latin squares have many subsquares. J. Combin. Theory Ser. A 86 322–347.CrossRefGoogle Scholar
[14]McKay, B. D., McLeod, J. C. and Wanless, I. M. (2006) The number of transversals in a Latin square. Des. Codes Cryptogr. 40 269–284.CrossRefGoogle Scholar
[15]McKay, B. D. and Wormald, N. C. (1991) Uniform generation of random Latin rectangles. J. Combin. Math. Combin. Comput. 9 179–186.Google Scholar
[16]Ryser, H. J. (1967) Neuere Probleme der Kombinatorik. In Vorträge über Kombinatorik, Mathematisches Forschungsinstitut Oberwolfach, pp. 24–29.Google Scholar
[17]Snevily, H. S. (1999) Unsolved problems: The Cayley addition table of Zn. Amer. Math. Monthly 106 584–585.Google Scholar
[18]Stein, S. K. (1975) Transversals of Latin squares and their generalizations. Pacific J. Math. 59 567–575.CrossRefGoogle Scholar
[20]Wanless, I. M. (2007) Transversals in Latin squares. Quasigroups Related Systems 15 169–190.Google Scholar
You have
Access
- 6
- Cited by