Experimental results on the number of perfect matchings in graphs of latin rectangles [Articol]

Abstract

Latin rectangles, perfect matchings, and 1-factorizations of regular bipartite graphs are closely related through combinatorial constructions. We give a survey of classical results concerning the existence and enumeration of perfect matchings in bipartite graphs, including König’s and Hall’s theorems, as well as lower bounds provided by van der Waerden, Voorhoeve, and Schrijver. We discuss the connection between Latin rectangles and k-factorizations of regular bipartite graphs, highlighting that every k n Latin rectangle corresponds to a k-regular bipartite graph with 2n vertices. In 1986, Bollobás and McKay presented the asymptotic estimate for the expected number of perfect matchings in random k-regular bipartite graphs. Motivated by this probabilistic result, we performed numerical experiments on the average number of perfect matchings in random 3-regular bipartite graphs arising from Latin rectangles. Our computational results, based on calculating matrix permanents for subsets of Latin squares, show strong agreement with the Bollobás-McKay asymptotic formula.