Bell Numbers of Graphs by Bryce Duncan A dissertation submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama May 7, 2012 Keywords: Graph Theory, Vertex Partitions, Enumeration Copyright 2012 by Bryce Duncan Approved by Peter Johnson, Chair, Professor of Mathematics Dean Ho man, Professor of Mathematics Curt Lindner, Distinguished University Professor of Mathematics Chris Rodger, C. Harry Knowles Professor of Mathematics Abstract Let G be a simple graph with vertex set V(G). Let F be a family of graphs such that K1 2F. Denote by B(G;F) the number of unordered partitions of V(G) such that each part induces a member ofF. We call B(G;F) the Bell number of the graph G with respect to the family F. We investigate properties of this function for di erent families F, and conditions on F for the function B(G;F) to have certain properties. ii Acknowledgments I am indebted to Rhodes Peele for the course in enumeration that uncovered this topic, and my to advisor Peter Johnson for giving me direction with this problem and invaluable editorial assistance. I cannot give enough thanks to Ken Baker and Tony Hickman, without whom I would not have had the opportuity to attend Auburn. For their emotional support over the years, I thank the Rowe family - especially Katie, Kathy, and John. All my love to my partner Stephen, even though he nds all this math stu terribly dull, because every day he gives me reason to smile. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Information on Set Partitions . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 The Bell Number of a Graph With Respect to the Family F0 . . . . . . . . . . 4 2.1 Deletion and Contraction Properties of B(G;F0) . . . . . . . . . . . . . . . 4 2.2 Multiplicative Property of B(G;F0) . . . . . . . . . . . . . . . . . . . . . . 7 2.3 B(G;F0) for Particular Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 B(G;F0) for Graphs with Two Components . . . . . . . . . . . . . . . . . . 13 3 The Bell Number of a Graph With Respect to the Family Ft . . . . . . . . . . 16 3.1 Complete Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4 Combinations of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 The Bell Number of a Graph With Respect to the Family Ff . . . . . . . . . . 22 5 Families F and Their Properties . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.0.1 Situations where B(G;F) is Maximum . . . . . . . . . . . . . . . . . 25 5.0.2 Families with a Multiplicative Property . . . . . . . . . . . . . . . . . 25 5.0.3 Families with a Cut Vertex Property . . . . . . . . . . . . . . . . . . 26 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 iv Chapter 1 Introduction Suppose that G is a simple graph and F is a family of simple graphs where K1 2F. We de ne the Bell number of G with respect to F, denoted B(G;F), to be the number of unordered partitions of V(G) such that each member of the partition induces a member of F. Such a partition is referred to as a F-partition of G. Members of partitions are referred to as blocks (even if the partition is not a F-partition). This problem arose when I was an undergraduate working with Rhodes Peele at Auburn University at Montgomery. I was assigned the following problem. Due to Herbert Wilf [1], let [n] denote the set of integers 1 through n: Let f(n) be the number of subsets of [n] that contain no two consecutive elements. Find the recurrence that is satis ed by these numbers, and then ? nd? the numbers themselves. [1] But I misread subsets as partitions; that is, I thought that f(n) was the number of unordered partitions of [n] in which no partition set contained two consecutive integers. This task proved to be more involved than Wilf?s problem. Dr. Peele suggested we view the problem as being about a simple graph G where V(G) = [n] and two distinct vertices i;j are adjacent if and only if ji jj = 1. In other words, G is a path on n vertices, and we seek to partition V(G) such that no two vertices together in the same block have an edge between them - that is, each block is an independent set of vertices of G. It turns out that the number of such partitions is (n 1)th Bell number. 1 The nth Bell number, bn, denotes the number of non-empty, unordered partitions of an n-element set. It is surprising that the number of partitions of the vertices of a path into independent sets followed the Bell sequence (with a shift in index), since these partitions are not unrestricted. Expanding this question to other graphs G, the Bell-like behavior motivated referring to this problem as nding the \Bell number" of G. With Dr. Johnson, this question was expanded from partitioning vertex sets into independent sets to partitioning into blocks which ecach induce a member of a speci ed family of graphs F. Denoting the number of such partitions by B(G;F), we call this the Bell number of G with respect to the family F. 1.1 Information on Set Partitions The Bell numbers satisfy a well-known recurrence bn = n 1X i=0 n 1 i bi: The proof of the recurrence is enlightening when it comes to certains proofs for the Bell numbers of graphs, so it is worthwhile to brie y examine it to build familiarity. Proof. To partition the set [n], consider which block will contain the element n. If n is in a block by itself, then there is n 10 ways to choose that block, n 1 elements remain outside of the block, and there are bn 1 ways to partition them. If n is in a block with one other element, then there are n 11 ways to form that block, n 2 elements remain outside of the block, and there are bn 2 ways to partition the rest. More generally, if n is in a block with k 1 other elements, then there are n 1k 1 ways to form the block, n k elements remain outside of the block, and there are bn k ways to partition the rest. Double counting does not occur from this process, so the recurrence is evident. 2 Another way of representing the Bell numbers is in terms of Stirling Numbers of the Second Kind, denoted ( n k ) , which indicates the number of unordered partitions of an n-element set into exactly k blocks. Clearly, bn = nX k=1 ( n k ) The corresponding notations that we will use for graphs G are B(G;F) and S(G;F;k). For graphs, the latter is de ned to be the number of unordered partitions of V(G) into exactly k blocks such that each block induces a member of F. It is, of course, the case that the sum of S(G;F;k) over 1 k jV(G)j yields B(G;F). 3 Chapter 2 The Bell Number of a Graph With Respect to the Family F0 F0 :=fKn : n2[n]g With Kn denoting the complete graph on n vertices,F0 is the collection of graphs with no edges and a positive number of vertices. The work I did with Rhodes Peele focused on B(G;F0) for various graphs G. In particular, we considered trees, cycles, stars, and comple- ments of paths. [2] More, we discovered certain properties of the B(G;F0) function. 2.1 Deletion and Contraction Properties of B(G;F0) For a simple graph G, the minimal k for which S(G;F0;k) is non-zero is the chromatic number (G). The chromatic polynomial (G; ) of a graph is a polynomial whose evaluation at integer m yields the number of functions f : V(G)!f1;2;:::;mgthat properly color G with at most m colors. It is commonly written as follows. (G; ) = n(G)X k=1 pk(G) (k) where (k) = ( 1) ( k + 1):[7] Note that S(G;F0;k) = pk(G). It?s possible to obtain the Bell number of a graph G with respect to F0 if the quantities pk(G) are known for all 1 k jV(G)j, but that?s equivalent to nding the chromatic polynomial, which is known to be a di cult problem. 4 (cite something here) The chromatic polynomial is known to have a very convenient deletion/contraction property which is shared by the function B(G;F0). For a graph G, if e2E(G) then denote by Gne the graph G with edge e removed. Denote by G e the graph G with the ends of e identi ed as a single vertex, which is adjacent to all vertices to which either of the ends of e were adjacent; if duplicate edges are created, merge them into a single edge. Then the chromatic polynomial has the following property. (G; ) = (Gne; ) (G e; ) The reason this works is as follows. Partitions of V(Gne) into independent sets consist of two types: partitions where the ends of e appear together in a block, and partitions where the ends of e are in di erent blocks. Partitions of V(G) into independent sets forbid the ends of e from appearing in the same block, and partitions of V(G e) are those where the ends of e are always together in the same block (as they are identi ed as the same vertex). This means that pk(G) = pk(Gne) pk(G e) for 1 k jV(G)j Since these coe cients determine the Chromatic polynomial, it must be the case that (G; ) = (Gne; ) (G e; ): Moreover, those coe cients determine the Bell number, so it must also be the case that B(G;F0) = B(Gne;F0) B(G e;F0): 5 Question Suppose thatF is a family of graphs with K12F. If for every graph G and every e2E(G) it happens that B(G;F) = B(Gne;F) B(G e;F), does it follow that F F0 ? Theorem 2.1. Let G = (V;E) be a simple graph and w a vertex not in V. Let Gw represent the collection of graphs obtained from G by adding w as a pendant vertex. Gw =fHv : V(H) = V [fwg and E(H) = E(G)[fw;vg for some v2Vg Then for any u, v 2 V, S(Hu;F0;k) = S(Hv;F0;k) for each 1 k jV(G)j+ 1. Consequently, B(Hu;F0) = B(Hv;F0). Proof. Let e = fw;ug2 E(Hu) and f = fw;vg2 E(Hv). Suppose we wish to examine the partitions of V(Hu) and V(Hv) with respect to F0 into exactly k blocks with 1 k jV(G)j+ 1. By deletion and contraction: S(Hu;F0;k) = S(Hune;F0;k) S(Hu e;F0;k) S(Hv;F0;k) = S(Hvnf;F0;k) S(Hv f;F0;k) Alternatively, we may represent Hune by G + w to represent the disjoint union of G and w. And then we see that Hvne = G+w as well. Since Hu e?G?Hv f, S(Hu;F0;k) = S(G+w;F0;k) S(G;F0;k) S(Hv;F0;k) = S(G+w;F0;k) S(G;F0;k) Therefore, S(Hu;F0;k) = S(Hv;F0;k): 6 Since B(J;F0) = n(J)X k=1 S(J;F0;k) for any graph J, we see that B(Hu;F0) = B(Hv;F0). 2.2 Multiplicative Property of B(G;F0) Suppose that G and H are graphs with disjoint vertex sets and denote by G_H the join of G and H where V(G_H) = V(G)[V(H) and E(G_H) = E(G)[E(H)[ffx;yg: x2V(G);y2V(H)g. Then B(G_H;F0) = B(G;F0) B(H;F0) The property follows from the observation that if p is a partition of V(G) into inde- pendent sets and q is a partition of V(H) into independent sets, then p[q is a partition of V(G_H) into independent sets. Conversely, if s is a partition of V(G_H) into independent sets then no block of s contains both a vertex of V(G) and a vertex of V(H), so s can be sorted into blocks consisting only of vertices of G and blocks consisting only of vertices of H. The former is a partition p of V(G) into independent sets and the latter is a parititon q of V(H) into independent sets. Note also that ifF0 F0, then B(G_H;F0) = B(G;F0) B(H;F0) by the same argu- ment, because the number of elements in each block is irrelevant to the proof. Question Let F be a family of graphs containing K1. If B(G_H;F) = B(G;F) B(H;F) for all simple graphs G and H, is it necessarily the case that F F0? 7 2.3 B(G;F0) for Particular Graphs Let n2N. Denote by Kn the complete graph on n vertices, and Kn its complement, the graph with n vertices and no edges. Then it is immediate that B(Kn;F0) = 1 and B(Kn;F0) = bn: Theorem 2.2. Let Tn denote a tree on n vertices. Then B(Tn;F0) = bn 1 Proof. By the deletion and contraction property, for any graph G and vertex w not in V(G): if Hv;Hu2Gw, then these two graphs will have the same Bell number wih respect to F0 by 2.1. Applying this to trees obtains the result, as follows. The result is immediate for n 2, so assume n > 2. Let Tn be a tree on n vertices. Choose any non-leaf r2V(Tn). Since any tree on at least two vertices has at least two leafs, let l be a leaf of Tn and e its edge. Denote by T0n the graph obtained from Tn by deleting e and attaching l to r. Let G = Tnnl, then Tn;T0n2Gl. So B(Tn;F0) = B(T0;F0): If we iterate this process, we can move all edges of Tn to r. At each step, we choose a leaf l not adjacent to r, delete its edge, and connect it to r. At each step, the Bell number is preserved. After at most n 2 steps, we?ll arrive at K1;n 1, the star with n 1 leafs. And so we see that for any tree Tn on n vertices, 8 B(Tn;F0) = B(K1;n 1;F0) Since K1;n 1 = K1_Kn 1, B(K1;n 1;F0) = B(K1_Kn 1;F0) = B(K1;F0)B(Kn 1;F0) = bn 1 Theorem 2.3. Let Pn denote a path on n vertices, and Pn the complement of Pn with respect to Kn. Then B(Pn;F0) = fn+1 where fn+1 denotes the (n+ 1)th Fibonacci number. Proof. Let the vertices of Pn, from one end to the other, be f1;2;:::;ng. Consider parti- tioning Pn with respect to F0. Blocks containing element n are either the singleton fng or the doubleton fn 1;ng. If fng is a block, then there are B(Pn 1;F0) partitions of the remaining vertices. If fn 1;ng is a block, then there are B(Pn 2;F0) partitions of the remaining vertices. Therefore, B(Pn;F0) = B(Pn 1;F0) +B(Pn 2;F0): Since B(P1;F0) = 1 and B(P2;F0) = 2, the recurrence shows us that the sequence (B(Pn;F0)) is \Fibonacci-like". In particular, B(Pn;F0) = fn+1. Theorem 2.4. Let K1;n denote the star graph with n leafs, n 0. Denote by K1;n its complement. Then B(K1;n;F0) = n+ 1 9 Proof. Let r be the central vertex of K1;n. Notice that K1;n = K1 + Kn. Considering partitioning its vertices with respect to F0. None of the vertices in the Kn component may appear in a block together, and r in the K1 component can appear in a block either by itself or with any of the vertices in the Kn component. Therefore, there are n+ 1 ways to form a partition of K1 +Kn, so B(K1;n;F0) = n+ 1. Corollary Every positive integer is the Bell number, with respect to F0, of some graph. Corollary For n> 3, there exist trees T;R on n vertices such that B(T;F0)6= B(R;F0). Proof. Let T = Pn and R = K1;n 1. Done. Theorem 2.5. Let Cn denote a cycle on vertex set f1;2;:::;ng, for n 3. Then B(Cn;F0) = n 2X k=0 ( 1)kbn (k+1) Proof. Apply deletion and contraction repeatedly. B(Cn;F0) = B(Pn;F0) B(Cn 1;F0) = B(Pn;F0) B(Pn 1;F0) +B(Cn 2;F0) = ... = B(Pn;F0) B(Pn 1;F0) +:::+ ( 1)n 3B(C3;F0) = Pn 4k=0( 1)kbn (k+1) + ( 1)n 3B(C3;F0) Since B(C3;F0) = 1 = b2 b1, the result follows. Theorem 2.6. Let Cn denote the complement of a cycle on n 4 vertices. Then B(Cn;F0) = fn + 2fn 1 where fk denotes the kth Fibonacci number. 10 Proof. Let Cn have vertex set f1;2;:::;ng, in order around the cycle, and consider parti- tioning wih respect to F0. In particular, consider vertex n. Vertex n may be in a block by itself, with 1, or with n 1. However, 1 and n 1 cannot be in a block together. Therefore, we have three cases. If n is in a block by itself, there are B(Pn 1;F0) ways to partition the remaining vertices. If eitherf1;ngorfn 1;ngare blocks, then there are B(Pn 2;F0) ways to partition the rest. Therefore, B(Cn;F0) = B(Pn 1;F0) + 2B(Pn 2;F0): Since we know that B(Pn;F0) = fn+1, the result follows. Theorem 2.7. Let Mn be a collection of n vertex-disjoint edges. (That is, Mn is a matching on 2n vertices.) Then, for n 2, B(Mn;F0) = n 1X k=0 n 1 k bn+k: Proof. Deletion and contraction can instead be thought of as insertion and contraction. Suppose n 2 and Mn is a matching on 2n vertices. Then the graph obtained from Mn by inserting an edge between any two of its non-adjacent vertices results in P4 +Mn 2. Deletion and contraction would tell us the Bell number of this graph is B(P4 +Mn 2;F0) = B(Mn;F0) B(P3 +Mn 2;F0): Therefore, B(P4 +Mn 2;F0) +B(P3 +Mn 2;F0) = B(Mn;F0): Successive applications of insertion/contraction to terms of the form B(Pi+Mj;F0) (for j > 0) will transform Pi +Mj into a path, providing we choose to insert edges only between 11 vertices of degree 1. The resulting coe cients on the terms are of importance. To see how they are generated, suppose that n is su ciently large to apply insertion/contraction several times. On each line, we will order the terms B(Pi +Mj;F0) by decreasing j. B(Mn;F0) = B(P4 +Mn 2;F0) +B(P3 +Mn 2;F0) = B(P6 +Mn 3;F0) +B(P5 +Mn 3;F0) +B(P5 +Mn 3;F0) +B(P4 +Mn 3;F0) = B(P6 +Mn 3;F0) + 2B(P5 +Mn 3;F0) +B(P4 +Mn 3;F0) Notice that under insertion/contraction, adjacent terms B(Pi + Mj;F0) and B(Pi 1 + Mj 2;F0) each generate a term involving B(Pi+1 + Mj 3;F0). The consequence of this is after i applications of insertion/contraction, the coe cients on the terms are precisely ni . B(Mn;F0) = B(P6 +Mn 3;F0) + 2B(P5 +Mn 3;F0) +B(P4 +Mn 3;F0) = B(P8 +Mn 4;F0) + 3B(P7 +Mn 4;F0) + 3B(P6 +Mn 4;F0) +B(P5 +Mn 4;F0) = B(P10 + 4Mn 5;F0) + 4B(P9 +Mn 5;F0) + 6B(P8 +Mn 5;F0) +4B(P7 +Mn 5;F0) +B(P6 +Mn 5;F0) = ... = kX i=0 k i B(P2k+2 i +Mn k 1;F0) When k = n 1, B(Mn;F0) = n 1X i=0 n 1 i B(P2(n 1)+2 i +M0;F0) Since M0 is the empty graph, we?re left with B(P2n i;F0) = b2n i 1 in the ith term, above. So, B(Mn;F0) = n 1X i=0 n 1 i b2n i 1 = n 1X i=0 n 1 n 1 i bn+(n 1 i) = n 1X i=0 n 1 k bn+k 12 2.4 B(G;F0) for Graphs with Two Components The material in this section originally appeared in [3]. Here we consider graphs with two components. Theorem 2.8. Suppose that D is a graph with components G and H, so we can write D = G+H. Let V(G) have size n and V(H) have size m. Then B(G+H;F0) = nX i= (G) mX j= (H) S(G;F0;i)S(H;F0;j)B(Ki +Kj;F0) where (G) and (H) are the chromatic numbers of G and H and Ki;Kj are complete graphs on i and j vertices, respectively. Proof. Let q = fq1;q2;:::;qig and r = fr1;r2;:::;rjg be F0-partitions of G and H respec- tively. We can form a F0-partition p = fp1;p2;:::;pkg of G + H = D by combininig the blocks of q and r in such a way that each block of p is either a block of q, a block of r, or a union of one block of q and one block of r. So, we see that F0-partitions of D may be constructed from any pair of partitions of its components. Conversely, suppose that p =fp1;p2;:::;pkgis aF0-partition of D. For each 1 i k, de ne qi = pi \V(G) and ri = pi \V(H). Let q = fqi : qi 6= ;;1 i kg and r = fri : ri 6= ;;1 i kg, and observe that q and r are F0-partitions of G and H respectively. Consequently, each F0-partition of D arises from a pair (q;r) of F0-partitions of G and H. Further, if a V(G) is a non-empty independent set and a =2q, then a[ri6= pj for any i;j2f1;2;:::;kg. Therefore, if q0 and r0 areF0-partitions of G and H respectively, then the F0-partitions of D derived from (q0;r0) and (q;r) are the same if and only if q = q0 and r = r0. 13 Regarding the blocks of q and r as vertices of complete graphs Ki and Kj respectively, then we see that the partitions yielded by the construction above are in one-to-one corre- spondence with the partitions of Ki+Kj. Since there are S(G;F0;i)F0-partitions of G into i blocks and S(H;F0;j)F0-partitions of H into j blocks, there are S(G;F0;i)S(H;F0;j) such pairs (q;r) and B(Ki+Kj;F0)S(G;F0;i)S(H;F0;j) partitions of D that can be constructed from those pairs. Theorem 2.9. For complete graphs Ki and Kj (with i j), B(Ki+Kj;F0) = Pil=0 il j!(j l)! Proof. Note that B(Kn;F0) = 1, and that partition consists only of singletons. F0-partitions of Ki +Kj will consist of singletons and only those doubletons consisting of one vertex from V(Ki) and one vertex from V(Kj). Let P and Q be the F0-partitions of Ki and Kj, respectively. We can construct a F0- partition of Ki +Kj from blocks of P and Q such that each block of the resulting partition is either a block of P (i.e., a vertex of Ki), a block of Q, or the union of exactly one block of P and one block of Q. There are il ways to select l blocks from P. If these l blocks are used to form unions with blocks of Q in a partition of Ki + Kj, then there are j!(j l)! ways to choose blocks of Q for the l blocks of P. ThisF0-partition of Ki +Kj will have j +i l blocks: l blocks which are unions of blocks of P and blocks of Q, j l blocks which are singletons of Q, and i l blocks which are singletons of P. Since there can be no other way to form F0-partitions of Ki +Kj with j+i l blocks, we nd that S(Ki +Kj;F0;j+i l) = il j!(j l)!. Consequently, B(Ki +Kj) = Pil=0S(Ki +Kj;F0;j +i l) = Pil=0 il j!(j l)!. 14 Theorem 2.10. Consider a graph D with connected components G and H. Then S(G+H;F0;k) = X (i;j)2N2 S(G;F0;i)S(H;F0;j)S(Ki +Kj;F0;k) the sum taken over pairs (i;j) subject to max(i;j) k i + j, (G) i n(G) and (H) j n(H). Proof. The method of construction here will be the same as in 2.8. Let P =fp1;p2;:::;pig be a partition of G with i blocks and Q =fq1;q2;:::;qjg be a partition of H with j blocks. Then P and Q will be used to construct partitions of G+H where blocks will be of the form pr, qs, or pr[qs. With this in mind, the pair (P;Q) can construct partitions of G+H with as few as max(i;j) blocks and as many as i+j blocks. In order to construct a partition with exactly k blocks from (P;Q), it is necessary that max(i;j) k i+j. Suppose a pair of partitions (P;Q) of G;H respectively satis es max(i;j) k i + j for some chosen k. If we regard the blocks of P and Q as vertices of complete graphs Ki and Kj respectively, then the number of partitions with k blocks yielded by (P;Q) are in one-to-one correspondence with the partitions of Ki + Kj with k blocks. Since there are B(G;F0;i), B(H;F0;j) partitions of G with i blocks and H with j blocks, re- spectively, there are B(G;F0;i)B(H;F0;j) such pairs (P;Q) and thus there are B(Ki + Kj;F0;k)B(G;F0;i)B(H;F0;j) partitions of G + H with k blocks that can be constructed from partitions of G with i blocks and partitions of H with j blocks. As noted in the proof of 2.8, every partition of G+H is derived from some pair (P;Q) of partitions of G;H separately, and collections of partitions derived from di erent pairs are disjoint. Since max(i;j) k i + j is a necessary condition on i and j for a partition of G + H to be constructed from a partition P of G with i blocks and Q of H with j blocks, and clearly there can be no such partitions unless (G) i n(G) and (H) j n(H), the sum in 2.9 counts each k-block partition of G+H exactly once. 15 Chapter 3 The Bell Number of a Graph With Respect to the Family Ft Ft :=fT : T is a tree g Ft is the collection of acyclic connected graphs, or trees. For this family, the Bell num- ber B(G;Ft) is examined in the cases where G is a complete graph, a tree, and a cycle. Moreover, exploitable properties of B(G;Ft) are found when G has certain features. It is rst worthwhile to notice that the functions B(G;F0) and B(G;Ft) behave very di erently. This material originally appeared in [4]. 3.1 Complete Graphs Theorem 3.1. B(Kn;Ft) = Pbn2ck=0 n!2kk!(n 2k)! Proof. The subgraph induced by any collection of m vertices (for 1 m n) is Km. Of these, only K1 and K2 are also trees, so no block of a Ft-partition may contain more than 2 elements. We can count the number of Ft-partitions of Kn by counting the number of partitions of f1;2;:::;ng containing no blocks of size 2, exactly one block of size 2, exactly two blocks of size 2, and so on, up to exactly bn2c blocks of size 2. 16 In Kn, there is one Ft-partition with no blocks of size 2. There are n2 ways to choose one block of size 2, so there are precisely that manyFt-partitions containing exactly 1 block of size 2. There are 12! n2 n 22 ways to choose blocks of size 2, irrespective of order, so there are precisely that many Ft-partitions containing exactly 2 blocks of size 2. The number of ways to select k blocks of size 2, irrespective of order, is 1k!Qk 1i=0 n 2i2 . Notice, however, that Qk 1i=0 n 2i2 collapses: Qk 1 i=0 n 2i 2 = n! 2(n 2)! (n 2)! 2(n 4)! (n 4)! 2(n 6)! (n 2k+4)! 2(n 2k+2)!) (n 2k+2)! 2(n 2k)! = n!2k(n 2k)! Thus, the number ofFt-partitions with exactly k blocks of size 2 is n!2kk!(n 2k)!. Summing over k gives the result. Remark. Counting the Ft-partitions of Kn is equivalent to partitioning an n-element set into (unordered) sets of size 1 and 2, so it is unsurprising that this is not the rst time this problem has arisen. Other interpretations can be found at [6]. 3.2 Trees Theorem 3.2. If H is a simple graph and v 2V(H) a pendant vertex, then B(H;Ft) = 2B(Hnv;Ft). Proof. If p is a Ft-partition of Hnv then we can form a new partition by inserting v either in a singleton set or in a block with its neighbor in H. This new partition will be a Ft- partition of H, so from each Ft-partition of Hnv we can create two Ft-partitions of H. These partitions will clearly be distinct. The reader can easily verify that all Ft-partitions of H are obtained in this way. Theorem 3.3. If G is a tree on n vertices, then B(G;Ft) = 2n 1. 17 Proof. Since G is a tree on n vertices, G can be built from a single vertex by sequentially appending pendant vertices n 1 times. Since B(K1;Ft) = 1, B(G;Ft) = 2n 1. 3.3 Cycles Theorem 3.4. If Cn is a cycle on n vertices (n 3), then B(Cn;Ft) = 2n (n+ 1). Remark. We have opted to prove this using mathematical induction and 3.2. The in- terested reader may notice a shorter, direct proof. Proof. Observe that B(C3;Ft) = 4, so the claim is true for n = 3. To proceed inductively, the following argument requires n 4. It can be easily veri ed that B(C4;Ft) = 11, so the state- ment is true for a base case. Assume now that for some n2N, n> 4, B(Cn 1;Ft) = 2n 1 n. We will count B(Cn;Ft) by constructing Ft-partitions of Cn from the Ft-partitions of Cn 1. Let V(Cn) =f1;2;:::;ng and V(Cn 1) =f1;2;:::;n 1g. A Ft-partition p of Cn 1 will be called \good" if 1 and n 1 do not appear in the same block. Otherwise, the partition is \bad". In a good p, n 1 is either in a block with n 2 or it is in a block by itself. Likewise, 1 is either in a block with 2 or in a block by itself. Notice that, except for the partition p = ff1;2;:::;n 1gg, every Ft-partition of Pn 1 (a path on n 1 vertices) is a good Ft-partition of Cn 1, and every good partition is aFt-partition of Pn 1. Therefore, there are B(Pn 1;Ft) 1 good Ft-partitions of Cn 1. From each good Ft-partition of Cn 1, we can construct three Ft-partitions of Cn: n can be inserted as a singleton block, n can be inserted into a block with n 1, and n can be inserted into a block with 1. In good partitions, n 1 and 1 are in separate blocks, 18 so each choice produces a distinct partition. The partitions are Ft-partitions of Cn since a block inducing a tree in Cn 1 also induces a tree in Cn, and keeping 1 and n 1 apart has avoided inducing cycles. And so, good Ft-partitions produce a total of 3(B(Pn 1;Ft) 1) Ft-partitions of Cn. In a bad Ft-partition, 1 and n 1 appear in a block together, which means that block induces two disjoint paths in Cn. However, by inserting n into such a block, since n is a neighbor of both 1 and n 1 in Cn, the block now induces a tree. In Ft-partitions of Cn 1, since 1 and n 1 either appear together in a block or in two separate blocks, we know that there must be B(Cn 1;Ft) (B(Pn 1;Ft) 1) bad Ft-partitions of Cn 1. Each of these yields exactly one Ft-partition of Cn, and each Ft-partition produced is distinct. Recall the partition p. Being that it is not a Ft partition of Cn 1, it is neither good nor bad. However, the block f1;2;:::;n 1g induces a tree in Cn and this block does not appear in any good or bad partitions. The only way to construct from p a Ft-partition of Cn is to form p[ffngg. Every Ft-partition of Cn is counted in this way. This produces B(Cn;Ft) = 3(B(Pn 1;Ft) 1) +B(Cn 1;Ft) (B(Pn 1;Ft) 1) + 1 = 2B(Pn 1;Ft) +B(Cn 1;Ft) 1 Since Pn 1 is a tree, B(Pn 1;Ft) = 2n 2. By the inductive step, B(Cn 1;Ft) = 2n 1 n, so B(Cn;Ft) = 2 2n 2 + 2n 1 n 1 = 2n (n+ 1): 19 Remark. Like 3.1, this theorem again provides new interpretation for an integer se- quence. Other interpretations can be found at [6]. 3.4 Combinations of Graphs Theorem 3.5. If G is a graph with components H1 and H2, then B(G;Ft) = B(H1;Ft)B(H2;Ft) Proof. If p is aFt-partition of H1 and q is aFt-partition of H2, then p[q is aFt-partition of G. Conversely, if r is aFt-partition of G then each block of r contains vertices either strictly from V(H1) or strictly from V(H2), so r may be viewed as the union of aFt-partition of H1 and a Ft-partition of H2. Theorem 3.6. Suppose G is a graph with cut vertex v, and let H1;H2;:::;Hk be the components of Gnv. De ne Ij to be the subgraph of G induced by V(Hj)[fvg. Then B(G;Ft) = Qkj=1B(Ij;Ft) Proof. For 1 j k, let pj denote a Ft-partition of Ij and bj denote the block of pj containing vertex v. Let p =[kj=1pj and b =[kj=1bj. Form a new set collection q: q = (pnfb1;b2;:::;bkg)[fbg Observe that q is a Ft partition of G, and q is distinct for distinct choices of pj. Every Ft-partition of G is obtained in this way. Let q be a Ft-partition of G. Denote by b the block containing v. For each block c 6= b, there is a j 2f1;2;:::kg such that c V(Hj). For each j, de ne bj =fu2b : u2V(Ij)gand pj =fc2q : c V(Hj)g[fbjg. This yields a collection p1;p2;:::;pk of partitions of the vertex sets of I1;I2;:::;Ik. It is 20 straightforward that each pj is aFt-partition of Ij and that q arises from p1;p2;:::;pk in the way described above. Theorem 3.7. Suppose G is a connected graph with cut edge e, and let H1;H2 be the components of Gne. Then B(G;Ft) = 2B(H1;Ft)B(H2;Ft). Proof. If either end of e has degree 1, the result follows from 3.2. Assume that the ends of e have degree larger than 1. In a Ft-partition of G, the end points of e are either in a block together or they are in separate blocks. TheFt-partitions of G where the end points of e are in separate blocks are exactly theFt-partitions of Gne, so there are precisely B(H1;Ft)B(H2;Ft)Ft-partitions of G of this type. The Ft-partitions of G where the end points of e appear in the same block correspond to the Ft-partitions of the graph G e obtained by contracting the end points v1;v2 of e to a single vertex w. Because e was a cut edge, w2V(G e) is a cut vertex. Let J1 be the subgraph of G e induced byfwg[V(H1)nfv1g, and J2 be the subgraph of G e induced by fwg[V(H2)nfv2g. Then B(G e;Ft) = B(J1;Ft)B(J2;Ft). But clearly J1 is isomorphic to H1 and J2 to H2, so B(H1;Ft)B(H2;Ft) = B(J1;Ft)B(J2;Ft). This gives us B(G;Ft) = B(Gne;Ft) +B(G e;Ft) B(G;Ft) = 2B(H1;Ft)B(H2;Ft) Questions Which familiesF of graphs with K12F share some or all of the properties of Ft expressed in 3.2, 3.5, 3.6 or 3.7? 21 Chapter 4 The Bell Number of a Graph With Respect to the Family Ff Ff :=fF : F is a forest g Many properties of Ft are lost by extending the family to forests, largely because the family contains graphs which are not connected. For example, Theorem 3.2 does not hold for the familyFf as it does forFt. To illustrate, let G be a K3 with a pendant vertex attached. If 3.2 held, then B(G;Ff) = 2B(K3;Ff) B(K3;Ff) = 4, so we would nd B(G;Ff) = 8. However, we may nd B(G;Ff) quickly by considering all (ordinary) partitions of the set V(G), of which there are b4 = 15, and elim- inating those where a block induces K3. There are exactly 2 of those: the partition consisting of V(G) and the partition where the pendant vertex is isolated and the vertices of K3 are in a block. Clearly, B(G;Ff) = 136= 2B(G;Ff). Ff is an incredibly permissive family. It excludes only blocks which induce non-acyclic graphs. This makes it surprisingly easy to estabish Bell numbers, but less easy to identify 22 convenient properties. For example, supppose G is any forest and jV(G)j = n. Then B(G;Ff) = bn because absolutely every partition of V(G) is a Ff-partition. If G = Cn, then B(G;Ff) = bn 1 because only V(Cn) itself fails to be a Ff-partition. If G = Kn, then B(G;Ff) = B(G;Ft) since it is still the case that the only valid partitions are those whose blocks consist only of singletons and doubletons. Theorem 4.1. Suppose G is a unicyclic graph with jV(G)j = n and the cycle has size k. Then B(G;Ff) = bn bn k+1 Proof. The only partitions of V(G) which are not Ff-partitions are those in which some block induces a non-acyclic subgraph. De ne G0 to be the graph obtained by identifying the vertices of the k-cycle in G as the single vertex v. Then B(G0;Ff) is the number of partitions of this graph, and each of these corresponds to a non-Ff-partition of G. Since G0 is a tree on n k + 1 vertices, B(G0;Ff) = bn k+1. The result follows. The idea of shrinking cycles to single vertices allows this theorem to generalize. Theorem 4.2. Let G be a graph where jV(G)j= n and V(G) has pairwise disjoint subsets W1;W2;:::;Wl such that the subgraph of G induced by Wi (1 i l) is a cycle, and suppose that there is no other subset of V(G) whose induced subgraph is a cycle. Refer to these cycles as Ck1;Ck2;:::;Ckl (where each ki is the cycle length), and let K =fk1;k2;:::;klg. Then B(G;Ff) = bn + lX j=1 ( 1)j X S K jSj=j bn (Px2S x)+j Proof. Let Ai denote the collection of (ordinary) partitions p of V(G) such that some block of p induces a subgraph containing Cki. Let [l] =f1;2;:::;lg. If we know the size ofSli=1Ai, then we know how many partitions of V(G) are notFf-partitions of G. The size of a union 23 is well known to be j l[ i=1 Aij= lX j=1 ( 1)j 1 X R [l] jRj=j j \ r2R Arj From here, consider the sizes of these di erent sets. The size of Ai, for any 1 i n, is bn ki+1. Identify all vertices of Cki as a single vertex ci. Consider the (ordinary) partitions of this new vertex set of size n ki+1. Each of these partitions corresponds to a partition of V(G) in which Cki is in a block, and the subgraph of G induced by that block will contain Cki. For i;j2[l];i6= j; the size of Ai\Aj can be found by shrinking the cycles Cki and Ckj to single vertices ci and cj, respectively. The resulting graph has n ki kj + 2 vertices, and there are bn ki kj+2 (ordinary) partitions of that vertex set. For R [l], the size of Tr2RAr can be found by, for each r2R, shrinking the cycle Cr to a single point cr. Then the number of partitions of that vertex set is bn (Pr2Rkr)+jRj. 24 Chapter 5 Families F and Their Properties Throughout this chapter, F will denote a family of graphs containing K1. We have seen the families F0 and Ft exhibit a variety of properties. We now turn our attention to identifying other families that might share these properties. 5.0.1 Situations where B(G;F) is Maximum Recall that for any familyF and any graph G withjV(G)j= n, B(G;F) bn. Equality occurs when every induced subgraph of G is a member ofF. We also found that B(G;Ff) = bjV(G)j for every G2Ff, but it was not the case that B(G;Ft) = bjV(G)j for every G2Ft. Observe the following. Theorem 5.1. If F is a family of graphs containing K1, then B(G;F) = bjV(G)j for all G2F if and only if F is closed under the operation of taking induced subgraphs. Proof. Suppose that B(G;F) = bjV(G)j for all G2F. Then for all G2F, every subgraph of G is a member of F. So, F is closed under the operation of taking induced subgraphs. Conversely, if F is closed under the operation of taking induced subgraphs, then for every G2F, all of its induced subgraphs are members of F. Therefore, B(G;F) = bjV(G)j. 5.0.2 Families with a Multiplicative Property Theorem 5.2. Let G be a graph with connected components H1;H2;:::;Hn. IfF is a family of connected graphs, then B(G;F) = Qni=1B(Hi;F). 25 Proof. Recall the proof of 3.5 used only that each member of the family is a connected graph. The proof here is similar. 5.0.3 Families with a Cut Vertex Property In this section, G will be a graph with a cut vertex v such that Gnv has con- nected components H1;H2;:::;Hk; respectively subgraphs I1;I2;:::;Ik of G are induced by V(H1)[fvg;V(H2)[fvg;:::;V(Hk)[fvg, respectively. For the sake of brevity, we will abridge this by referring to these special induced subgraphs as the v-induced subgraphs of G. Recall the proof of 3.6. We began with a graph G with cut vertex v and v-induced subgraphs I1;I2;:::;Ik. From Ft-partitions p1;p2;:::;pk of I1;I2;:::;Ik (respectively), we constructed a Ft-partition of G by de ning the block of q containing v to be the union of the blocks of p1;p2;:::;pk containing v. There are two reasons this construction is valid in proving 3.6. First, the construction of the block containing v in q requires that any time X;Y 2Ft, if x2V(X) and y2V(Y) then the graph X Y obtained by identifying x = y is also a member ofFt. Additionally, it is necessary that the graphs ofFt be connected as this means the only block of q containing vertices of each of I1;I2;:::;Ik is the block containing v. This observation of the essential properties of Ft used in the proof of 3.6 leads to the following generalization. A familyF of graphs containing K1 will be said to have the Cut Vertex Property if and only if the statement obtained from 3.6 by replacing Ft by F is true. Theorem 5.3. Suppose thatF is a family of connected graphs with the following properties. (1) For every X;Y 2F, if x2V(X) and y2V(Y) then the graph X Y 2F where X Y 26 is the graph obtained by identifying the vertices x = y. (2) For any X2F with cut vertex x, the v-induced subgraphs of X are each members of F. Then F has the Cut Vertex Property. Proof. The proof proceeds essentially the same as the one for Ft. Our interest will be in identifying families F with the Cut Vertex Property, but some of them can be observed right now, thanks to 5.3. fK1g, a trivial family Ft, the family of all trees Fc, the family of all connected graphs The relationship fK1g Ft Fc gives rise to several questions. Is there a family fK1g F Ft with this cut vertex property? Are there familiesfK1g F Fc with the cut vertex property other than the family Ft ? What are the necessary and su cient conditions for the cut vertex property? Theorem 5.4. If F is a family of graphs such that fK1g F Ft, then F does not have the cut vertex property. Proof. Let T 2FtnF be such that jV(T)j is minimal among all trees in FtnF. Case 1. T 6= K2. Observe that T has a cut vertex v. Consider B(T;F). Since T 2FtnF is of minimal order, every tree of order smaller than T is in F. Therefore, the only subtree of T not in F is the tree induced by V(T). Consequently, B(T;F[fTg) = B(T;Ft) since every subtree of T is a member of F[fTg. If T has v-induced subgraphs I1;I2;:::;Ik then 27 B(T;F) = B(T;F[fTg) 1 = kY j=1 B(Ij;F) 16= kY j=1 B(Ij;F) Thus we see that F does not have the cut vertex property. Case 2. T = K2 By way of contradiction, assume that F does have the cut vertex property. Let R be any tree with jV(R)j 3. Since R is a tree, it has at least 2 leafs. Let v be a vertex adjacent to a leaf, and suppose it has m neighbor leafs. Let R have v-induced subgraphs I1;I2;:::;Ik ordered so that jV(Ii)j jV(Ij)j whenever i j. Since there are m neighbor leafs to v, the subgraphs I1;I2;:::;Im will all be isomorphic to K2. Since K2 =2F, B(K2;F) = 1. As F has the cut vertex property, B(R;F) = kY j=1 B(Ij;F) = kY j=m+1 B(Ij;F): We see that each leaf contributes nothing to the Bell number with respect to F. Since each of Im+1;Im+2;:::;Ik are trees larger than K2, the process applied to R can be iterated on each of them. The iterations halt when all v-induced subgraphs are isomorphic to K2, and this leads us to conclude B(R;F) = 1. But this tree R was arbitrary, so we see that the Bell number of any tree with respect toF must be 1. That meansF =fK1g, but we began by assuming fK1g F. Corollary 5.1. If fK1g F Ft then F fails to have at least one of the properties (1) and (2) in 5.3. We have enough information to conclude that there are families fK1g F Fc with the Cut Vertex Property other than the family Ft. For example, let G be a collection of graphs (possibly nite), not all trees. Generate a larger collection G (containing K1) by applying the operations suggested by 5.3 properties (1) and (2). That is, for any graphs 28 H;K2G and any h2V(H) and k2V(K), the graph obtained by identifying h and k as a single vertex (\gluing" h and k) is also a member of the new collection. Moreover, if L is a member of the new collection and v is a cut vertex of L, then the v-induced subgraphs of L must be members of the new collection. And if L1 and L2 are both members of the new collection, any graph obtained through a \gluing" manipulation (using only one vertex of each graph) must also be in the new collection. In this way, we can see that there will indeed be many more distinct families with the Cut Vertex Property. For example, if fC4g is our initial collection, then applying the oper- ations suggested by (1) and (2) will generate a family distinct from both Ft and the family of all connected graphs. Remark. The Cut Edge Property of Ft can be considered for generalization as well. At the time of this writing, we will content ourselves with the discovery of the existence of families with the Cut Vertex Property apart from fK1g;Ft; and Fc. 29 Bibliography [1] H. Wilf, Generatingfunctionlogy, Academic Press Inc., 1994, pp. 26. [2] B. Duncan and R. Peele, Bell and Stirling numbers for graphs, J. Integer Seq., 12 (2009), Article 09.7.1 [3] B. Duncan, Bell and Stirling numbers for disjoint unions of graphs, Congressus Numer- antium, 206 (2010), 215-217 [4] B. Duncan, Generalized Bell numbers for trees, submitted [5] N.J.A. Sloane, J. H. Conway, The On-Line Encyclopedia of Integer Sequences, http://oeis.org/A000085 [6] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org/A000295 [7] D. West, Graph Theory, Prentice Hall, 2001, pp. 220-221. 30