On permanents of random doubly stochastic matrices and on asymptotic estimates for the number of Latin rectangles and Latin squares

A. N. Timashev

Diskretnaya Matematika, Tome 14 (2002) no. 4, pp. 65-86.

Résumé

We consider the class $\mathfrak A_n(k)$ of all $(0,1)$-matrices $A_k$ of size $n\times n$ with exactly $k$ ones in each row and each column, $k=1,\dots,n$. We prove an asymptotic formula for the permanent $\operatorname{per}A_k$, which holds true as $n\to\infty$ and $0$ uniformly with respect to $A_k\in\mathfrak A_n(k)$. We discuss the known upper and lower bounds for the numbers of $m\times n$ Latin rectangles and of $n\times n$ Latin squares and asymptotic expressions of these numbers as $n\to\infty$ and $m=m(n)$. We notice that the well-known O'Neil conjecture on the asymptotic behaviour of the number of Latin squares holds in a strong form. We formulate new conjectures of such kind and deduce from these conjectures asymptotic estimates of the numbers of Latin rectangles and Latin squares that sharpen the results known before. In conclusion, we give a short review of the literature devoted to the questions discussed in the paper with formulations of the main results.

Bibliographie

[1] Mink Kh., Permanenty, Mir, Moskva, 1982 | MR

[2] Bregman L. M., “Nekotorye svoistva neotritsatelnykh matrits i ikh permanentov”, DAN SSSR, 211:1 (1973), 27–30 | MR | Zbl

[3] Egorychev G. P., Reshenie problemy Van-der-Vardena dlya permanentov, Preprint, Institut fiziki im. L. V. Kirenskogo SO AN SSSR, IFSO-13M, Krasnoyarsk, 1980 | MR | Zbl

[4] O'Neil P. E., “Asymptotic and random matrices with row-sum and column-sum restrictions”, Bull. Amer. Math. Soc., 75:6 (1969), 1276–1282 | DOI | MR

[5] Stein C. M., “Asymptotic evaluation of the number of Latin rectangles”, J. Comb. Theory, 25:1 (1978), 38–49 | DOI | MR | Zbl

[6] Godsil C. D., McKay B. D., “Asymptotic enumeration of Latin rectangles”, J. Comb. Theory, 48:1 (1990), 19–44 | DOI | MR | Zbl

[7] Pazizin S. V., “Ob odnom podkhode k polucheniyu statisticheskikh otsenok razmera generalnoi sovokupnosti”, Diskretnaya matematika, 7:1 (1995), 123–133 | MR | Zbl

[8] Yamamoto K., “On the asymptotic number of Latin rectangles”, Japan. J. Math., 21 (1951), 113–119 | MR | Zbl

[9] Veroyatnost i matematicheskaya statistika, Entsiklopediya, Nauchn. izd-vo BRE, Moskva, 1999

[10] McKay B. D., Rogoyski E., “Latin squares of order 10”, Electronic J. Comb., 1995, no. 2(3), 1–4 | MR

[11] Riordan Dzh., Vvedenie v kombinatornyi analiz, IL, Moskva, 1963

[12] König D., “Über Graphen und ihre Anwendung auf Determinanten–Theorie und Mengelehre”, Math. es Termesz. Ërtesitő, 34 (1916), 104–119 | Zbl

[13] Van der Waerden B. L., “Aufgabe 45”, Jahresber. Deutsch. Math.-Vereinig., 35 (1926), 117

[14] Falikman D. I., “Dokazatelstvo gipotezy Van-der-Vardena o permanente dvazhdy stokhasticheskoi matritsy”, Matem. zametki, 29:6 (1981), 931–938 | MR | Zbl

[15] Minc H., “Upper bounds for permanents of $(0,1)$-matrices”, Bull. Amer. Math. Soc., 69 (1963), 789–791 | DOI | MR | Zbl

[16] Wilf H. S., “On the permanent of a doubly stochastic matrix”, Canad. J. Math., 18 (1966), 758–761 | MR | Zbl

