Colloquium Mathematics, Prof. Roberto Fernandez

 

Join us for coffee and tea at 15.45 p.m.

 

 

Date: Tuesday, March 13^th 2012

Speaker: Prof. Roberto Fernandez

Room: 5161.0267 (Bernoulliborg)

Time: 16.15

 

 

 

 

Title: Improvement of the Lov\'{a}sz Local Lemma via

         Cluster Expansion

 

 

Abstract:  

 

Shearer observed that the Lov\'asz Local Lemma is related with the independent set polynomial on graphs. Scott and Sokal showed that the latter, coincide with the partition function of the hard core lattice gas on graphs. The logarithm of this partition function is the natural object for the application of cluster expansion techniques.  Through this chain of arguments, better convergence conditions for cluster expansions translate into an improved version of the Lov\'asz Local Lemma.  I will discuss the latest version of the lemma obtained from the strongest results available for cluster expansions.  As applications I will present bounds on conditions for the existence of independent sets for partitions of vertices, $k$-SAT families of clauses and latin transversal matrices.

 

 

 

 

 

 

Colloquium coordinators are Prof.dr. A.C.D. van Enter (e-mail : A.C.D.van.Enter@rug.nl) and

Dr. A.V. Kiselev (e-mail: a.v.kiselev rug.nl )