Half Covering, Half Coloring Open Access
Clifton, Alexander (Spring 2022)
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 Thue--Morse 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
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 () | 2022-04-28 23:35:54 -0400 |
|
Supplemental Files
Thumbnail | Title | Date Uploaded | Actions |
---|