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).
1
vote
0answers
87 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$ ...
3
votes
0answers
48 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 ...
3
votes
0answers
158 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 ...
2
votes
1answer
117 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,...
1
vote
1answer
100 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 ...
8
votes
0answers
61 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). ...
7
votes
2answers
149 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 ...
27
votes
1answer
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 ...
11
votes
0answers
461 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 $...
0
votes
0answers
61 views
Set of equivalent Latin squares closed under matrix multiplication
Let $L$ a set of $k$ matrices of dimension $k\times k$, $L=(L_1,\cdots,L_k)$, such that:
1) each matrix is a Latin Square.
2) each matrix can be transformed into another by a change of the symbols (...
2
votes
1answer
95 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
2
votes
1answer
225 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 \...
5
votes
0answers
114 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 & \...
8
votes
1answer
310 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 ...
2
votes
0answers
57 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
vote
1answer
222 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 ...
7
votes
0answers
168 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 ...
5
votes
0answers
119 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$-...
3
votes
1answer
147 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 ...
7
votes
1answer
280 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 ...
7
votes
2answers
428 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 ...
4
votes
1answer
306 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 ...
12
votes
0answers
190 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 ...
5
votes
0answers
161 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$-...
19
votes
1answer
973 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 ...
3
votes
2answers
358 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 ...
7
votes
1answer
684 views
(0,1)-matrix congruence: is it known?
[[UPDATE: This work has now been published at SIAM J Discrete Math.: Formulae for the Alon–Tarsi Conjecture.]]
By equating two formulae (one congruence by Glynn (1) (which has just appeared) and one ...
12
votes
0answers
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
votes
1answer
492 views
Diagonally-cyclic Steiner Latin squares
A Steiner triple system is a decomposition of $K_n$ into $K_3$, such as $S=\{013,026,045,124,156,235,346\}$. Steiner triple systems give rise to a Steiner Latin squares, such as $L$ below.
\[L=\left(...
