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

Neidmann, Dana Neidinger

Permalink

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

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

Copyright and License Information

Copyright 2022 Dana Neidmann

Owning Collections