Enumerative Combinatorics of Posets

Abstract

This thesis contains several results concerning the combinatorics of partially ordered sets (posets) which are either of enumerative or extremal nature. <br><br> The first concerns conjectures of Friedland and Kahn, which state that the (extremal) d-regular graph on N vertices containing both the maximal number of matchings and independent sets of a fixed size is the graph consisting of disjoint union of appropriate number of complete bipartite d-regular graphs on 2d vertices. We show that the conjectures are true in an asymptotic sense, using entropy techniques. <br><br> As a second result, we give tight bounds on the size of the largest Boolean family which contains no three distinct subsets forming an "induced V" (i.e. if A,B,C are all in our family, if C is contained in the intersection of A B, A must be a subset of B). This result, though similar to known results, gives the first bound on a family defined by an induced property. <br><br> We pose both Dedekind-type questions concerning the number of antichains and a Stanley-type question concerning the number of linear extensions in generalized Boolean lattices; namely, products of chain posets and the poset of partially defined functions. We provide asymptotically tight bounds for these problems. <br><br> A Boolean function, f, is called cherry-free if for all triples x,y,z where z covers both x and y, f(z)=1 whenever both f(x)=1 and f(y)=1. We give bounds on the number of cherry-free functions on bipartite regular posets, with stronger results for bipartite posets under an additional co-degree hypotheses. We discuss applications of these functions to Boolean Horn functions and similar structures in ranked regular posets.