tailieunhanh - Báo cáo toán học: "A Gessel–Viennot-Type Method for Cycle Systems in a Directed Graph"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A Gessel–Viennot-Type Method for Cycle Systems in a Directed Graph. | A Gessel-Viennot-Type Method for Cycle Systems in a Directed Graph Christopher R. H. Hanusa Department of Mathematical Sciences Binghamton University Binghamton New York USA chanusa@ Submitted Nov 28 2005 Accepted Mar 31 2006 Published Apr 4 2006 Mathematics Subject Classifications Primary 05B45 05C30 Secondary 05A15 05B20 05C38 05C50 05C70 11A51 11B83 15A15 15A36 52C20 Keywords directed graph cycle system path system walk system Aztec diamond Aztec pillow Hamburger Theorem Kasteleyn-Percus Gessel-Viennot Schroder numbers Abstract We introduce a new determinantal method to count cycle systems in a directed graph that generalizes Gessel and Viennot s determinantal method on path systems. The method gives new insight into the enumeration of domino tilings of Aztec diamonds Aztec pillows and related regions. 1 Introduction In this article we present an analogue of the Gessel-Viennot method for counting cycle systems on a type of directed graph we call a hamburger graph. A hamburger graph H is made up of two acyclic graphs G1 and G2 and a connecting edge set E3 with the following properties. The graph G1 has k distinguished vertices v- .-. Vk with directed paths from Vi to Vj only if i j. The graph G2 has k distinguished vertices wk 1 . w2k with directed paths from wi to Wj only if i j. The edge set E3 connects the vertices vi and wk i by way of edges ei vi wk i and ei wk i vi. See Figure 1 for a visualization. Hamburger graphs arise naturally in the study of Aztec diamonds as explained in Section 5. The Gessel-Viennot method is a determinantal method to count path systems in an acyclic directed graph G with k sources s1 . sk and k sinks t1 . tk. A path system P is a collection of k vertex-disjoint paths each one directed from si to tơ i for some permutation Ơ 2 Sk where Sk is the symmetric group on k elements . Call a path system P positive if the sign of this permutation Ơ satisfies sgn a 1 and negative if sgn a 1. Let p be the number of positive .