Another sensation – Annika Heckel: Non-concentration of the chromatic number of a random graph

Annika Heckel

Sorry for the long period of non blogging. There are a lot of things to report and  various other plans for posts and I hope to come back to it soon. But it is nice to break the silence with another sensational result by Annika Heckel. I first heard about it some time ago and Noam Lifshitz just informed be that the paper is on the arXive!

Non-concentration of the chromatic number of a random graph

And here is the abstract: We show that the chromatic number of $latex G(n,1/2)$ is not concentrated on fewer than n^{1/4-\epsilon}  consecutive values. This addresses a longstanding question raised by Erdős and several other authors.

The Introduction tells the history of the problem very nicely.

This entry was posted in Combinatorics and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s