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

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² : 1 \leq i \leq r\}, we introduce the corresponding Exact Covering System Digraph (ECSD) G_S = G(d₁n+a₁, \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₁, \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₁, \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₀. 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₀, 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₀.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Neidmann, Dana Neidinger

Contributors dc:contributor

• Reznick, Bruce
• Kostochka, Alexandr
• Thorner, Jesse
• Shankar, Isabelle

• exact covering system
• infinite graph
• directed graph
• digital representation
• non-standard representation

Statement dc:rights

• Copyright 2022 Dana Neidmann

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F115380