In
mathematics, the theory of
Latin squares
In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin s ...
is an active research area with many
open problems In science and mathematics, an open problem or an open question is a known problem which can be accurately stated, and which is assumed to have an objective and verifiable solution, but which has not yet been solved (i.e., no solution for it is kno ...
. 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
In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin sq ...
of order ''n'' is a set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
''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 . 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 ''c''
''n'' < ''T''(''n'') < ''d''
''n'' ''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
Queens is a borough of New York City, coextensive with Queens County, in the U.S. state of New York. Located on Long Island, it is the largest New York City borough by area. It is bordered by the borough of Brooklyn at the western tip of Long ...
in non-attacking positions on a
toroid
In mathematics, a toroid is a surface of revolution with a hole in the middle. The axis of revolution passes through the hole and so does not intersect the surface. For example, when a rectangle is rotated around an axis parallel to one of its ...
al
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 table Named after the 19th century British mathematician Arthur Cayley, a Cayley table describes the structure of a finite group by arranging all the possible products of all the group's elements in a square table reminiscent of an addition or multiplic ...
s of
cyclic group
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
s of
odd
Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric.
Odd may also refer to:
Acronym
* ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
order. In other words, how many orthomorphisms do these
groups
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
have?
:The minimum number of transversals of a Latin square is also an open problem.
H. J. Ryser
Herbert John Ryser (July 28, 1923 – July 12, 1985) was a professor of mathematics, widely regarded as one of the major figures in combinatorics in the 20th century.[Moufang loop Moufang is the family name of the following people:
* Christoph Moufang (1817–1890), a Roman Catholic cleric
* Ruth Moufang (1905–1977), a German mathematician, after whom several concepts in mathematics are named:
** Moufang–Lie algebra
** ...]
s arise.
*''Proposed:'' by Aleš Drápal at Loops '03, Prague 2003
*''Comments:'' It is well known that every Latin subsquare in a
multiplication table
In mathematics, a multiplication table (sometimes, less formally, a times table) is a mathematical table used to define a multiplication operation for an algebraic system.
The decimal multiplication table was traditionally taught as an essenti ...
of a group ''G'' is of the form ''aH'' x ''Hb'', where ''H'' is a
subgroup
In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''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'' ''n''2 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 be the number of Latin squares of order ''n''. What is the largest integer such that divides
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
? Does grow quadratically in ''n''?
* ''Proposed:'' by Ian Wanless at Loops '03, Prague 2003
* ''Comments:'' Of course,
where
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
for ''n'' = 2, ...,11:
:This table suggests that the power of 2 is growing superlinearly. The best current result is that
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).
See also
*
Problems in loop theory and quasigroup theory
*
Rainbow matching
In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.
Definition
Given an edge-colored graph , a rainbow matching in is a set of pairwise non-adja ...
References
*.
*.
*.
*{{ 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
, doi=10.2307/2974691
, publisher=Mathematical Association of America
, jstor=2974691
.
External links
Loops '99 conferenceLoops '03 conferenceLoops '07 conferenceMilehigh conference on quasigroups, loops, and nonassociative systemsLOOPS package for GAP
Unsolved problems in mathematics
Latin squares