Abstract
dc:descriptionFor 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} ω(\cC) of $\cC$ by ω(\cC) = \sum\{A, B\} \in \cC (|A|+|B|). We define $h(n, k)$ to denote the minimum weight ω(\cC) among all covers $\cC$ of $\binom{V}{k}$. In~1964, Hansel~\cite{H} determined the bounds \lceil n \log2 n \rceil \leq h(n, 2) \leq n\lceil \log2 n\rceil, which are sharp precisely when n = 2p 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 = 2p + R for p = \lfloor \log2 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 = 2p + R satisfy p = \lfloor \log2 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 ω(\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 \{A1, \dots, Ad\} \in \cD of pairwise disjoint sets Ai \subset V, $1 \leq i \leq d$. We require that every element $K \in \binom{V}{k}$ is covered by some \{A1, \dots, Ad\} \in \cD, in the sense that K \subseteq A1 \dot\cup \cdots \dot\cup Ad where K \cap Ai \neq \emptyset holds for each $1 \leq i \leq d$. We analogously define hd(n,k) as the minimum weight ω(\cD) = \sumD \in \cD \sumA \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 hd(n,k) \geq n \logd/(d-1) (n/(k-1)) always holds, and that this bound is asymptotically sharp whenever d = d(k) = O (k/\log2 k) and $k = k(n) = O(\sqrt{\log \log n})$.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy (Ph.D.)
- Level thesis:degree_level
- Dissertation
- Discipline thesis:degree_discipline
- Mathematics and Statistics
- Grantor
- University of South Florida
- Year dc:date
- 2017
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Churchill, Gregory Sutton
- Contributors dc:contributor
-
- Brendan Nagle, Ph.D.
- Brian Curtin, Ph.D.
- Mohamed Elhamdadi, Ph.D.
- Theo Molla, Ph.D.
- Dmytro Savchuk, Ph.D.
- Jay Ligatti, Ph.D.
Subjects
dc:subject × 5Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.usf.edu/etd/7008