Transversals in generalized Latin squares
| Autor: | Zoltán Lóránt Nagy, János Barát |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Algebra and Number Theory Conjecture Theoretical Computer Science Combinatorics Transversal (geometry) Integer Latin square Bounded function Mathematics - Combinatorics Discrete Mathematics and Combinatorics Order (group theory) Geometry and Topology Connection (algebraic framework) Lovász local lemma Mathematics |
| Zdroj: | Ars mathematica contemporanea |
| Popis: | 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-factor. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|