On the chromatic number of a sparse random hypergraph

Add to your list(s) Download to your calendar using vCal

• Dmitry Shabanov (Moscow)
• Thursday 05 October 2017, 16:00-17:00
• MR12.

If you have a question about this talk, please contact Andrew Thomason.

The talk deals with estimating the probability threshold for r-colorability of a random hypergraph. Let H(n,k,p) denote the classical binomial model of a random k-uniform hypergraph: every edge of a complete k-uniform hypergraph on n vertices is included into H(n,k,p) independently with probability p.

We study the question of estimating the probability threshold for the r-colorability property of H(n,k,p). It is well known that for fixed r>=2 and $k>=2, this threshold appears in the sparse case when the expected number of edges is a linear function cn for some fixed c>0.

We will present a new lower bound for the r-colorability threshold which improves previous result of Dyer, Frieze and Greenhill (2015) and provides a bounded gap with the known upper bound. For the case r>>k, a slightly better result was recently obtained by Ayre, Coja-Oghlan and Greenhill (2015+).

The proof of the main result is based on a new approach to the second moment method. We will also discuss the applications of the used technique to the non-classical colorings of random hypergraphs.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.