============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Counting perfect matchings of cubic graphs in 
             the geometric dual
            
Palestrante: Marcos Kiwi
             Universidade do Chile

Hora e Data: 14h, sexta-feira, 23 de setembro de 2011

Local:       auditório do NUMEC

Resumo:

A well-known  conjecture of Lovász and Plummer  from the mid
70's claims  that for every  cubic graph G with  no cutedge,
the  number of  perfect  matchings in  G  is exponential  in
|V(G)|.   The   conjecture  was  very   recently  positively
settled.   In  this talk  we  will  describe an  alternative
approach  for  trying to  prove  the conjecture/theorem  and
illustrate its  application in order to show  that any cubic
planar  graph  G  whose  geometric  dual graph  is  a  stack
triangulation     (planar    3-tree),    has     at    least
3\varphi^{|V(G)|/72}   distinct  perfect   matchings,  where
\varphi \approx 1.6180 denotes the golden ratio.

Our approach  relies in techniques  developed in statystical
physics, and leads to both computational and graph theoretic
questions concerning  the so called  antiferromagnetic Ising
model  on  irregular  lattices.   Time  allowing,  we  shall
address some of these questions.

The talk  will survey joint work with  Martin Loebl (Charles
U.)  and Andrea Jiménez (U.~Chile).