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
1answer
77 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
2answers
505 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 ...
3
votes
1answer
2k 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 ...
4
votes
0answers
81 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
vote
1answer
56 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 ...
5
votes
2answers
132 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 ...
3
votes
1answer
57 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 ...
1
vote
0answers
157 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$ ...
4
votes
0answers
71 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 ...
4
votes
0answers
167 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
134 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
103 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
70 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
161 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 ...
12
votes
0answers
480 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 $...
2
votes
1answer
116 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
231 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
116 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
345 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
60 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
237 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
171 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
127 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
156 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
329 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
456 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
345 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
210 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
168 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
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 ...
3
votes
2answers
363 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 ...
8
votes
1answer
730 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 ...
13
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
509 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(...