2026-09-20T03:54:39Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/115380 2023-07-11 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

application/pdf Reznick, Bruce Kostochka, Alexandr Thorner, Jesse Shankar, Isabelle 2022-05 en text 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 Exact covering system digraphs a number-theoretic family of directed graphs on the integers Neidmann, Dana Neidinger 2022-04-08 exact covering system infinite graph directed graph digital representation non-standard representation 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$. Thesis eng https://hdl.handle.net/2142/115380 Copyright 2022 Dana Neidmann Ph.D. Dissertation Mathematics University of Illinois at Urbana-Champaign Mathematics