Questions tagged [latin-square]
For questions about latin squares, latin rectangles, their enumeration, their properties, generalisations and related combinatorial configurations such as MOLS (sets of Mutually Orthogonal Latin Squares).
21 questions with no upvoted or accepted answers
13
votes
0
answers
1k
views
Finding a chromatic polynomial by polynomial fitting
I would like to find the chromatic polynomial χ for the n by m rook's graph Gn,m for as many values of n and m possible. The rooks graph is also (a) the line graph of the complete bipartite graph ...
- 4,229
12
votes
0
answers
513
views
Converse of Frobenius
Enumerate the elements of a finite group $G$ as follows: $g_1,g_2,\dots,g_n$. Introduce $n$ variables indexed by the elements of $G$: $x_{g_1},\dots,x_{g_n}$.
Consider the matrix $X_G$ with entries $...
- 43.2k
12
votes
0
answers
258
views
Proving that the set of $\lfloor n/3 \rfloor+1$ partial Latin squares given by Pebody is unavoidable?
Introduction
Cutler and Öhman (2006) attribute to Pebody (via personal communication) a construction of a set of $k:=\lfloor n/3 \rfloor+1$ partial Latin squares which are unavoidable (i.e., any ...
- 4,229
10
votes
0
answers
141
views
Smallest counterexample to Stein's conjecture?
An equi-$n$-square is an $n$ by $n$ array of cells filled with the symbols $1,2,\dots,n$ so that each symbol occurs exactly $n$ times.
(Every Latin square of order $n$ is an equi-$n$-square, but the ...
- 2,350
8
votes
0
answers
88
views
Is recognizing if a Latin square is isotopic to its transpose more efficient than computing its symmetry group?
Ihrig and Ihrig (2007) described a mathematical method for determining if a Latin square is isotopic to its transpose (where isotopic Latin squares vary by permuting the rows, columns and symbols). ...
- 1,327
7
votes
0
answers
190
views
Signatures of latin squares: what about the extremal cases?
For a latin square (LS) of order $n$, we will define a cut (or maybe general transversal, I don't know whether there is an entrenched name for this) as a collection of $n$ cells such that no two share ...
- 13.4k
5
votes
0
answers
105
views
Dinitz Conjecture extension to rectangles
The Dinitz Conjecture, which was proved later in a more general form by Galvin, stated that given an $n\times n$ array, its elements could be filled exactly like a latin square, where the elements in ...
- 2,089
5
votes
0
answers
143
views
Lower bound on the number of k-plexes in a Latin square
Let $A$ be an order-$n$ Latin square. A $k$-plex of $A$ is a set of entries , $k$ from each row and column and $k$ from each symbol.
My question is: Is there a Latin square with a large number of $k$-...
- 1,643
5
votes
0
answers
184
views
Existence problem for a generalisation of Latin squares (matrices with fixed row and column sets)
Let $R_1,\ldots,R_n$ and $C_1,\ldots,C_n$ be sets of size n.
When does there exist an $n \times n$ matrix in which the $i$-th row is a permutation of $R_i$, for all $1 \leq i \leq n$, and the $j$-...
- 4,229
4
votes
0
answers
114
views
Has the existence of a 3-MOLS(10) containing a self-orthogonal Latin square and its transpose been eliminated?
McKay, Meynert, Myrvold (2006) (Small latin squares, quasigroups, and loops, DOI:10.1002/jcd.20105, author copy) computationally eliminate the possibility of set of 3 mutually orthogonal Latin squares ...
- 1,327
4
votes
0
answers
191
views
Does every $n\times n\times n$ Latin cube contain a Latin transversal?
In 1967 H. J. Ryser conjectured that every Latin square of odd order has a Latin transversal. Similar to Latin squares, we may consider Latin cubes.
QUESTION: Let $n$ be any positive integer. Does ...
- 15.6k
3
votes
0
answers
130
views
Is counting Latin squares #P-complete?
I feel like I should know the answer to this. I did some Googling and didn't easily find the answer...
Question: Is counting Latin squares #P-complete?
Obviously the corresponding decision problem &...
- 1,327
2
votes
0
answers
132
views
Proof that a pandiagonal Latin square of order $n$ exists iff $n$ is not a multiple of $2$ or $3$?
A pandiagonal Latin square of order $n$ is an assignment of the numbers $\{0,\ldots,n-1\}$ to the cells of an $n \times n$ grid such that no row, column, or diagonal of any length contains the same ...
- 21
2
votes
1
answer
189
views
Tighter lower bound of the lower triangular sum of an arbitrary Latin square
In this math.stackexchange.com question I seek a tighter bound than the one I presented in there in the question. Rob Pratt puts forth a conjecture in his answer motivated by the dual problem of the ...
- 2,239
2
votes
0
answers
68
views
What is the minimum number of filled cells in a partial Latin rectangle with autotopism group $\cong C_2$ and autoparatopism group $\cong S_3$?
Definitions: a partial Latin rectangle is an $r \times s$ matrix containing symbols from $[n] \cup \{\cdot\}$ such that each row and each column contains at most one copy of any symbol in $[n]$. The ...
- 1,327
1
vote
0
answers
41
views
Unexpected non-uniformity of results from some implementations of Jacobson-Matthews seem to show a strange sensitivity to isotopy class
Questions
Why do some Jacobson-Matthews (J-M) implementations for generating random latin squares exhibit frequencies inconsistent with an underlying uniform distribution?
Further investigation ...
- 41
1
vote
0
answers
26
views
What are the limits to the lengths of the sequences of consecutive completed Sudoku when order 9 Latin squares are generated in lexicographic order?
Question: What are the maximum and minimum lengths of the sequences of consecutive completed Sudoku which occur when order 9 Latin squares are generated in (standard) lexicographic order?
A minimum ...
- 41
1
vote
0
answers
115
views
The condition for mutually orthogonal Latin square
Suppose $A$ and $B$ are Latin squares of order $n$. And suppose any column of $A$ and any column of $B$ have common entry only once. Then are $A$ and $B$ mutually orthogonal?
I know the converse is ...
- 11
1
vote
0
answers
32
views
Is the (left or right) Bol property Isotopy-invariant?
It is well known that a loop satisfies both the left Bol property $(x(yx))z = x(y(xz))$ and the right Bol property $((zx)y)x = z((xy)x)$ if and only if it is a Moufang loop. It is also well known that ...
- 1,947
1
vote
0
answers
383
views
Minimal-information description of sudoku solution (Latin square)
Sudoku puzzles consist of a $9 \times 9$ grid of cells in which some cells contain integers from the set $\{ 1, \ldots, 9 \}$ and the task is to fill in the remaining cells such that the numbers $1$ ...
- 2,558
0
votes
0
answers
131
views
Comparing the perfect groups of order 1344
Take two nonisomorphic perfect groups of order 1344 and label the elements of each with the numbers 1 through 1344, then superimpose their respective Cayley tables (for simplicity’s sake, the nth row ...
- 2,773