A latin négyzetektől a házasságig

Rácz Gabriella: A latin négyzetektől a házasságig 

Ha egy n sorból és n oszlopból álló táblázatot úgy töltünk ki n darab szimbólum használatával, hogy a táblázat minden sorában és oszlopában minden szimbólum pontosan egyszer szerepeljen, akkor egy n × n-es latin négyzetet kapunk. Latin négyzet minden méretben létezik. 

Jeff Dinitz 1978-ban azt a kérdést tette fel, hogy ha az üres táblázatunk minden mezőjéhez hozzárendeljük szimbólumoknak egy-egy listáját, akkor kitölthető-e a táblázat úgy, hogy továbbra is minden sorban és minden oszlopban csupa különböző szimbólum szerepeljen, továbbá, hogy minden mezőbe csak az ahhoz tartozó listáról választhatunk szimbólumot? 

Bár ez nem tűnik túl nagy megszorításnak, mégis 15 évet kellett várni a kérdés megválaszolására. Az előadás során megismerkedünk a megoldáshoz szükséges ötletekkel, és az is kiderül majd, hogy mi köze van mindehhez a házasságnak. 

Az előadás a Kutatók Éjszakája a Matematikai Intézetben esemény része.