CanaDAM 2021
En ligne, 25 - 28 mai 2021

Arithmetic Combinatorics

An exponential bound for exponential diffsequences  [PDF]

A theorem of van der Waerden states that for any positive integer $r$, if you color $\mathbb{N}$ with $r$ colors, then one color will contain arbitrarily long arithmetic progressions. It is natural to ask what other arithmetic structures are preserved when $r$-coloring $\mathbb{N}$ and to pose quantitative questions about these. We consider $D$-diffsequences, introduced by Landman and Robertson, which are increasing sequences $a_1<a_2<\cdots<a_k$ in which the consecutive differences $a_i-a_{i-1}$ all lie in some given set $D$. Here, we consider the case where $D$ consists of all powers of $2$ and define $f(k)$ to be the smallest $n$ such that coloring $\{1,2,\cdots,n\}$ with $2$ colors guarantees the existence of a monochromatic $D$-diffsequence of length $k$. We establish that $f(k)$ grows exponentially and time permitting, we will discuss other choices of $D$ which behave differently.

TORIN GREENWOOD, North Dakota State University
Bounding monochromatic arithmetic progressions  [PDF]

We find a 2-coloring of the integers $\{1, 2, ..., n\}$ that minimizes the number of monochromatic arithmetic 3-progressions under certain restrictions. A monochromatic arithmetic progression is a set of equally-spaced integers that are all the same color. Previous work by Parrilo, Robertson, and Saracino conjectured an optimal coloring for large $n$ that involves 12 colored blocks. Here, we prove that the conjectured coloring is optimal among symmetric colorings with 12 intervals. We leverage a connection to coloring the continuous interval $[0, 1]$ first identified by Butler, Costello, and Graham. The proof relies on identifying classes of colorings with permutations, and enumerating these permutations using mixed integer linear programming. Joint work with Jonathan Kariv and Noah Williams.

GLENN HURLBERT, Virginia Commonwealth University
On intersecting families of independent sets in trees  [PDF]

The Erd\H{o}s-Ko-Rado Theorem states that, for $r\leq n/2$, intersecting families of $r$-sets have size at most that of a star. A graph $G$ is $r$-EKR if intersecting families of independent $r$-sets of $G$ are maximized by a star. Holroyd and Talbot conjectured that every graph $G$ is $r$-EKR for all $1\leq r\leq \mu(G)/2$. We verified the conjecture for all chordal graphs with isolated vertices.

While investigating whether trees are $r$-EKR, we had conjectured that stars of trees are maximized at leaves. We proved this for $r\le 4$, but Borg gave counterexamples for all $r\ge 5$. Here we prove that all trees with a unique split vertex satisfy the leaf conjecture, and we characterize their best leaves. It was recently shown that all trees whose split vertices have pendant edges satisfy the leaf conjecture. For such trees with exactly two split vertices, we also provide partial results on their best leaves.

STANIS{\L}AW RADZISZOWSKI, Rochester Institute of Technology
On Some Generalized Vertex Folkman Numbers  [PDF]

For graph $G$ and integers $a_i\ge 2$, the expression $G \rightarrow (a_1,\dots,a_r)^v$ means that for any $r$-coloring of the vertices of $G$ there exists a monochromatic $a_i$-clique for some color $i \in \{1,\cdots,r\}$. The vertex Folkman numbers are defined as $F_v(a_1,\dots,a_r;H) = \min\{|V(G)|: G$ is $H$-free and $G \rightarrow (a_1,\dots,a_r)^v\}$, where $H$ is a graph. Such numbers have been extensively studied for $H=K_s$ with $s>\max\{a_i\}_{1\le i \le r}$.

Let $J_k$ be the complete graph $K_k$ missing one edge, $J_k=K_k-e$. In this work we focus on vertex Folkman numbers with $H=J_k$, in particular for $k=4$ and $a_i\le 3$. We prove that $F_v(3,3,\cdots,3;J_4)$ is well defined for any $r\ge 2$. The simplest but intriguing case is that of $F_v(3,3;J_4)$, for which we establish the upper bound 135. The best known lower bound for this case is 25, which is implied by prior results.

Joint work Yu Jiang, David Narv\'{a}ez and Xiaodong Xu.