The optimal edge-colouring threshold

arXiv2212.04397MaRDI QIDQ6419987FDOQ6419987

Publication date: 8 December 2022

Abstract: Consider any dense r-regular quasirandom bipartite graph H with parts of size n and fix a set of r colours. Let L be a random list assignment where each colour is available for each edge of H with probability p. We show that the threshold probability for H to have a proper L-edge-colouring is p of order (log n)/n. This answers a question of Kang, Kelly, K"uhn, Methuku and Osthus. We thus obtain the same threshold for Steiner Triple Systems and Latin squares; the latter answers a question of Johanssen from 2006.

This page was built for publication: The optimal edge-colouring threshold

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6419987)