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).

Filter by
Sorted by
Tagged with
2 votes
0 answers
100 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 ...
Milo B's user avatar
  • 21
1 vote
1 answer
108 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) ...
John's user avatar
  • 161
1 vote
0 answers
24 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 ...
John Palmer's user avatar
0 votes
0 answers
120 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 ...
Daniel Sebald's user avatar
1 vote
0 answers
109 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 ...
Lim do's user avatar
  • 11
2 votes
1 answer
69 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 ...
John Palmer's user avatar
3 votes
0 answers
123 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 &...
Rebecca J. Stones's user avatar
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 ...
Rebecca J. Stones's user avatar
8 votes
3 answers
416 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\\...
user1020406's user avatar
1 vote
3 answers
185 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,...
Martín's user avatar
  • 93
1 vote
0 answers
31 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 ...
saolof's user avatar
  • 1,823
10 votes
0 answers
133 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 ...
András Salamon's user avatar
3 votes
1 answer
263 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 ...
vidyarthi's user avatar
  • 2,007
2 votes
2 answers
215 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 ...
vidyarthi's user avatar
  • 2,007
2 votes
1 answer
139 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 ...
Thomas Lesgourgues's user avatar
-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 ...
KcH's user avatar
  • 180
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 ...
David G. Stork's user avatar
5 votes
0 answers
101 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 ...
vidyarthi's user avatar
  • 2,007
2 votes
1 answer
157 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 ...
Hans's user avatar
  • 2,169
5 votes
2 answers
194 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 ...
John Samples's user avatar
4 votes
1 answer
90 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 ...
Nathaniel Butler's user avatar
1 vote
0 answers
367 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$ ...
David G. Stork's user avatar
4 votes
0 answers
102 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 ...
Rebecca J. Stones's user avatar
4 votes
0 answers
186 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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
2 votes
1 answer
168 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,...
Anupam Ah's user avatar
  • 163
1 vote
1 answer
112 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 ...
Rebecca J. Stones's user avatar
8 votes
0 answers
86 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). ...
Rebecca J. Stones's user avatar
7 votes
2 answers
180 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 ...
Gjergji Zaimi's user avatar
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 ...
მამუკა ჯიბლაძე's user avatar
12 votes
0 answers
510 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 $...
T. Amdeberhan's user avatar
2 votes
1 answer
166 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
Fabio's user avatar
  • 329
2 votes
1 answer
254 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 \...
Rebecca J. Stones's user avatar
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 & \...
Rebecca J. Stones's user avatar
8 votes
1 answer
399 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 ...
Denis Serre's user avatar
  • 51.5k
2 votes
0 answers
66 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 ...
Rebecca J. Stones's user avatar
1 vote
1 answer
258 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 ...
user43928's user avatar
  • 175
7 votes
0 answers
188 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 ...
Wolfgang's user avatar
  • 13.2k
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$-...
Zur Luria's user avatar
  • 1,613
4 votes
1 answer
187 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 ...
Stefan Gyürki's user avatar
7 votes
1 answer
483 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 ...
Arimakat's user avatar
  • 333
8 votes
2 answers
541 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 ...
user44255's user avatar
4 votes
1 answer
454 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 ...
Felix Goldberg's user avatar
12 votes
0 answers
255 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 ...
Douglas S. Stones's user avatar
3 votes
1 answer
129 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 ...
Douglas S. Stones's user avatar
5 votes
0 answers
181 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$-...
Douglas S. Stones's user avatar
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 ...
Per Alexandersson's user avatar
3 votes
2 answers
405 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 ...
Douglas S. Stones's user avatar
8 votes
1 answer
803 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 ...
Douglas S. Stones's user avatar
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 ...
Douglas S. Stones's user avatar
4 votes
1 answer
534 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(...
Douglas S. Stones's user avatar