search

Lunches

Digital materials and aerospace applications Wed, Dec 14, 2016 14:30 CET

Speakers: Irina Kostitsyna

Wed, Dec 7, 2016 12:00 CET

Speakers: Michele Conforti

Characterizing Polytopes Contained in the 0/1-Cube with Bounded Chvatal-Gomory Rank Wed, Nov 30, 2016 12:00 CET

Speakers: Samuel Fiorini

Transfinite Ford-Fulkerson on a Finite Network Wed, Nov 23, 2016 12:00 CET

Speakers: Tony Huynh

Today Tony will tell us about Transfinite Ford-Fulkerson on a Finite Network.

Comparison of real roots (without numerical approximations) Wed, Nov 16, 2016 12:00 CET

Speakers: Aurélien Ooms

Recognizing visibility graphs of polygons with holes is hard for the existential theory of the reals Wed, Nov 9, 2016 12:30 CET

Speakers: Udo Hoffmann

The sandpile model on K_{m,n} and the rank of its configurations Wed, Oct 19, 2016 14:15 CEST

Speakers: Michele D'Adderio

Mon, Jan 1, 0001 00:17 LMT

date: 2019-10-16T10:30:00.000Z title: 'Using hard-core distributions for sparse graph colouring' speakers: François Pirot duration: PT1H location: Plaine campus, NO building, 8th floor, Rotule (P.2NO8.08) geolocation: latitude: 50.82005 longitude: 4.39767 tags: Graphs Coloring Graph Coloring Sparse Graphs Writing \(\mathcal{I}(G)\) for the collection of independent sets of a given graph \(G\), a random independent set \(\mathcal{B}\) drawn according to the hard-core distribution at fugacity \(\lambda\) on \(\mathcal{I}(G)\) satisfies for every independent set \(I\in \mathcal{I}(G)\) that \(\Pr[\mathcal{B} = I] = \frac{\lambda^{|I|}}{Z_\lambda(G)}\), where \(Z_\lambda(G) = \sum_{I\in \mathcal{I}(G)} \lambda^{|I|}\) is a normalising factor, called the independence polynomial of \(G\).