Friday, November 14, 2008 — 3:30 PM to 4:30 PM EST

On the chromatic number of random d-regular graphs

Speaker: Nick Wormald
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Achlioptas and Moore have announced a proof that random d-regular graphs asymptotically almost surely (a.a.s.) have chromatic number k-1, k, or k+1 where k is the smallest integer satisfying d < 2(k-1)\log(k-1). For about half the values of d, they showed it was k or k+1. We have shown that a.a.s. it is not k+1, which determines the chromatic number a.a.s. for about half the values of d. The proof applies the small subgraph conditioning method to the number of balanced k-colourings, where a colouring is balanced if the number of vertices of each colour is equal, and makes essential use of some of the earlier work of Achlioptas and Naor.

This is joint work with Graeme Kemkes and Xavier Perez.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2019 (139)
    1. October (10)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)