Enumerative combinatorics of posets

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/22659

Title: Enumerative combinatorics of posets
Author: Carroll, Christina C.
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.
Type: Dissertation
URI: http://hdl.handle.net/1853/22659
Date: 2008-04-01
Publisher: Georgia Institute of Technology
Subject: Enumeration
Entropy
Dedekind's problem
Combinatorial analysis
Partially ordered sets
Graph theory
Department: Mathematics
Advisor: Committee Chair: Tetali, Prasad; Committee Member: Duke, Richard; Committee Member: Heitsch, Christine; Committee Member: Randall, Dana; Committee Member: Trotter, William T.
Degree: Ph.D.

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
carroll_christina_c_200805_phd.pdf 678.9Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record