Back to search

Georgia Institute of Technology

Enumerative combinatorics of posets

Abstract

dc:description.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.

Degree

thesis:*
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2008

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Carroll, Christina C.
Advisor dc:contributor.advisor
  • Tetali, Prasad
Committee members dc:contributor.committeemember
  • Duke, Richard
  • Heitsch, Christine
  • Randall, Dana
  • Trotter, William T.

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/22659

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Carroll, Christina C.. Enumerative combinatorics of posets. Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/22659