University of Cambridge > > Combinatorics Seminar > On the chromatic number of a sparse random hypergraph

On the chromatic number of a sparse random hypergraph

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

  • UserDmitry Shabanov (Moscow)
  • ClockThursday 05 October 2017, 16:00-17:00
  • HouseMR12.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity