In this dissertation, we study the following two topics, i.e., the union closed set conjecture and the maximum edges cut in connected digraphs. The union-closed-set-conjecture-topic goes as follows. A finite family of finite sets is {\it union closed} if it contains the union of any two sets in it. Let $X_{\mathcal{F}}=\cup_{F\in\mathcal{F}}F$. A union closed family of sets is {\it separating} if for any two distinct elements in $\mathcal{F}$, there is a set in $\mathcal{F}$ containing one of them, but not the other and there does not exist an element which is contained in every set of it. Note that any union closed family $\mathcal{F}$ is a poset with set inclusion as the partial order relation. A separating union closed family $\mathcal{F}$ is {\it irreducible} ({\it normalized}) if $|X_{\mathcal{F}}|$ is the minimum (maximum, resp.) with respect to the poset structure of $\mathcal{F}$. In the part of dissertation related to this topic, we develop algorithms to transfer any given separating union closed family to a/an normalized/irreducible family without changing its poset structure. We also study properties of these two extremal union closed families in connection with the {\it Union Closed Sets Conjecture} of Frankl. Our result may lead to potential full proof of the union closed set conjecture and several other conjectures. The part of the dissertation related to the maximum edge cuts in connected digraphs goes as follows. In a given digraph $D$, a set $F$ of edges is defined to be a {\it directed cut} if there is a nontrivial partition $(X,Y)$ of $V(D)$ such that $F$ consists of all the directed edges from $X$ to $Y$. The maximum size of a directed cut in a given digraph $D$ is denoted by $\Lambda (D)$, and we let $\mathcal{D}(1,1)$ be the set of all digraphs $D$ such that $d^{+}(v)=1$ or $d^{-}(v)=1$ for every vertex $v$ in $D$. In this part of dissertation, we prove that $\Lambda (D) \geq \frac{3}{8}(|E(D)|-1)$ for any connected digraph $D\in\mathcal{D}(1,1)$, which provides a positive answer to a problem of Lehel, Maffray, and Preissmann. Additionally, we consider triangle-free digraphs in $\mathcal{D}(1,1)$ and answer their another question.
| Identifer | oai:union.ndltd.org:GEORGIA/oai:scholarworks.gsu.edu:math_diss-1019 |
| Date | 12 August 2014 |
| Creators | Li, Nana, Chen, Guantao |
| Publisher | ScholarWorks @ Georgia State University |
| Source Sets | Georgia State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Mathematics Dissertations |
Page generated in 0.0016 seconds