Transversals in generalized Latin squares

angleški

2019

letnik 16, številka 1

anti-Ramseyjevi problemi   latinski kvadrati   Lovászeva lokalna lema   transverzale

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Iščemo zadosten pogoj za obstoj transverzale v posplošenem latinskem kvadratu. Posplošeni latinski kvadrat reda n je ekvivalenten pravilnemu barvanju povezav grafa ?$K_{n, n}$?. Transverzala ustreza večbarvnemu popolnemu prirejanju. Akbari in Alipour sta definirala ?$l(n)$? kot najmanjše celo število, za katero velja, da vsako pravilno barvanje povezav grafa ?$K_{n, n}$?, ki vsebuje najmanj ?$l(n)$? različnih barv, dopušča večbarvno popolno prirejanje. Postavila sta domnevo, da je ?$l(n) \leq n^2/2\ \mathrm{if}\ n$? če je ?$n$? dovolj velik. V tem kratkem članku dokažemo, da je število ?$l(n)$? navzgor omejeno z ?$0.75n^2\ \mathrm{if}\ n > 1$?. Izpostavimo povezavo z anti-Ramseyevimi problemi. Postavimo domnevo, povezano z dobro znanim rezultatom Woolbrighta in Fuja, da vsako pravilno barvanje povezav grafa ?$K_{2n}$? dopušča večbarvni 1-faktor.

29.05.2020