On the relations of various conjectures on Latin squares and straightening coefficients
type: Item
instance of: scholarly article
title: On the relations of various conjectures on Latin squares and straightening coefficients
zbMATH Open document ID: 0797.05019
DOI: 10.1016/0012-365X(94)90114-7
author: Rosa Q. Huang
author: Gian-Carlo Rota
published in: Discrete Mathematics
publication date: 1994-10-10T00:00:00Z
review text: This paper discusses the relations among several combinatorial conjectures. 1. (Dinitz, 1978). Associate to each pair \((k,j)\) where \(1\leq i\), \(j\leq n\) a set \(S_{ij}\) of size \(n\). Then there exists a partial Latin square \(A=(a_{ij})\) with \(a_{i,j}\in S_{ij}\) for all pairs \((i,j)\). 2. (Alon and Tarsi, 1986). If \(n\) is even, then ELS\((n)\neq\text{OLS}(n)\) where ELS\((n)\) is the number of even Latin squares of side \(n\) and OLS\((n)\) is the number of odd Latin squares of side \(n\). 3. If \(n\) is even, then RELS\((n)\neq\text{ROLS}(n)\) where RELS\((n)\) is the number of row even Latin squares of side \(n\) (i.e. the total number of row inversions is even) and ROLS\((n)\) is the number of row odd Latin squares. 4. (Rota, 1989). Let \(V\) be a vector space over an arbitrary infinite field. Suppose \(B_ 1,B_ 2\ldots,B_ n\) are \(n\) sets of bases of \(V\). Then for each \(i\), there is a linear order of \(B_ i\), say \(B_ 1=\{a_ 1,a_ 2,\ldots,a_ n\}\), \(B_ 2=\{b_ 1,b_ 2,\ldots,b_ n\},\ldots\), \(B_ n=\{c_ 1,c_ 2,\ldots,c_ n\}\) such that the sets \(C_ 1=\{a_ 1,b_ 1,\ldots,c_ 1\}\) and \(C_ 2=\{a_ 2,b_ 2,\ldots,c_ 2\},\ldots\), \(C_ n=\{a_ n,b_ n,\ldots,c_ n\}\) are \(n\) sets of bases of \(V\). 5. (Rota, 1989). Let Bracket\([L^ +]\) be the bracket algebra of rank \(n\) on a set \(L^ +\) of positive letters. If \(n\) is even, then \([ab\cdots c]\in\text{Bracket}[L^ +]\) is nonzero whenever \(a,b,\ldots,c\) are \(n\) distinct letters in \(L^ +\). In this paper it is shown that (a) Conjecture \(5\Leftrightarrow\) Conjecture \(3\Leftrightarrow\) Conjecture 2, (b) Conjecture \(5\Rightarrow\) Conjecture 4 (for \(n\) even), and (c) Conjecture \(2\Rightarrow\) Conjecture 1 (for \(n\) even). The techniques involve the use of straightening coefficients in the bracket algebra, the use of umbral linear operators, and the use of a theorem of Alon and Tarsi on list colorings of graphs. Note: Conjecture 1 has recently been proven by \textit{Fred Galvin} [The l…
Mathematics Subject Classification ID: 05B15
Mathematics Subject Classification ID: 05E99
zbMATH DE Number: 562593
zbMATH Keywords: Latin square
zbMATH Keywords: bracket algebra
zbMATH Keywords: straightening coefficients
zbMATH Keywords: umbral linear operators
zbMATH Keywords: list colorings
Wikidata QID: Q122932579
reviewed by: J. H. Dinitz
MaRDI profile type: Publication
cites work: Colorings and orientations of graphs
cites work: A note on list-colorings
cites work: Invariant theory, Young bitableaux, and combinatorics
cites work: On the Foundations of Combinatorial Theory: IX Combinatorial Methods in Invariant Theory
cites work: Q3792822
cites work: Supersymmetric bracket algebra and invariant theory
cites work: Q4326643
full work available at URL: 0012-365x(94)90114-7
OpenAlex ID: W2082199499
description: scientific article; zbMATH DE number 562593