University of Illinois Urbana-Champaign

Exact covering system digraphs a number-theoretic family of directed graphs on the integers

Neidmann, Dana Neidinger

Content Files
NEIDMANN-DISSERTATION-2022.pdf

Permalink

https://hdl.handle.net/2142/115380

Description

Title
Exact covering system digraphs a number-theoretic family of directed graphs on the integers
Author(s)
Neidmann, Dana Neidinger
Issue Date
2022-04-08
Director of Research (if dissertation) or Advisor (if thesis)
Reznick, Bruce
Doctoral Committee Chair(s)
Kostochka, Alexandr
Committee Member(s)
  • Thorner, Jesse
  • Shankar, Isabelle
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
  • exact covering system
  • infinite graph
  • directed graph
  • digital representation
  • non-standard representation
Abstract
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$.
Graduation Semester
2022-05
Type of Resource
Thesis
Handle URL
https://hdl.handle.net/2142/115380
Copyright and License Information
Copyright 2022 Dana Neidmann

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois