The chromatic number of finite group Cayley tables (Q1732031)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The chromatic number of finite group Cayley tables |
scientific article |
Statements
The chromatic number of finite group Cayley tables (English)
0 references
15 March 2019
0 references
Summary: The chromatic number of a Latin square \(L\), denoted \(_\chi(L)\), is the minimum number of partial transversals needed to cover all of its cells. It has been conjectured that every Latin square satisfies \(_\chi(L) \leq |L|+2\). If true, this would resolve a longstanding conjecture -- commonly attributed to Brualdi -- that every Latin square has a partial transversal of size \(|L|-1\). Restricting our attention to Cayley tables of finite groups, we prove two results. First, we resolve the chromatic number question for Cayley tables of finite abelian groups: the Cayley table of an abelian group \(G\) has chromatic number \(|G|\) or \(|G|+2\), with the latter case occurring if and only if \(G\) has nontrivial cyclic Sylow 2-subgroups. Second, we give an upper bound for the chromatic number of Cayley tables of arbitrary finite groups. For \(|G|\geq 3\), this improves the best-known general upper bound from \(2|G|\) to \(\frac{3}{2}|G|\), while yielding an even stronger result in infinitely many cases.
0 references