[17] Jurkat W. B., Ryser H. J., “Matrix factorizations of determinants and permanents”, J. Algebra, 3 (1966), 1–27 | DOI | MR | Zbl

[18] Minc H., “A lower bound for permanents of $(0,1)$-matrices”, Proc. Amer. Math. Soc., 18 (1967), 1128–1132 | DOI | MR | Zbl

[19] Erdős P., Rényi A., “On random matrices. II”, Studia Sci. Math. Hungar., 3:4 (1968), 459–464 | MR | Zbl

[20] O'Neil P., “Asymptotic in random $(0,1)$-matrices”, Proc. Amer. Math. Soc., 25:2 (1970), 290–295 | DOI | MR

[21] Sachkov V. N., Veroyatnostnye metody v kombinatornom analize, Nauka, Moskva, 1978 | MR | Zbl

[22] Everett C. J., Stein P. R., “The asymptotic number of $(0,1)$-matrices with zero permanent”, Discrete Math., 6 (1973), 29–34 | DOI | MR | Zbl

[23] Gordon B., Motzkin T. S., Welch L., “Permanents of $(0,1)$-matrices”, J. Comb. Theory, 17 (1974), 145–155 | DOI | MR | Zbl

[24] Schrijver A., Valiant W. G., “On lower bounds for permanents”, Indag. Math., 42 (1980), 425–427 | MR | Zbl

[25] Voorhoeve M., “A lower bound for the permanents of certain $(0,1)$-matrices”, Indag. Math., 41 (1979), 83–86 | MR | Zbl

[26] Timashëv A. N., “Zakon bolshikh chisel dlya permanentov sluchainykh stokhasticheskikh matrits”, Diskretnaya matematika, 11:3 (1999), 91–98

[27] Shevelev V. S., “On “projection” of the Erdős–Rényi theorem about permanent of stochastic $(0,1)$-matrices into the subset of stochastic $(0,1)$-matrices wich equal row sums”, Tezisy dokl. Tretei Vserossiiskoi shkoly-kollokviuma po stokhasticheskim metodam, TVP, Moskva, 1996, 177–178

[28] Ambrosimov A. S., Timashëv A. N., “Zakon bolshikh chisel dlya propusknoi sposobnosti kanalov bez pamyati so sluchainoi perekhodnoi matritsei”, Probl. peredachi informatsii, 31:3 (1995), 24–34 | MR

[29] Mineev M. P., Pavlov A. I., “O chisle $(0,1)$-matrits s zadannymi summami po strokam i stolbtsam”, Dokl. AN SSSR, 230:2 (1976), 271–274 | MR | Zbl

[30] Sachkov V. N., “Sistemy razlichnykh predstavitelei dlya sluchainykh mnozhestv”, Matem. sb., 97 (1975), 395–402 | MR | Zbl

[31] Nosov V. A., Sachkov V. N., Tarakanov V. E., “Kombinatornyi analiz (Matrichnye problemy, teoriya vybora)”, Itogi nauki i tekhniki, ser. Teoriya veroyatnostei. Matematicheskaya statistika. Teoreticheskaya kibernetika, 18, VINITI, Moskva, 1981, 53–93 | MR | Zbl

[32] Rybnikov K. A., Vvedenie v kombinatornyi analiz, MGU, Moskva, 1972 | MR

[33] Sachkov V. N., Kombinatornye metody diskretnoi matematiki, Nauka, Moskva, 1977

[34] Raizer G. Dzh., Kombinatornaya matematika, Mir, Moskva, 1966

[35] Sachkov V. N., “Kombinatornye svoistva neotritsatelnykh matrits”, Probl. kibern., 26 (1978), 37–50

[36] Sachkov V. N., Tarakanov V. E., Kombinatorika neotritsatelnykh matrits, TVP, Moskva, 2000 | MR | Zbl

