TAILIEUCHUNG - Báo cáo toán học: " Cyclic Sieving Phenomenon in Non-Crossing Connected Graphs"

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: Cyclic Sieving Phenomenon in Non-Crossing Connected Graphs. | Cyclic Sieving Phenomenon in Non-Crossing Connected Graphs Alan Guo Department of Mathematics Duke University Durham North Carolina USA Submitted Jul 27 2010 Accepted Dec 15 2010 Published Jan 5 2011 Mathematics Subject Classification 05A15 primary 05C30 secondary Abstract A non-crossing connected graph is a connected graph on vertices arranged in a circle such that its edges do not cross. The count for such graphs can be made naturally into a q-binomial generating function. We prove that this generating function exhibits the cyclic sieving phenomenon as conjectured by . Eu. 1 Introduction A non-crossing graph on a finite set S is a graph with vertices indexed by S arranged in a circle such that no edges cross. When we say a graph on n vertices we will mean S 1 . n . In 3 Flajolet and Noy showed that the number cn k of non-crossing connected graphs see Figure 1 on n vertices with k edges n 1 k 2n 3 is cn k 3n 3 k 1 n k n 2 . 1 n 1 1 Define n n q kj q k q n k q where n q n q n 1 q 1 q and n q 1 q -- qn 1 admits a natural q-analogue k n. The formula in 1 c n k q 1 n 1 q 3n 3 k 1 n kJ q _n 2 2 q THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P9 1 Figure 1 A non-crossing connected graph on 12 vertices with 14 edges It turns out that c n k q is a polynomial in q with nonnegative integer coefficients see Proposition below. The main result of this paper is the following which was conjectured by . Eu 1 . Theorem . Let n 1 and n 1 k 2n 3 and let X be the set of non-crossing connected graphs on n vertices with k edges. If d 1 divides n and w is a primitive d-th root of unity then c n k w sd n k where we define 1 Sd n k 2n x G X x is fixed under rotation by d In 4 Reiner Stanton and White introduced the notion of the cyclic sieving phenomenon. A triple X X q C consisting of a finite set X a polynomial X q G N q satisfying X 1 X and a cyclic group C acting on X exhibits the cyclic sieving phenomenon if for every c G C if w is a primitive root

• 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