Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

Research lectures, seminars and events

The events listed in this area are research seminars, workshops and lectures hosted by Durham University departments and research institutes. If you are not a member of the University, but  wish to enquire about attending one of the events please contact the organiser or host department.


 

January 2020
SunMonTueWedThuFriSat
December 2019 February 2020
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

Events for 14 January 2020

Marcin Wrochna: Applying topology in graph colouring and constraint satisfaction problems

1:00pm, E245

I will present several applications of topology in graph colouring and related problems, from classical lower bounds on chromatic numbers of graphs, through toy examples in statistical physics, to recent results in hardness of approximation. Surprisingly, even though the questions are purely combinatorial, topology turns out to give elegant solutions, and is sometimes provably unavoidable, in some technical sense. No knowledge of topology assumed. Based on joint work with Stanislav Zivny, Andrei Krokhin, and Jakub Oprsal.

Contact algorithms.complexity@dur.ac.uk for more information about this event.