Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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