Problems in Latin squares

Problems in Latin squares

In mathematics, the theory of Latin squares is an active research area with many open problems. As in other areas of mathematics, such problems are often made public at professional conferences and meetings. Problems posed here appeared in, for instance, the "Loops (Prague)" conferences and the "Milehigh (Denver)" conferences.

Open problems

Bounds on maximal number of transversals in a Latin square

A "transversal" in a Latin square of order n is a set S of n cells such that every row and every column contains exactly one cell of S, and such that the symbols in S form {1,...,n}. Let T(n) be the maximum number of transversals in a Latin square of order n. Estimate T(n).
  • "Proposed:" by Ian Wanless at Loops '03, Prague 2003
  • "Comments:" Wanless, McKay and McLeod have bounds of the form cn < T(n) < dn n!, where c > 1 and d is about 0.6. A conjecture by Rivin, Vardi and Zimmermann (Rivin et al, 1994) says that you can place at least exp(c n log n) queens in non-attacking positions on a toroidal chessboard (for some constant c). If true this would imply that T(n) > exp(c n log n). A related question is to estimate the number of transversals in the Cayley tables of cyclic groups of odd order. In other words, how many orthomorphisms do these groups have?

Characterization of Latin subsquares in multiplication tables of Moufang loops

Describe how all Latin subsquares in multiplication tables of Moufang loops arise.
  • "Proposed:" by Aleš Drápal at Loops '03, Prague 2003
  • "Comments:" It is well known that every Latin subsquare in a multiplication table of a group G is of the form aH x Hb, where H is a subgroup of G and a, b are elements of G.

Densest partial Latin squares with Blackburn property

A partial Latin square has "Blackburn property" if whenever the cells (i,j) and (k,l) are occupied by the same symbol, the opposite corners (i,l) and (k,j) are empty. What is the highest achievable density of filled cells in a partial Latin square with the Blackburn property? In particular, is there some constant c > 0 such that we can always fill at least c n2 cells?
  • "Proposed:" by Ian Wanless at Loops '03, Prague 2003
  • "Comments:" In a paper to appear, Wanless has shown that if c exists then c < 0.463. He also constructed a family of partial Latin squares with the Blackburn property and asymptotic density of at least exp(-d(log n)1/2)) for constant d>0.

Largest power of 2 dividing the number of Latin squares

Let L_n be the number of Latin squares of order n. What is the largest integer p(n) such that 2^{p(n)} divides L_n? Does p(n) grow quadratically in n?
  • "Proposed:" by Ian Wanless at Loops '03, Prague 2003
  • "Comments:" Of course, L_n=n!(n-1)!R_n where R_n is the number of reduced Latin squares of order n. This immediately gives a linear number of factors of 2. However, here are the prime factorizations of R_n for n=2, ... ,11:This table suggests that the power of 2 is growing superlinearly. The best current result is that R_n is always divisible by f!, where f is about n/2. See (McKay and Wanless, 2003). Two authors noticed the suspiciously high power of 2 (without being able to shed much light on it): (Alter, 1975), (Mullen, 1978).

ee also

*Problems in loop theory and quasigroup theory

References

Citation
last=Alter | first=Ronald | title=How many latin squares are there? | journal=Amer. Math. Monthly
volume=82 | year=1975 | issue=6 | pages=632-634
. Citation
last=McKay | first=Brendan | first2=Ian | last2=Wanless | title=On the number of latin squares
journal=Ann. Combin. | volume=9 | year=2005 | pages=335-344
. Citation
last=Mullen | first=Garry | title=How many i-j reduced latin squares are there?
journal=Amer. Math. Monthly | volume=85 | year=1978 | issue=9 | pages=751-752
. Citation
last1=Rivin | first1=Igor | first2=Ilan | last2=Vardi | first3=Paul | last3=Zimmerman
title=The n-queens problem | journal=Amer. Math. Monthly | volume=101 | year=1994 | issue=7 | pages=629-639
.

External links

* [http://www.karlin.mff.cuni.cz/~loops99 Loops '99 conference]
* [http://www.karlin.mff.cuni.cz/~loops03 Loops '03 conference]
* [http://www.karlin.mff.cuni.cz/~loops07 Loops '07 conference]
* [http://www.math.du.edu/milehigh Milehigh conference on quasigroups, loops, and nonassociative systems]
* [http://www.math.du.edu/loops LOOPS package for GAP]


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Latin square — A Latin square is an n times; n table filled with n different symbols in such a way that each symbol occurs exactly once in each row and exactly once in each column. Here is an example: egin{bmatrix} 1 2 3 2 3 1 3 1 2 end{bmatrix} Latin squares… …   Wikipedia

  • Problems in loop theory and quasigroup theory — In mathematics, especially abstract algebra, loop theory and quasigroup theory are active research areas with many open problems. As in other areas of mathematics, such problems are often made public at professional conferences and meetings. Many …   Wikipedia

  • List of unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Contents 1 Millennium Prize Problems 2 Other still unsolved problems 2.1 Additive number theory …   Wikipedia

  • Unsolved problems in statistics — There are many longstanding unsolved problems in mathematics for which a solution has still not yet been found. The unsolved problems in statistics are generally of a different flavor; according to John Tukey, difficulties in identifying problems …   Wikipedia

  • Unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Millennium Prize Problems Of the seven Millennium Prize Problems set by the Clay Mathematics Institute, the six ones yet to be solved are:… …   Wikipedia

  • Graeco-Latin square — Orthogonal Latin squares of order 3 Orthogonal Latin squares of order 5 In mathematics, a Graeco Latin square or Euler square or orthogonal Latin squares of order n over two …   Wikipedia

  • Glossary of chess problems — This is a list of terms used in chess problems. For a list of unorthodox pieces used in chess problems, see fairy chess piece. For a list of terms used in chess is general, see chess terminology. Contents: Top · 0–9 · A B C D E F G H I… …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium

  • Sudoku — Not to be confused with Sodoku. A Sudoku puzzle …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”