37
votes
Accepted
What is the name of this combinatorial object and place to read about it?
What you're asking for is a code with two non-usual restrictions. It's a code over alphabet size $d$. You want each code word to have length $pd$ and you want to have $qd$ total code words.
The ...
- 2,720
19
votes
Does there exist a Latin square of order 9 for which its 9 broken diagonals and 9 broken antidiagonals are transversals?
Oh, I just realized how to prove non-existence for all $n \equiv 3 \pmod 6$.
We take the circulant and back-circulant Latin squares, defined as $L_{ij} = i+j \pmod n$ and $M_{ij} = i-j \pmod n$. ...
- 1,327
14
votes
Accepted
Does there exist a Latin square of order 9 for which its 9 broken diagonals and 9 broken antidiagonals are transversals?
I've verified with ILP that such Latin squares do not exist for $n\in\{9,15,21,27\}$.
The ILP formulation is based on binary indicator variables $p_{c,i,j}$ telling whether Latin square has character $...
- 34.3k
8
votes
Accepted
Evans conjecture for symmetric latin squares
No, when it comes to symmetric latin squares it is no longer true that as many as $n-1$ cells can be prescribed unconditionally. This is explained in the Ph.D. thesis of Matthew Henderson.
The key ...
- 188k
7
votes
Latin squares with one cycle type?
There are also "pan-Hamiltonian" Latin squares, see Perfect Factorisations of Bipartite Graphs and Latin Squares Without Proper Subrectangles by I. M. Wanless, Electronic J. Combin. 6 (1999),...
- 37.7k
6
votes
Accepted
Latin squares with one cycle type?
One way to achieve the required property is to construct a Latin square whose autotopism group acts transitively on unordered pairs of rows. This can be achieved for orders that are a prime power ...
- 341
6
votes
Should the "L" in the term latin/Latin square be capitalized?
English adjectives that derive from proper nouns are usually capitalised. However, over time, such an adjective can lose its capitalisation provided that it sufficiently departs from its origins in ...
- 364
5
votes
Accepted
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?
I eventually co-authored a paper which includes this topic. The non-trivial results are:
There exists a Latin square of order $n$ which decomposes into $2 \times (n/2)$ subrectangles for all even $n ...
- 1,327
3
votes
Accepted
Comparability of elements in a Latin square based on a few rows
The answer to the first question is that for some Latin squares of order $n$ (namely the addition table of a cyclic group) the minimum size of $\Pi'$ is $n$.
With addition modulo $n$, let $\pi_i=(i,i+...
- 13.4k
3
votes
Do successive maximum permutations pick latin squares uniformly?
Studying the results given in YBerman's answer gave me the following. Consider these two possibilities after drawing two symbols (in order) for $n=4$:
$$
\begin{align*}
A &= \begin{pmatrix}
1 &...
- 638
3
votes
Do successive maximum permutations pick latin squares uniformly?
I wanted to point out that there seems to be biases even in the set it does generate (regardless if that is all that is possible).
I know this is not a proof (and therefore not an answer), but I think ...
- 781
3
votes
Bounding the number of orthogonal Latin squares from above
Design Theory by Beth, Jungnickel & Lenz gives on page 724 the upper bounds
- 188k
3
votes
Accepted
How to get Latin squares from a finite group and a subgroup
I don't know of any general construction. Perhaps the most 'natural' examples are loop transversals: Given a left transversal $X$ to $H$ in $G$ with $1 \in X$, define a binary operation on $X$ by ...
- 4,728
2
votes
Number of solutions and minimal clues in Sixy Sudoku
As for the first question, a backtracking algorithm, see sixy.c at
https://github.com/wilberdk/sixy
shows there are 1936 completions of
$$\matrix{1&2&3&4&5&6\cr
*&*&*&...
- 3,504
2
votes
Accepted
Existence of latin squares with an involutory symmetry
To achieve your goal, we can use the "tensor product construction" for Latin squares. It is carried out as follows: Let $X_a$ be a latin square indexed by $a$, i.e. $X_a$ is a function $a \...
- 9,501
2
votes
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?
My coauthors and I created a canonical labelling method for Latin squares based on partial Latin squares in our paper: Fang, Stones, Marbach, Wang, Liu, Towards a Latin-Square Search Engine (pdf), ...
- 1,327
2
votes
Should the "L" in the term latin/Latin square be capitalized?
A close mathematician friend of mine used to try to stick to the rule of capitalizing any word that derives from a person's name: Noetherian (not "noetherian") ring, Abelian (not "abelian") group, etc....
1
vote
A bound on the number of partial transversals of a latin square
Here are some results for small $n$, obtained via integer linear programming.
$a_1 = 1$:
\begin{matrix}
1 \\
\end{matrix}
$a_2 = 0$:
\begin{matrix}
1 & 2 \\
2 & 1 \\
\end{matrix}
$a_3 = 3$:
\...
- 5,429
1
vote
The edge precoloring extension problem for complete graphs
Assuming that you mean to precolour $k$ subdiagonals and have no further constraints on the precolouring, the answer to both of your questions is no.
For every $n$ there is a precolouring which cannot ...
- 2,671
1
vote
The edge precoloring extension problem for complete graphs
For the case $n=8$, with the precoloring you describe the completion you give is indeed unique. I checked by writing the corresponding boolean program and let a solver enumerate all solutions: there ...
- 10.7k
1
vote
Accepted
graph built from orthogonal Latin Squares
Reposted answer from MathSE; seems like there's a little more attention here. Brendan McKay's comment settles the conjecture, and you addressed the coloring question. Here I have some comments on ...
- 4,589
1
vote
Coloring in Combinatorial Design Generalizing Latin Square
Hope I didn't misunderstand the question, but isn't this a counterexample (different letters correspond to different equivalence classes):
AAB
ACD
BDC
Each ...
- 5,590
1
vote
Is there a way to estimate the number of Latin squares with a given autotopism?
This is a dumb answer, and will not yield information quickly. I give it in hopes that it inspires smarter answers.
I use the triple form of representation for a Latin square, which is a collection ...
- 13k
Only top scored, non community-wiki answers of a minimum length are eligible