For integers $n \geq k \geq 2$, let $V$ be an $n$-element set, and let $\binom{V}{k}$ denote the family of all $k$-element subsets of $V$. For disjoint subsets $A, B \subseteq V$, we say that $\{A, B\}$ {\it covers} an element $K \in \binom{V}{k}$ if $K \subseteq A \dot\cup B$ and $K \cap A \neq \emptyset \neq K \cap B$. We say that a collection $\cC$ of such pairs {\it covers} $\binom{V}{k}$ if every $K \in \binom{V}{k}$ is covered by at least one $\{A, B\} \in \cC$. When $k=2$, covers $\cC$ of $\binom{V}{2}$ were introduced in~1961 by R\'enyi~\cite{Renyi}, where they were called {\it separating systems} of $V$ (since every pair $u \neq v \in V$ is separated by some $\{A, B\} \in \cC$, in the sense that $u \in A$ and $v \in B$, or vice-versa). Separating systems have since been studied by many authors.
For a cover $\cC$ of $\binom{V}{k}$, define the {\it weight} $\omega(\cC)$ of $\cC$ by $\omega(\cC) = \sum_{\{A, B\} \in \cC} (|A|+|B|)$. We define $h(n, k)$ to denote the minimum weight $\omega(\cC)$ among all covers $\cC$ of $\binom{V}{k}$. In~1964, Hansel~\cite{H} determined the bounds $\lceil n \log_2 n \rceil \leq h(n, 2) \leq n\lceil \log_2 n\rceil$, which are sharp precisely when $n = 2^p$ is an integer power of two. In~2007, Bollob\'as and Scott~\cite{BS} extended Hansel's bound to the exact formula $h(n, 2) = np + 2R$, where $n = 2^p + R$ for $p = \lfloor \log_2 n\rfloor$.
The primary result of this dissertation extends the results of Hansel and of Bollob\'as and Scott to the following exact formula for $h(n, k)$, for all integers $n \geq k \geq 2$. Let $n = (k-1)q + r$ be given by division with remainder, and let $q = 2^p + R$ satisfy $p = \lfloor \log_2 q \rfloor$. Then
h(n, k) = np + 2R(k-1) + \left\lceil\frac{r}{k-1}\right\rceil (r + k - 1).
A corresponding result of this dissertation proves that all optimal covers $\cC$ of $\binom{V}{k}$, i.e., those for which $\omega(\cC) = h(n, k)$, share a unique {\it degree-sequence}, as follows. For a vertex $v \in V$, define the {\it $\cC$-degree} $\deg_{\cC}(v)$ of $v$ to be the number of elements $\{A, B\} \in \cC$ for which $v \in A \dot\cup B$. We order these degrees in non-increasing order to form $\bd(\cC)$, and prove that when $\cC$ is optimal, $\bd(\cC)$ is necessarily binary with digits $p$ and $p+1$, where uniquely the larger digits occur precisely on the first $2R(k-1) + \lceil r/(k-1) \rceil (r + k - 1)$ many coordinates. That $\bd(\cC)$ satisfies the above for optimal $\cC$ clearly implies the claimed formula for $h(n,k)$, but in the course of this dissertation, we show these two results are, in fact, equivalent.
In this dissertation, we also consider a $d$-partite version of covers $\cC$, written here as {\it $d$-covers} $\cD$. Here, the elements $\{A,B\} \in \cC$ are replaced by $d$-element families $\{A_1, \dots, A_d\} \in \cD$ of pairwise disjoint sets $A_i \subset V$, $1 \leq i \leq d$. We require that every element $K \in \binom{V}{k}$ is covered by some $\{A_1, \dots, A_d\} \in \cD$, in the sense that $K \subseteq A_1 \dot\cup \cdots \dot\cup A_d$ where $K \cap A_i \neq \emptyset$ holds for each $1 \leq i \leq d$. We analogously define $h_d(n,k)$ as the minimum weight $\omega(\cD) = \sum_{D \in \cD} \sum_{A \in D} |A|$ among all $d$-covers $\cD$ of $\binom{V}{k}$. In this dissertation, we prove that for all $2 \leq d \leq k \leq n$, the bound $h_d(n,k) \geq n \log_{d/(d-1)} (n/(k-1))$ always holds, and that this bound is asymptotically sharp whenever $d = d(k) = O (k/\log^2 k)$ and $k = k(n) = O(\sqrt{\log \log n})$.
| Identifer | oai:union.ndltd.org:USF/oai:scholarcommons.usf.edu:etd-8205 |
| Date | 08 November 2017 |
| Creators | Churchill, Gregory Sutton |
| Publisher | Scholar Commons |
| Source Sets | University of South Flordia |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Graduate Theses and Dissertations |
Page generated in 0.0022 seconds