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

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$$.