On the relations of various conjectures on Latin squares and straightening coefficients (Q1322185): Difference between revisions

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 list chromatic index of a bipartite mutligraph, preprint]. Indeed, the more general result that for the line graph \(L(G)\) of any bipartite graph \(\chi_ \ell'(G)=\chi'(G)\) is established. The proof uses none of the techniques of this paper.