Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Satisfying states of triangulations of a convex n-gon. | Satisfying states of triangulations of a convex n-gon A. Jimenez Departamento de Ingenieria Matematica Universidad de Chile ajimenez@ M. Kiwi 1 Departamento de Ingeniería Matemática Centro de Modelamiento Matematico UMI 2807 CNRS-UChile Universidad de Chile mkiwi M. Loeblỉ Department of Applied Mathematics Institute for Theorical Computer Science Charles University loebl Submitted Dec 23 2009 Accepted Feb 26 2010 Published Mar 8 2010 Mathematics Subject Classification 05C30 Abstract In this work we count the number of satisfying states of triangulations of a convex n-gon using the transfer matrix method. We show an exponential in n lower bound. We also give the exact formula for the number of satisfying states of a strip of triangles. 1 Introduction A classic theorem of Petersen claims that every cubic each degree 3 graph with no cutedge has a perfect matching. A well-known conjecture of Lovasz and Plummer from the Gratefully acknowledges the support of Mecesup via UCH0607 Project CONICYT via Basal-FONDAP in Applied Mathematics FONDECYT 1090227 and the partial support of the Czech Research Grant MSM 0021620838 while visiting KAM MFF UK. 1 Gratefully acknowledges the support of CONICYT via Basal-FONDAP in Applied Mathematics and FONDECYT 1090227. Partially supported by Basal project Centro de Modelamiento Matematico Universidad de Chile. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R39 1 mid-1970 s still open asserts that for every cubic graph G with no cutedge the number of perfect matchings of G is exponential in V G . The assertion of the conjecture was proved for the k regular bipartite graphs by Schrijver Sch98 and for the planar graphs by Chudnovsky and Seymour CS08 . Both of these results are difficult. In general the conjecture is widely open see KSS08 for a linear lower bound obtained so far. We suggest to study the conjecture of Lovasz and Plummer in the dual setting. This relates the conjecture to a .
