tailieunhanh - Báo cáo toán học: "The Induced Subgraph Order on Unlabelled Graphs"

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: The Induced Subgraph Order on Unlabelled Graphs. | The Induced Subgraph Order on Unlabelled Graphs Craig A. Sloss Department of Combinatorics and Optimization University of Waterloo Ontario Canada csloss@ Submitted Jul 31 2006 Accepted Oct 17 2006 Published Oct 27 2006 Mathematics Subject Classification 06A07 Abstract A differential poset is a partially ordered set with raising and lowering operators U and D which satisfy the commutation relation DU UD rl for some constant r. This notion may be generalized to deal with the case in which there exist sequences of constants qn n 0 and rn n 0 such that for any poset element x of rank n DU x qnUD x rnx. Here we introduce natural raising and lowering operators such that the set of unlabelled graphs ordered by G H if and only if G is isomorphic to an induced subgraph of H is a generalized differential poset with qn 2 and rn 2 . This allows one to apply a number of enumerative results regarding walk enumeration to the poset of induced subgraphs. 1 Introduction The class of posets known as differential posets were first introduced and studied by Stanley 3 . Generalizations of this class of posets were studied by Stanley 4 and Fomin 1 . A number of examples of generalized differential posets are given in these papers. Another example a poset of rooted unlabelled trees was recently introduced by Hoffman 2 . In the present paper we discuss a new example of a generalized differential poset namely the induced subgraph order on isomorphism classes of graphs. These results could potentially have applications to the analysis of dynamic algorithms in which vertices are added or removed from graphs in an unrestricted manner. 2 Definitions and Terminology Let P be a locally finite ranked partially ordered set with least element 0 and finitely many elements of each rank. For X y 2 P we say that y covers X if X y and for any Supported by the Natural Sciences and Engineering Research Council of Canada through its postgraduate scholarship program. THE ELECTRONIC JOURNAL .