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).
53 questions
1
vote
1
answer
52
views
Comparability of elements in a Latin square based on a few rows
Let $\Pi=\{\pi_1,\pi_2,\dots,\pi_n\}$ be the rows of an $n\times n$ Latin square (the order of the rows does not matter).
Each row $\pi_i$ induces an order $\prec_i$ on the elements of $[1,n]$, where $...
- 235
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
3
votes
2
answers
197
views
Proper Latin sub-squares of generalized Latin squares
Say we have a generalization of a Latin square, where the square is of size $n \times n$, $n = ab$ and each row and each column has $b$ occurrences of each of $[1, \dots, a]$. Is there always ...
- 31
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
1
vote
1
answer
118
views
A bound on the number of partial transversals of a latin square
A Latin Square (LS) of order $n$ is an $n$ on $n$ matrix, each entry contains one of the symbols $1,2,\ldots,n$, and every row and every column contains each symbol exactly once. A (complete) ...
- 173
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
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
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
2
votes
1
answer
81
views
Are there any studies about general lexicographical orderings of Latin Squares and random walks on the space of all such orderings of a given order?
Are there any previous studies about the general lexicographical orderings of Latin squares including random walks the space of all such orderings for a given order of Latin squares?
Are there any ...
- 41
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
13
votes
3
answers
1k
views
Does there exist a Latin square of order 9 for which its 9 broken diagonals and 9 broken antidiagonals are transversals?
A Latin square of order $n$ has $n$ broken diagonals and $n$ broken antidiagonals. When $n \equiv \pm 1 \pmod 6$, we have diagonally cyclic Latin squares in which those $2n$ diagonals are ...
- 1,327
8
votes
3
answers
433
views
Latin squares with one cycle type?
Cross posting from MSE, where this question received no answers.
The following Latin square
$$\begin{bmatrix}
1&2&3&4&5&6&7&8\\
2&1&4&5&6&7&8&3\\...
- 168
1
vote
3
answers
187
views
Existence of latin squares with an involutory symmetry
Let $M \in \mathbb{N}$ and let $\pi \in S_{M}$ be an involution with at least one fixed point. I'm interested in finding a latin square $A$ of order $M$ such that $A_{i,j} = \pi(A_{j,i})$ for each $i,...
- 93
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
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
3
votes
1
answer
311
views
Evans conjecture for symmetric latin squares
The Evans conjecture ( which was proved later by Smetaniuk) states that for any $n$, if at most $n-1$ entries of a partial $n\times n$ latin square are filled, it can be completed to the full latin ...
- 2,089
2
votes
2
answers
228
views
The edge precoloring extension problem for complete graphs
Consider coloring the edges of a complete graph on even order. This can be seen as the completion of an order $n$ symmetric Latin square except the leading diagonal. My question pertains to whether we ...
- 2,089
2
votes
1
answer
167
views
graph built from orthogonal Latin Squares
I've asked the following question on MathExchange site, with a bounty, with no answer or comments. Maybe I would have additional comments here. The problem came to be while reading some articles on ...
-2
votes
2
answers
3k
views
Should the "L" in the term latin/Latin square be capitalized? [closed]
In Denes and Keedwell's book the word "latin" is not capitalized, and there seems to be some precedent in the literature for this usage. However, the vast majority of work on the subject ...
- 180
4
votes
1
answer
3k
views
Number of solutions and minimal clues in Sixy Sudoku
Sixy Sudoku is a variation on Latin squares and traditional sudoku played on a $6 \times 6$ grid with an initial clue of several cells filled in with a subset of the digits $1$–$6$. The task is to ...
- 2,558
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
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
5
votes
2
answers
211
views
Coloring in Combinatorial Design Generalizing Latin Square
I have a question about a combinatorial design very similar to a Latin Square, which is arising out of an open problem in graph theory. The design is an $n \times n$ matrix whose entries we want to ...
- 439
4
votes
1
answer
113
views
Bounding the number of orthogonal Latin squares from above
As is usual, let $N(n)$ denote the maximum size of a set of mutually orthogonal Latin squares of order $n$. I am wondering what results hold that bound $N(n)$ from above; the only ones I can think of ...
- 513
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
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
2
votes
1
answer
176
views
How to get Latin squares from a finite group and a subgroup
Let G be a finite group and we know its group table is a Latin square of order |G|. Now let H be any subgroup of G of index n. Then we can form G/H which is a collection of left cosets. My question is,...
- 163
1
vote
1
answer
113
views
Is there a way to estimate the number of Latin squares with a given autotopism?
An autotopism of a Latin square $L$ of order $n$ is a triple of permutations $(\alpha,\beta,\gamma)$ for which $L$ is stabilized after permuting the rows by $\alpha$, the columns by $\beta$, and the ...
- 1,327
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
2
answers
186
views
Do successive maximum permutations pick latin squares uniformly?
Suppose we start with a $n\times n$ matrix with entries sampled independently and uniformly at random from $[0,1]$. The weight of a set of entries will simply be the sum of those entries. A ...
- 85.6k
27
votes
1
answer
1k
views
What is the name of this combinatorial object and place to read about it?
The title is admittedly noninformative but I could not figure out how to squeeze into it the description of the object I am interested in. Judge by yourself.
I have an alphabet on $d$ symbols. I want ...
- 18.4k
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
2
votes
1
answer
170
views
Transformation between latin squares
Let $L\in R^{k\times k}$ a Latin square matrix.
Which is the most general form of $A\in R^{k\times k}$ such that
$$
A^TLA=L'
$$
with $L'$ another Latin square?
Thanks!
Fabio
- 329
2
votes
1
answer
259
views
How to generate a Latin square $M'$ in the same main class as $M \in \mathrm{LS}(9)$ which agrees with $L$ in the most cells?
I'm brainstorming an idea for storing a compressed list of main class representatives of Latin squares of order $9$. One way to compress the list would be to store one Latin square $L_1$, and for $i \...
- 1,327
6
votes
1
answer
164
views
For which divisors $a$ and $b$ of $n$ does there exist a Latin square of order $n$ that can be partitioned into $a \times b$ subrectangles?
There exists a Latin square of order $8$ which can be partitioned into $2 \times 4$ subrectangles:
$$
\begin{bmatrix}
\color{red} 1 & \color{red} 2 & \color{red} 3 & \color{red} 4 & \...
- 1,327
8
votes
1
answer
406
views
Determinant of symmetric Latin square
Let $n=2m$ be an even number. Let us construct $n\times n$ symmetric matrices $S_n$ in the following way. The entries are indeterminates $X_1,\ldots,X_{n-1}$. We choose a $1$-factorization of the ...
- 52.3k
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
1
answer
280
views
Creating a Latin rectangle from a projective plane
Given a projective plane I'd like to form a latin rectangle from the lines. In particular, I'd like to take each line from the plane, order the elements in some way, and stick them into the matrix as ...
- 175
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
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
4
votes
1
answer
191
views
Connections between loops (algebraic structure) and graphs
I would like to know whether there are known constructions which provide a bijection between loops (isomorphism classes) and (possibly directed) graphs. Any reference to a useful paper in this ...
- 143
7
votes
1
answer
544
views
Is there a simple proof that there is no five mutually orthogonal Latin squares of order 6?
It is well known that there is a projective plane of order $n$ if and only if
there exist a set of $n-1$ mutually orthogonal Latin squares. The first nontrivial
case is $n=6$, which fails because of ...
- 333
8
votes
2
answers
544
views
How many finite loops?
How many finite loops of order $n$ are there?
I am interested in the exact values of $n$ if $n <40$ or even reasonable estimates. I am also interested in formulae or bounds for all $n$.
Note ...
- 91
4
votes
1
answer
478
views
Are all symmetric idempotent Latin squares known?
Are all symmetric idempotent Latin squares known?
There is such a square of order $n$ if and only if $n$ is odd. However, is there a classification of all of them?
(The motivation for the question ...
- 6,962
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
3
votes
1
answer
131
views
A graph $G$ with two $K_6$ subgraphs, in which any one-factor of $G$ induces a one-factor in exactly one of the $K_6$ subgraphs?
I'm seeking a simple graph $G$ of the following type:
It contains two disjoint copies of $K_6$ (the complete graph on 6 nodes), $H$ and $H'$ say.
Any one-factor of $G$ must contain either (a) a one ...
- 4,229
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
20
votes
1
answer
1k
views
Symmetric polynomial from graphs
Let $g$ be a directed, connected multigraph, on $n$ vertices, without loops.
Define
$$P_g(x_1,\dots,x_n) := Sym\left[ \prod_{(i,j) \in g} (x_i-x_j) \right]$$
where $(i,j)$ is the directed edge ...
- 15.8k
3
votes
2
answers
414
views
What is the number of k-regular subgraphs of $K_{12,12}$?
I'm thinking about making an attempt at counting the number of Latin squares of order 12. Currently I'm in (what I call) the "sanity check" stage, where we check that the ranges that need searching ...
- 4,229