{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/115380"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/115380","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Exact covering system digraphs a number-theoretic family of directed graphs on the integers","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-11 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-11 without embargo terms","abstract_has_math":false,"creators":["Neidmann, Dana Neidinger"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Reznick, Bruce","Kostochka, Alexandr","Thorner, Jesse","Shankar, Isabelle"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-05","date_published":"2022-05","updated_at":"2026-07-22T22:24:54Z","subjects":["exact covering system","infinite graph","directed graph","digital representation","non-standard representation"],"languages":["en","eng"],"rights":["Copyright 2022 Dana Neidmann"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/115380","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Reznick, Bruce","Kostochka, Alexandr","Thorner, Jesse","Shankar, Isabelle"]},{"key":"dc:creator","label":"Author","values":["Neidmann, Dana Neidinger"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-05","2022-04-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["exact covering system","infinite graph","directed graph","digital representation","non-standard representation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2022 Dana Neidmann"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/115380"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-11 without embargo terms","The student, Dana Neidmann, accepted the attached license on 2022-04-06 at 12:29.","The student, Dana Neidmann, submitted this Dissertation for approval on 2022-04-06 at 12:37.","This Dissertation was approved for publication on 2022-04-08 at 10:47.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17597 on 2022-11-11 at 13:04:51","Given an exact covering system $\\{x \\equiv \\modd{a_i} {d_i}\\ : 1 \\leq i \\leq r\\}$, with a specific representative set $S = \\{(a_i, d_i) \\in \\Z^2 : 1 \\leq i \\leq r\\}$, we introduce the corresponding Exact Covering System Digraph (ECSD) $G_S = G(d_1n+a_1, \\ldots, d_rn + a_r)$. The vertices of $G_S$ are the integers and the edges are $(n,d_in+a_i)$ for each $n \\in \\Z$ and for each pair in the representative set. We study the structure of these directed graphs, which have finitely many components, one cycle per component, as well as indegree 1 and outdegree $r$ at each vertex. We classify all ECSDs with $r=2$ by their cycles, and find graph isomorphisms between different ECSDs in certain cases. We completely describe the cycles of ECSDs of the form $G(2n,2n-a)$. Using this classification, we consider a natural edge-coloring of these ECSDs, and find all one-component ECSDs with $r=2$. We extend these ideas to ECSDs with $r>2$, and we generalize some of the theorems proved for $r=2$ to the general case $r=d$. We also consider one family of ECSDs with $r=3$, namely $G(\\pm3n,\\pm3n-a,\\pm3n+a)$. We also explore the link between ECSDs that have a single component and non-standard digital representations of integers. If the ECSD $G(dn+a_1, \\ldots, dn + a_d)$ has a single component and 0 is a vertex in its cycle, then every integer can be represented in base $d$ with digit set $\\{a_1, \\ldots, a_d\\}$. Using the classification of all one-component ECSDs, we prove that the only ECSDs of degree 2 with one component are $G(2n,-2n+1)$ or isomorphic to an ECSD of the form $G(-2n+1,-2n+a)$ with $a = \\pm3^m+1$ for some $m \\in \\N_0$. Thus, every integer can be represented in base $-2$ with digit set $\\{1,a\\}$ if and only if $a = \\pm3^m+1$ for some $m \\in \\N_0$, equivalently, \\[\\Z = \\left\\{\\sum_{j=0}^k b_j(-2)^j : b_j \\in \\{1, a\\}, k \\in \\N_0 \\right\\}\\] if and only if $a = 1\\pm3^m$ for some $m \\in \\N_0$."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Exact covering system digraphs a number-theoretic family of directed graphs on the integers"]}]}],"canonical_facts":{"dc:contributor":["Reznick, Bruce","Kostochka, Alexandr","Thorner, Jesse","Shankar, Isabelle"],"dc:creator":["Neidmann, Dana Neidinger"],"dc:date":["2022-05","2022-04-08"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-11 without embargo terms","The student, Dana Neidmann, accepted the attached license on 2022-04-06 at 12:29.","The student, Dana Neidmann, submitted this Dissertation for approval on 2022-04-06 at 12:37.","This Dissertation was approved for publication on 2022-04-08 at 10:47.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17597 on 2022-11-11 at 13:04:51","Given an exact covering system $\\{x \\equiv \\modd{a_i} {d_i}\\ : 1 \\leq i \\leq r\\}$, with a specific representative set $S = \\{(a_i, d_i) \\in \\Z^2 : 1 \\leq i \\leq r\\}$, we introduce the corresponding Exact Covering System Digraph (ECSD) $G_S = G(d_1n+a_1, \\ldots, d_rn + a_r)$. The vertices of $G_S$ are the integers and the edges are $(n,d_in+a_i)$ for each $n \\in \\Z$ and for each pair in the representative set. We study the structure of these directed graphs, which have finitely many components, one cycle per component, as well as indegree 1 and outdegree $r$ at each vertex. We classify all ECSDs with $r=2$ by their cycles, and find graph isomorphisms between different ECSDs in certain cases. We completely describe the cycles of ECSDs of the form $G(2n,2n-a)$. Using this classification, we consider a natural edge-coloring of these ECSDs, and find all one-component ECSDs with $r=2$. We extend these ideas to ECSDs with $r>2$, and we generalize some of the theorems proved for $r=2$ to the general case $r=d$. We also consider one family of ECSDs with $r=3$, namely $G(\\pm3n,\\pm3n-a,\\pm3n+a)$. We also explore the link between ECSDs that have a single component and non-standard digital representations of integers. If the ECSD $G(dn+a_1, \\ldots, dn + a_d)$ has a single component and 0 is a vertex in its cycle, then every integer can be represented in base $d$ with digit set $\\{a_1, \\ldots, a_d\\}$. Using the classification of all one-component ECSDs, we prove that the only ECSDs of degree 2 with one component are $G(2n,-2n+1)$ or isomorphic to an ECSD of the form $G(-2n+1,-2n+a)$ with $a = \\pm3^m+1$ for some $m \\in \\N_0$. Thus, every integer can be represented in base $-2$ with digit set $\\{1,a\\}$ if and only if $a = \\pm3^m+1$ for some $m \\in \\N_0$, equivalently, \\[\\Z = \\left\\{\\sum_{j=0}^k b_j(-2)^j : b_j \\in \\{1, a\\}, k \\in \\N_0 \\right\\}\\] if and only if $a = 1\\pm3^m$ for some $m \\in \\N_0$."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/115380"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 Dana Neidmann"],"dc:subject":["exact covering system","infinite graph","directed graph","digital representation","non-standard representation"],"dc:title":["Exact covering system digraphs a number-theoretic family of directed graphs on the integers"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:54Z"}