Half Covering, Half Coloring Pubblico

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

Rights statement

• 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	Laney Graduate School
Department	Mathematics
Degree	Ph.D.
Submission	Dissertation
Language	English
Research Field	Mathematics
Parola chiave	Extremal Combinatorics
Committee Chair / Thesis Advisor	Hao Huang, National University of Singapore
Committee Members	Liana Yepremyan, Emory University Vojtech Rodl, Emory University Dwight Duffus, Emory University

Ultima modifica

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Half Covering, Half Coloring ()	2022-04-28 23:35:54 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions