Half Covering, Half Coloring Open Access
Clifton, Alexander (Spring 2022)
Published
Abstract
Alon and F\"{u}redi determined the minimum number of affine hyperplanes needed to cover all but one point of an $n$dimensional rectangular grid. It is natural to extend this to higher covering multiplicities and ask for the minimum number of affine hyperplanes needed to cover every grid point at least $k$ times each, except for one point that is not covered at all. In the special case of an $n$cube, we use a Punctured Combinatorial Nullstellensatz of Ball and Serra to exactly determine the minimum for $k=3$ and to formulate a lower bound for $k\geq{4}$. We also treat the problem as an integer program to determine an asymptotic answer for fixed $n$ as $k\to\infty$. Again using the Punctured Combinatorial Nullstellensatz, we answer the question for a general grid when $k=2$.
Another generalization we address for the $n$cube is the minimum number of affine subspaces of codimension $d$ needed to cover all but one vertex at least once. We also consider the minimum number of hyperplanes needed to cover all points of a triangular grid.
In the second half of this dissertation, we consider arithmetic Ramsey theory problems in the spirit of van der Waerden's theorem. For a set $D\subset\mathbb{Z}_{>0}$, Landman and Robertson introduced the notion of a $D$diffsequence, which is an increasing sequence $a_1<\cdots
By considering the case where $D$ consists of all powers of $2$, we provide an example of a $2$accessible set where $\Delta(D,k;2)$ grows faster than any polynomial. The proof relies on a series of periodic colorings based on the ThueMorse sequence. We also use Beatty sequences to classify which sets of the form $D=\{d_1,d_2,\cdots\}$ with $d_i\mid d_{i+1}$ for all $i$ are $2$accessible.
Table of Contents
1 Introduction
1.1 Covering and Coloring
1.2 Background for Covering
1.2.1 Covering Problems
1.2.2 Combinatorial Nullstellensatz
1.3 Background for Coloring
1.3.1 Ramsey Theory
1.3.2 Diffsequences
1.4 Dissertation Synopsis
2 Covering for Hypercubes
2.1 Preliminary Results
2.2 Fixed Covering Multiplicity
2.3 Fixed Dimension
2.4 Higher Codimension
2.5 Connections to Graph Covering and Sidon Sets
3 Covering for General Grids
3.1 Rectangular Grids
3.1.1 Complications for k=3
3.1.2 Restrictions on the Minimum Degree Polynomial
3.2 Triangular Grids
3.2.1 With a Point Uncovered
3.2.2 With All Points Covered
4 Results in Arithmetic Ramsey Theory
4.1 Superpolynomial Growth for Delta(D,k;2)
4.2 Inaccessibility of Certain Sets
4.2.1 Factorials
4.2.2 Existence Proof for General Dividing Sets
4.2.3 Random Diffsequences
A Number of Lines Needed to Cover Triangular Grids
B Values of Delta(D,k;2) when D={2^i  i is a nonnegative integer}
C Gurobi Code
Bibliography
About this Dissertation
 Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School  

Department  
Degree  
Submission  
Language 

Research Field  
Keyword  
Committee Chair / Thesis Advisor  
Committee Members 
Primary PDF
Thumbnail  Title  Date Uploaded  Actions 

Half Covering, Half Coloring ()  20220428 23:35:54 0400 

Supplemental Files
Thumbnail  Title  Date Uploaded  Actions 
