All Questions
Tagged with latin-square co.combinatorics
19 questions with no upvoted or accepted answers
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,229
12
votes
0
answers
513
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 $...
- 43.2k
12
votes
0
answers
258
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,229
10
votes
0
answers
141
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,350
8
votes
0
answers
88
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,327
7
votes
0
answers
190
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 ...
- 13.4k
5
votes
0
answers
105
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 ...
- 2,089
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$-...
- 1,643
5
votes
0
answers
184
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,229
4
votes
0
answers
114
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,327
4
votes
0
answers
191
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 ...
- 15.6k
3
votes
0
answers
131
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 &...
- 1,327
2
votes
0
answers
132
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 ...
- 21
2
votes
1
answer
189
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,251
2
votes
0
answers
68
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,327
1
vote
0
answers
41
views
Unexpected non-uniformity of results from some implementations of Jacobson-Matthews seem to show a strange sensitivity to isotopy class
Questions
Why do some Jacobson-Matthews (J-M) implementations for generating random latin squares exhibit frequencies inconsistent with an underlying uniform distribution?
Further investigation ...
- 41
1
vote
0
answers
26
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 ...
- 41
1
vote
0
answers
115
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 ...
- 11
1
vote
0
answers
383
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,558