TAILIEUCHUNG - Báo cáo toán học: "Ehrhart clutters: Regularity and Max-Flow Min-Cut"

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: Ehrhart clutters: Regularity and Max-Flow Min-Cut. | Ehrhart clutters Regularity and Max-Flow Min-Cut Jose Martinez-Bernal Departamento de Matemáticas Centro de Investigacion y de Estudios Avanzados del IPN Apartado Postal 14-740 07000 Mexico City . jmb@ Edwin O Shea Departamento de Matemáaticas Centro de Investigaciáon y de Estudios Avanzados del IPN Apartado Postal 14-740 07000 Mexico City . edwin@ Rafael H. Villarreal Departamento de Matemaáticas Centro de Investigaciáon y de Estudios Avanzados del IPN Apartado Postal 14-740 07000 Mexico City . vila@ Submitted Mar 16 2009 Accepted Mar 15 2010 Published Mar 29 2010 Mathematics Subject Classifications 13H10 52B20 13D02 90C47 05C17 05C65. Abstract If C is a clutter with n vertices and q edges whose clutter matrix has column vectors A v1 . vq we call C an Ehrhart clutter if v1 1 . vq 1 c 0 1 n 1 is a Hilbert basis. Letting A P be the Ehrhart ring of P conv A we are able to show that if C is a uniform unmixed MFMC clutter then C is an Ehrhart clutter and in this case we provide sharp upper bounds on the Castelnuovo-Mumford regularity and the a-invariant of A P . Motivated by the Conforti-Cornuejols conjecture on packing problems we conjecture that if C is both ideal and the clique clutter of a perfect graph then C has the MFMC property. We prove this conjecture for Meyniel graphs by showing that the clique clutters of Meyniel graphs are Ehrhart clutters. In much the same spirit we provide a simple proof of our conjecture when C is a uniform clique clutter of a perfect graph. We close with a generalization of Ehrhart clutters as it relates to total dual integrality. Partially supported by SNI. tPartially supported by CONACyT grant 49251-F and SNI. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R52 1 1 Introduction A clutter C is a family E of subsets of a finite ground set X such that if S1 S2 G E then S1 c S2. The ground set X is called the vertex set of C and E is called the edge set of C they are denoted by

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học