Problémy v latinských čtvercích - Problems in Latin squares

v matematika, teorie Latinské čtverce je aktivní výzkumná oblast s mnoha otevřené problémy. Stejně jako v jiných oblastech matematiky jsou tyto problémy často zveřejňovány na odborných konferencích a setkáních. Problémy, které zde nastaly, se objevily například v Loops (Praha) konference a konference Milehigh (Denver) konference.

Otevřené problémy

Hranice maximálního počtu příčných v latinském čtverci

A příčný v Latinský čtverec řádu n je soubor S z n buňky tak, že každý řádek a každý sloupec obsahuje přesně jednu buňku Sa takové, že symboly v S formulář {1, ..., n}. Nechat T(n) je maximální počet průřezů v latinském čtverci pořadí n. Odhad T(n).

Navrženo: Ian Wanless at Loops '03, Praha 2003
Komentáře: Wanless, McKay a McLeod mají hranice formy Cⁿ < T(n) < dⁿ n!, kde C > 1 a d je asi 0,6. Domněnka Rivina, Vardiho a Zimmermanna (Rivin et al., 1994) říká, že můžete umístit alespoň exp (C n log n) královny v neútočících pozicích na a toroidní šachovnice (pro nějakou konstantu C). Pokud je to pravda, znamenalo by to T(n)> exp (C n log n). Související otázkou je odhadnout počet příčných řezů v Cayleyovy stoly z cyklické skupiny z zvláštní objednat. Jinými slovy, kolik ortomorfismů to dělá skupiny mít?

Otevřeným problémem je také minimální počet příčných řezů latinského čtverce. H. J. Ryser domníval se (Oberwolfach, 1967), že každý latinský čtverec lichého řádu má jeden. Úzce souvisí domněnka připisovaná Richardu Brualdimu, že každý latinský čtverec řádu n má alespoň částečný příčný řád n − 1.

Charakterizace latinských dílčích čtverců v multiplikačních tabulkách Moufangových smyček

Popište, jak se všechny latinské podčíslí v násobících tabulkách Mufangové smyčky vzniknout.

Navrženo: Aleš Drápal na Loops '03, Praha 2003
Komentáře: Je dobře známo, že každý latinský subsquare v a násobilka skupiny G je ve formě aH X Hb, kde H je podskupina z G a A, b jsou prvky G.

Nejhustší částečné latinské čtverce s vlastnostmi Blackburnu

Částečný latinský čtverec má Nemovitost Blackburn pokud kdykoli buňky (i, j) a (k, l) jsou obsazeny stejným symbolem, protilehlé rohy (i, l) a (k, j) jsou prázdné. Jaká je nejvyšší dosažitelná hustota vyplněných buněk v částečném latinském čtverci s vlastností Blackburn? Zejména existuje nějaká konstanta C > 0, takže můžeme vždy vyplnit alespoň C n² buňky?

Navrženo: Ian Wanless at Loops '03, Praha 2003
Komentáře: V příspěvku, který se má objevit, Wanless ukázal, že pokud C pak existuje C <0,463. Zkonstruoval také rodinu částečných latinských čtverců s vlastností Blackburnu a asymptotickou hustotou alespoň exp (-d(log n)^1/2) pro konstantní d > 0.

Největší síla 2 dělící počet latinských čtverců

Nechat ${ displaystyle L_ {n}}$ být počet latinských čtverců objednávky n. Co je to největší celé číslo ${ displaystyle p (n)}$ takhle ${ displaystyle 2 ^ {p (n)}}$ rozděluje ${ displaystyle L_ {n}}$ ? Ano ${ displaystyle p (n)}$ kvadraticky rostou n?

Navrženo: Ian Wanless at Loops '03, Praha 2003
Komentáře: Samozřejmě, ${ displaystyle L_ {n} = n! (n-1)! R_ {n}}$ kde ${ displaystyle R_ {n}}$ je počet zmenšených latinských čtverců objednávky n. To okamžitě dává lineární počet faktorů 2. Zde jsou však primární faktorizace z ${ displaystyle R_ {n}}$ pro n = 2, ...,11:

2	3	4	5	6	7	8	9	10	11
1	1	2²	2³7	2⁶37²	2¹⁰35*1103	2¹⁷31361291	2²¹3²5231*3824477	2²⁸3²53137*547135293937	2³⁵3⁴528012206499*62368028479

Tato tabulka naznačuje, že síla 2 roste superlineárně. Nejlepší aktuální výsledek je

{ displaystyle R_ {n}}

je vždy dělitelné F!, kde F je o n/ 2. Viz (McKay a Wanless, 2003). Dva autoři si všimli podezřele vysoké síly 2 (aniž by na ni dokázali vrhnout mnoho světla): (Alter, 1975), (Mullen, 1978).

Viz také

Reference

Alter, Ronald (1975), „Kolik je latinských čtverců?“, Amer. Matematika. Měsíční, Mathematical Association of America, 82 (6): 632–634, doi:10.2307/2319697, JSTOR 2319697.
McKay, Brendan; Wanless, Ian (2005), „O počtu latinských čtverců“, Ann. Kombinovat., 9 (3): 335–344, doi:10.1007 / s00026-005-0261-7.
Mullen, Garry (1978), „Kolik i-j zmenšených latinských čtverců existuje?“, Amer. Matematika. Měsíční, Mathematical Association of America, 85 (9): 751–752, doi:10.2307/2321684, JSTOR 2321684.
Rivin, Igor; Vardi, Ilan; Zimmerman, Paul (1994), „Problém n-královen“, Amer. Matematika. Měsíční, Mathematical Association of America, 101 (7): 629–639, doi:10.2307/2974691, JSTOR 2974691.