{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-8205"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-8205","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"On Extending Hansel's Theorem to Hypergraphs","abstract":"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})$.","abstract_html":"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\\&#x27;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} <span class=\"etd-inline-math\">&omega;(\\cC)</span> of $\\cC$ by <span class=\"etd-inline-math\">&omega;(\\cC) = \\sum<sub>\\{A, B\\} \\in \\cC</sub> (|A|+|B|)</span>. We define $h(n, k)$ to denote the minimum weight <span class=\"etd-inline-math\">&omega;(\\cC)</span> among all covers $\\cC$ of $\\binom{V}{k}$. In~1964, Hansel~\\cite{H} determined the bounds <span class=\"etd-inline-math\">\\lceil n \\log<sub>2</sub> n \\rceil \\leq h(n, 2) \\leq n\\lceil \\log<sub>2</sub> n\\rceil</span>, which are sharp precisely when <span class=\"etd-inline-math\">n = 2<sup>p</sup></span> is an integer power of two. In~2007, Bollob\\&#x27;as and Scott~\\cite{BS} extended Hansel&#x27;s bound to the exact formula $h(n, 2) = np + 2R$, where <span class=\"etd-inline-math\">n = 2<sup>p</sup> + R</span> for <span class=\"etd-inline-math\">p = \\lfloor \\log<sub>2</sub> n\\rfloor</span>. The primary result of this dissertation extends the results of Hansel and of Bollob\\&#x27;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 <span class=\"etd-inline-math\">q = 2<sup>p</sup> + R</span> satisfy <span class=\"etd-inline-math\">p = \\lfloor \\log<sub>2</sub> q \\rfloor</span>. 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 <span class=\"etd-inline-math\">&omega;(\\cC) = h(n, k)</span>, share a unique {\\it degree-sequence}, as follows. For a vertex $v \\in V$, define the {\\it $\\cC$-degree} <span class=\"etd-inline-math\">\\deg<sub>\\cC</sub>(v)</span> 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 <span class=\"etd-inline-math\">\\{A<sub>1</sub>, \\dots, A<sub>d</sub>\\} \\in \\cD</span> of pairwise disjoint sets <span class=\"etd-inline-math\">A<sub>i</sub> \\subset V</span>, $1 \\leq i \\leq d$. We require that every element $K \\in \\binom{V}{k}$ is covered by some <span class=\"etd-inline-math\">\\{A<sub>1</sub>, \\dots, A<sub>d</sub>\\} \\in \\cD</span>, in the sense that <span class=\"etd-inline-math\">K \\subseteq A<sub>1</sub> \\dot\\cup \\cdots \\dot\\cup A<sub>d</sub></span> where <span class=\"etd-inline-math\">K \\cap A<sub>i</sub> \\neq \\emptyset</span> holds for each $1 \\leq i \\leq d$. We analogously define <span class=\"etd-inline-math\">h<sub>d</sub>(n,k)</span> as the minimum weight <span class=\"etd-inline-math\">&omega;(\\cD) = \\sum<sub>D \\in \\cD</sub> \\sum<sub>A \\in D</sub> |A|</span> 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 <span class=\"etd-inline-math\">h<sub>d</sub>(n,k) \\geq n \\log<sub>d/(d-1)</sub> (n/(k-1))</span> always holds, and that this bound is asymptotically sharp whenever <span class=\"etd-inline-math\">d = d(k) = O (k/\\log<sup>2</sup> k)</span> and $k = k(n) = O(\\sqrt{\\log \\log n})$.","abstract_has_math":true,"creators":["Churchill, Gregory Sutton"],"institution":"University of South Florida","degree_name":"Doctor of Philosophy (Ph.D.)","degree_level":"Dissertation","degree_discipline":"Mathematics and Statistics","degree_department":null,"school":null,"contributors":["Brendan Nagle, Ph.D.","Brian Curtin, Ph.D.","Mohamed Elhamdadi, Ph.D.","Theo Molla, Ph.D.","Dmytro Savchuk, Ph.D.","Jay Ligatti, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-11-08T08:00:00Z","date_published":"2017-11-08T08:00:00Z","updated_at":"2026-11-19T08:43:09Z","subjects":["Extremal Combinatorics","Covers","Weight","Hansel","Mathematics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/7008","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/7008","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-8205","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Brendan Nagle, Ph.D.","Brian Curtin, Ph.D.","Mohamed Elhamdadi, Ph.D.","Theo Molla, Ph.D.","Dmytro Savchuk, Ph.D.","Jay Ligatti, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Churchill, Gregory Sutton"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-11-08T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics and Statistics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation","Ph.D."]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (Ph.D.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Extremal Combinatorics","Covers","Weight","Hansel","Mathematics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/7008"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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})$."]},{"key":"dc:title","label":"Title","values":["On Extending Hansel's Theorem to Hypergraphs"]}]}],"canonical_facts":{"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."],"dc:creator":["Churchill, Gregory Sutton"],"dc:date":["2017-11-08T08:00:00Z"],"dc:description":["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})$."],"dc:identifier":["https://digitalcommons.usf.edu/etd/7008"],"dc:subject":["Extremal Combinatorics","Covers","Weight","Hansel","Mathematics"],"dc:title":["On Extending Hansel's Theorem to Hypergraphs"],"thesis:degree_discipline":["Mathematics and Statistics"],"thesis:degree_level":["Dissertation","Ph.D."],"thesis:degree_name":["Doctor of Philosophy (Ph.D.)"],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:43:09Z"}