[37] Korolyuk V. S., Borovskikh Yu. V., Sluchainye permanenty, In-t matematiki AN Ukrainy, Kiev, 1993 | MR

[38] Touchard J., “Sur un problème de permutations”, C. R. Acad. Sci. Paris, 198 (1934), 631–633

[39] Riordan J., “Three-line Latin rectangles”, Amer. Math. Monthly, 51 (1944), 450–452 | DOI | MR

[40] Yamamoto K., “An asymptotic series for the number of three-line Latin rectangles”, J. Math. Soc. Japan, 1 (1949), 226–241 | MR

[41] Gergely E., “A simple method for constructing doubly diagonalized Latin squares”, J. Comb. Theory, 16:2 (1974), 266–272 | DOI | MR | Zbl

[42] Dobrovolskii M. A., “O chetyrekhstrochnykh latinskikh pryamougolnikakh”, Materialy mezhvuzovskoi nauchnoi konf. ped. in-tov tsentr. zony (Tula, 1968), 72–75

[43] Light F. W., “Enumeration of truncated Latin rectangles”, Fibonacci Quart., 17:1 (1979), 34–36 | MR | Zbl

[44] Erdős P., Kaplansky I., “The asymptotic number of Latin rectangles”, Amer. J. Math., 68 (1946), 230–236 | DOI | MR | Zbl

[45] Fisher R., Yates F., “The $6\times 6$ Latin squares”, Proc. Cambridge Philos. Soc., 30 (1934), 492–507 | DOI

[46] Norton H., “The $7\times 7$ squares”, Ann. Eugenics, 9 (1939), 269–307 | MR

[47] Wells B., “The number of Latin squares of order 8”, J. Comb. Theory, 3 (1967), 98–99 | DOI | MR | Zbl

[48] Bammel S., Rothstein J., “The number of $9\times 9$ Latin squares”, Discrete Math., 11 (1975), 93–95 | DOI | MR | Zbl

[49] Alter R., “How many Latin squares are there?”, Amer. Math. Monthly, 82 (1975), 632–634 | DOI | MR | Zbl

[50] Jiayu Shao, Wandi Wei, “A formula for the number of Latin squares”, Discrete Math., 110 (1992), 239–246

[51] Evans T., “Embedding incomplete Latin squares”, Amer. Math. Monthly, 67:10 (1960), 958–961 | DOI | MR

[52] Marica J., Schönheim J., “Incomplete diagonals of Latin squares”, Can. Math. Bull., 12:2 (1969), 235 | MR | Zbl

[53] Lindner C. C., “On completing Latin rectangles”, Can. Math. Bull., 13:1 (1970), 65–68 | MR | Zbl

[54] Dacic R., “On the completion of incomplete Latin squares”, Publ. Inst. Math., Beograd, 23 (1978), 75–80 | MR | Zbl

[55] Häggkvist R., A partial solution of the Evans conjecture for Latin squares, Dep. Math. Univ. Umea, 1976

[56] Häggkvist R., “A solution of the Evans conjecture for Latin squares of large size”, Combinatorics, 1 (1978), 495–513 | MR

[57] Koksma K. K., “A lower bound for the order of a partial transversal in a Latin square”, J. Comb. Theory, 7:1 (1969), 94–95 | DOI | MR | Zbl

[58] Woolbright D. E., “An $n\times n$ Latin square has a transversal with at least $n-\sqrt n$ distinct symbols”, J. Comb. Theory, 24:2 (1978), 235–237 | DOI | MR | Zbl

[59] Brouwer A. E., de Vries A. J., Wieringa R. M. A., “A lower bound for the length of partial transversals in a Latin square”, Nieuw Arch. Wiskd., III, 26 (1978), 330–332 | MR | Zbl

[60] Denes J., Keedwell A. D., Latin squares and their applications, Akademiai Kiado, Budapest, 1974 | MR | Zbl

[61] Kholl M., Kombinatorika, Mir, Moskva, 1970 | MR