The chromatic number is a fundamental graph parameter. It is defined as the minimum number of colours needed for a vertex colouring where neighbouring vertices are always coloured differently.
How much does the chromatic number of the random graph G(n, 1/2) vary? Shamir and Spencer proved that it is contained in some sequence of intervals of length about $n^{(1/2)}$. Alon improved this slightly to $n^{(1/2)} / \log n$. Until recently, however, no lower bounds on the fluctuations of the chromatic number of G(n, 1/2) were known, even though the question was raised by Bollobás many years ago. I will talk about the main ideas needed to prove that, at least for infinitely many n, the chromatic number of G(n, 1/2) is not concentrated on fewer than $n^{(1/2-o(1))}$ consecutive values.
I will also discuss the Zigzag Conjecture, made recently by Bollobás, Heckel, Morris, Panagiotou, Riordan and Smith: this proposes that the correct concentration interval length 'zigzags' between $n^{(1/4+o(1))}$ and $n^{(1/2+o(1))}$, depending on n.
Joint work with Oliver Riordan.
Angelegt am Monday, 17.05.2021 16:19 von Anita Kollwitz
Geändert am Tuesday, 08.06.2021 10:57 von Anita Kollwitz
[Edit | Vorlage]