317 KB23 KB200820252019Barát, JánosNagy, Zoltán Lórántštevilka:1letnik:16str. 39-47ISSN:1855-3966COBISSID_HOST:18701401URN:URN:NBN:SI:doc-OJ7EHEDNenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaanti-Ramsey problemsanti-Ramseyjevi problemiLatin squareslatinski kvadratiLovász local lemmaLovászeva lokalna lematransversalstransverzaleTransversals in generalized Latin squares|We are seeking a sufficient condition that forces a transversal in a generalized Latin square. A generalized Latin square of order ?$n$? is equivalent to a proper edge-coloring of ?$K_{n, n}$?. A transversal corresponds to a multicolored perfect matching. S. Akbari and A. Alipour J. Comb. Des. 12, No. 5, 325-332 (2004) defined ?$l(n)$? as the least integer such that every properly edge-colored ?$K_{n, n}$?, which contains at least ?$l(n)$? different colors, admits a multicolored perfect matching. They conjectured that ?$l(n) \leq n^2/2\ \mathrm{if}\ n$? is large enough. In this note we prove that ?$l(n)$? is bounded from above by ?$0.75n^2\ \mathrm{if}\ n > 1$?. We point out a connection to anti-Ramsey problems. We propose a conjecture related to a well-known result by D. E. Woolbright and H.-L. Fu J. Comb. Des. 6, No. 1, 1-20 (1998), that every proper edge-coloring of ?$K_{2n}$? admits a multicolored 1-factorIšč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-faktorTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije