Problem i latinska rutor

Inom matematiken är teorin om latinska kvadrater ett aktivt forskningsområde med många öppna problem . Liksom inom andra matematikområden offentliggörs ofta sådana problem vid professionella konferenser och möten. Problem som ställs här dök upp i till exempel Loops (Prag) konferenser och Milehigh (Denver) konferenser.

Öppna problem

Gränser för maximalt antal transversaler i en latinsk kvadrat

En transversal i en latinsk kvadrat av ordningen n är en uppsättning S av n celler så att varje rad och varje kolumn innehåller exakt en cell av S , och så att symbolerna i S bildar {1, ..., n }. Låt T ( n ) vara det maximala antalet transversaler i en latinsk kvadrat av ordningen n . Uppskatta T ( n ).

Föreslagen: av Ian Wanless på Loops '03, Prag 2003
Kommentarer: Wanless, McKay och McLeod har gränser av formen c ⁿ < T ( n ) < d ⁿ n !, där c > 1 och d är ungefär 0,6. En gissning av Rivin, Vardi och Zimmermann (Rivin et al., 1994) säger att man kan placera åtminstone exp( c n log n ) damer i icke-attackerande positioner på ett toroidformat schackbräde (för vissa konstanta c ). Om sant skulle detta innebära att T ( n ) > exp( c n log n ). En relaterad fråga är att uppskatta antalet transversaler i Cayley-tabellerna för cykliska grupper av udda ordning . Med andra ord, hur många ortomorfismer har dessa grupper ?

Minsta antalet transversaler av en latinsk kvadrat är också ett öppet problem. HJ Ryser gissade (Oberwolfach, 1967) att varje latinsk kvadrat av udda ordning har en. Nära besläktad är gissningen, tillskriven Richard Brualdi, att varje latinsk kvadrat av ordningen n har en partiell tvärgående ordning på åtminstone n − 1.

Karakterisering av latinska delkvadrater i multiplikationstabeller för Moufang-slingor

Beskriv hur alla latinska delkvadrater i multiplikationstabellerna för Moufang-slingor uppstår.

Föreslagen: av Aleš Drápal på Loops '03, Prag 2003
Kommentarer: Det är välkänt att varje latinsk delkvadrat i en multiplikationstabell för en grupp G har formen aH x Hb , där H är en undergrupp av G och a , b är element i G .

Tätaste partiella latinska torg med Blackburn-egendom

En partiell latinsk kvadrat har Blackburn-egenskap om när cellerna ( i , j ) och ( k , l ) är upptagna av samma symbol, är de motsatta hörnen ( i , l ) och ( k , j ) tomma. Vilken är den högsta möjliga tätheten av fyllda celler i en partiell latinsk kvadrat med Blackburn-egenskapen? I synnerhet, finns det någon konstant c > 0 så att vi alltid kan fylla åtminstone c n ² celler?

Föreslagen: av Ian Wanless på Loops '03, Prag 2003
Kommentarer: Wanless har i ett papper som ska dyka upp visat att om c existerar så är c < 0,463. Han konstruerade också en familj av partiella latinska kvadrater med egenskapen Blackburn och en asymptotisk densitet på minst exp(- d (log n ) ^1/2 ) för konstant d > 0.

Största potens av 2 dividera antalet latinska rutor

Låt $L_{n}$ vara antalet latinska kvadrater av ordningen n . Vilket är det största heltal $p(n)$ så att $2^{p(n)}$ delar $L_{n}$ ? Växer $p(n)$ kvadratiskt i n ?

Föreslagen: av Ian Wanless på Loops '03, Prag 2003
Kommentarer: Naturligtvis, $L_{n}=n!(n-1)!R_{n}$ där $R_{n}$ är antalet reducerade latinska kvadrater av ordningen n . Detta ger omedelbart ett linjärt antal faktorer på 2. Men här är primfaktoriseringarna av R $\displaystyle R_{n}}$ för 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

Denna tabell antyder att styrkan av 2 växer superlinjärt. Det bästa aktuella resultatet är att

R_{n}

alltid är delbart med f !, där f är ungefär n /2. Se (McKay och Wanless, 2003). Två författare lade märke till den misstänkt höga kraften hos 2 (utan att kunna kasta mycket ljus över det): (Alter, 1975), (Mullen, 1978).

Se även

Alter, Ronald (1975), "Hur många latinska rutor finns det?", Amer. Matematik. Monthly , Mathematical Association of America, 82 (6): 632–634, doi : 10.2307/2319697 , JSTOR 2319697 .
McKay, Brendan; Wanless, Ian (2005), "Om antalet latinska kvadrater", Ann. Kombinera. , 9 (3): 335–344, doi : 10.1007/s00026-005-0261-7 , S2CID 7289396 .
Mullen, Garry (1978), "Hur många ij reducerade latinska kvadrater finns det?", Amer. Matematik. Monthly , Mathematical Association of America, 85 (9): 751–752, doi : 10.2307/2321684 , JSTOR 2321684 .
Rivin, Igor; Vardi, Ilan; Zimmerman, Paul (1994), "The n-queens problem", Amer. Matematik. Monthly , Mathematical Association of America, 101 (7): 629–639, doi : 10.2307/2974691 , JSTOR 2974691 .

externa länkar