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.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/22659 |
| Date | 01 April 2008 |
| Creators | Carroll, Christina C. |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Detected Language | English |
| Type | Dissertation |
Page generated in 0.0142 seconds