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).
43
questions
9
votes
2
answers
627
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,149
8
votes
3
answers
376
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\\...
- 158
1
vote
3
answers
170
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
24
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,025
10
votes
0
answers
111
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,240
3
votes
1
answer
198
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 ...
- 1,701
2
votes
2
answers
197
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 ...
- 1,701
2
votes
1
answer
106
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 ...
0
votes
2
answers
2k
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 capitalizes ...
- 168
3
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,498
4
votes
0
answers
93
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 ...
- 1,701
2
votes
1
answer
102
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,029
5
votes
2
answers
158
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 ...
- 389
4
votes
1
answer
74
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 ...
- 483
1
vote
0
answers
288
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,498
4
votes
0
answers
88
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,149
4
votes
0
answers
176
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 ...
- 13k
2
votes
1
answer
158
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,...
- 123
1
vote
1
answer
105
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,149
8
votes
0
answers
80
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,149
7
votes
2
answers
170
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 ...
- 82.1k
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 ...
- 16.2k
12
votes
0
answers
500
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 $...
- 38.3k
2
votes
1
answer
142
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
- 299
2
votes
1
answer
233
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,149
6
votes
1
answer
149
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,149
8
votes
1
answer
374
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 ...
- 47.5k
2
votes
0
answers
62
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,149
1
vote
1
answer
244
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
178
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 ...
- 12.6k
5
votes
0
answers
135
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,314
4
votes
1
answer
172
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
395
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
7
votes
2
answers
477
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 ...
- 81
4
votes
1
answer
379
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,614
12
votes
0
answers
235
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,063
3
votes
1
answer
123
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,063
5
votes
0
answers
176
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,063
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 ...
- 14.5k
3
votes
2
answers
372
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,063
8
votes
1
answer
771
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 ...
- 4,063
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,063
4
votes
1
answer
526
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(...
- 4,063