EUVIMEDEUVIMED entdecken
Crossref

Experimental results on the number of perfect matchings in graphs of Latin rectangles

Fariha Iftikhar, Gabor Nagy

Quasigroups and Related Systems · 2025-05 · 33 (2(54)) · 255-266

DOI: 10.56415/qrs.v33.19 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Quasigroups and Related Systems, 2025-05. Verfasst von Fariha Iftikhar und 1 weiteren Autor:innen. Die Arbeit nennt 17 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Iftikhar, F., & Nagy, G. (2025). Experimental results on the number of perfect matchings in graphs of Latin rectangles. Quasigroups and Related Systems, 33(2(54)), 255-266. https://doi.org/10.56415/qrs.v33.19

Vancouver

Iftikhar F, Nagy G. Experimental results on the number of perfect matchings in graphs of Latin rectangles. Quasigroups and Related Systems. 2025;33(2(54)):255-266. doi:10.56415/qrs.v33.19

BibTeX
@article{Iftikhar2025,
  author = {Iftikhar, Fariha and Nagy, Gabor},
  title = {Experimental results on the number of perfect matchings in graphs of Latin rectangles},
  journal = {Quasigroups and Related Systems},
  year = {2025},
  volume = {33},
  number = {2(54)},
  pages = {255--266},
  doi = {10.56415/qrs.v33.19}
}
Kostenlos starten →