A logarithmic approximation of linearly-ordered colourings
<|reference_start|>A logarithmic approximation of linearly-ordered colourings: A linearly ordered (LO) $k$-colouring of a hypergraph assigns to each vertex a colour from the set $\{0,1,\ldots,k-1\}$ in such a way that each hyperedge has a unique maximum element. Barto, Batistelli, and Berg conjectured that it is NP-hard to find an LO $k$-colouring of an LO 2-colourable 3-uniform hypergraph for any constant $k\geq 2$ [STACS'21] but even the case $k=3$ is still open. Nakajima and \v{Z}ivn\'{y} gave polynomial-time algorithms for finding, given an LO 2-colourable 3-uniform hypergraph, an LO colouring with $O^*(\sqrt{n})$ colours [ICALP'22] and an LO colouring with $O^*(\sqrt[3]{n})$ colours [ACM ToCT'23]. Very recently, Louis, Newman, and Ray gave an SDP-based algorithm with $O^*(\sqrt[5]{n})$ colours. We present two simple polynomial-time algorithms that find an LO colouring with $O(\log_2(n))$ colours, which is an exponential improvement.<|reference_end|>
@article{håstad2024a,
    title={A logarithmic approximation of linearly ordered colourings},
    author={Johan H{aa}stad and Bj"orn Martinsson and Tamio-Vesa Nakajima and
  Stanislav v{Z}ivn'y},
    journal={arXiv preprint arXiv:2404.19556},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.19556},
    primaryClass={math.CO cs.DM cs.DS}
}