Schedule for: 19w5132 - Zero-Sum Ramsey Theory: Graphs, Sequences and More

A sequence of positive integers $A$ is said to be entirely Ramsey complete if, for any two-colouring of $A$, every positive integer can be written as the sum of distinct elements of $A$ of the same colour. We show that there exists a constant $C$ and an entirely Ramsey complete sequence $A$ such that $|A \cap [n]| \leq C \log^2n$ for all $n$. This is best possible up to the constant and solves a problem of Burr and Erd\H{o}s. We also discuss several related problems stated by the same authors. Joint work with Jacob Fox.

The underlying philosophy of Ramsey Theory is that total disorder is impossible, and the underlying philosophy of Discrepancy Theory is that a totally equal distribution is impossible. In both theories we mainly try to find extremal configurations that satisfy some property or at least their magnitude. It is convenient to express these configurations as colored objects. Both theories can be extended from using colors to the use of vanishing (or almost vanishing) linear sums in several variables. Theorems in Ramsey Theory can be generalized using the Erdős Ginzburg Ziv theorem, by replacing a {0,1}-coloring by a coloring which uses the residues modulo a positive integer assuring a modular zero-sum. In Discrepancy Theory, many combinatorial problems can be expressed by a {-1,1}-coloring and the discrepancy from a uniform distribution is expressed as the deviation from zero. In the lecture we will discuss from a personal perspective, several Ramsey-type theorems and Discrepancy theorems in order to demonstrate the breadth of the subjects. Next we will survey recent developments of the EGZ theorem and other developments relating to integer-coloring. Finally, we will show how these developments relate to Ramsey Theory and Discrepancy Theory. The linear sums mentioned above can be generalized to symmetric polynomials. This suggests new avenues of research and many more problems.

The Erdos-Ginzburg-Ziv (EGZ) Theorem has an elegant proof due to Bailey and Richter that employs a 1935 result of Chevalley.  Chevalley’s Theorem states that the number of shared zeros of a polynomial system over a finite field is not equal to one whenever the number of variables exceeds the sum of the degrees of the polynomials.  In the same year, Warning generalized Chevalley’s Theorem and gave a lower bound on the number of shared zeros in such a system so long as one exists.  We discuss our generalization of Warning’s Theorem and show how we can quantitatively refine existence theorems, such as EGZ, and simultaneously include the inhomogeneous case.  Specifically, we show how one can apply our theorem to recover a 2012 result of Das Adhikari, Grynkiewicz and Sun that treats an analogue of the EGZ Theorem, one in which one considers the EGZ-problem for generalized zero-sum subsequences in any finite commutative p-group.   Joint work with Pete L. Clark and Aden Forrow.

In this talk, we will present a new upper bound for the Davenport constant of finite Abelian groups of the form $C^r_n$. An old conjecture in zero-sum theory asserts that $\mathsf{D}(C^r_n) = r(n-1) + 1$ holds for all integers $n,r \geqslant 1$ and still widely stands to this day. In this context, our bound turns out to be particularly relevant as it implies that for every integer $r \geqslant 1$, the Davenport constant $\mathsf{D}(C^r_n)$ is asymptotic to $rn$ when $n$ tends to infinity, thus proving the conjecture in an asymptotic sense. This improves on the best previously known upper bound which was $\mathsf{D}(C^r_n) \leqslant n(1 + (r-1)\log n)$. An extension of our theorem to a wider framework as well as related open problems will also be discussed.

In this talk, we will shortly present a direct and reverse way to develop the polynomial method that relies on the Combinatorial Nullstellensatz. The direct and usual way states that a multivariate polynomial of small degree cannot vanish on a large cartesian product provided that a specified coefficient is non zero. The reverse way relies on the coefficient formula and establishes an expression for this specified coefficient. This double interpretation of the polynomial method allows to shorten the proofs of the Cauchy-Davenport and the Dias da Silva-Hamidoune theorems and a new result on the cardinality of sets of subsums. Moreover tese proofs do not require any computations and do imply the critical cases of these three problems: arithmetical progressions.

The last few years have seen the development and improvement of structural results in the area of sequence subsums over abelian groups. These results often have the flavor that either many elements can be represented as a sum of terms from  a subsequence of the given sequence (possibly with length restrictions) or else the sequence must itself be highly structured. The Subsum Kneser's Theorem, giving the corresponding analog of the classical Kneser's Theorem for sumsets,  is one such example. The statements of such results, particulary in their stronger forms, are often more challenging and technical in appearance, but they have been  utilized to strong effect when searching for zero-sums in a variety of  circumstances.   In this talk, we will give an overview of several of these results, focussing on how they were successfully used in various concrete extremal  problems involving zero-sums.

For $(G,+,0)$ a finite abelian group and $S= g_1 \dots g_k$ a sequence over $G$, we denote by $\sigma(S)$ the sum of all terms of $S$. We call $|S|=k$ the length of the sequence. If the sum of $S$ is $0$, we say that $S$ is a zero-sum sequence. We denote by $\mathcal{B}(G)$ the set of all zero-sum sequences over $G$. This is a submonoid of the monoid of all sequences over $G$. We say that a zero-sum sequence is a minimal zero-sum sequence if it cannot be decomposed into two non-empty zero-sum subsequences. In other words, this means that it is an irreducible element in $\mathcal{B}(G)$. For $S \in \mathcal{B}(G)$ we say that $\ell$ is a factorization-length of $S$ if there are minimal zero-sum sequences $A_1, \dots , A_{\ell}$ over $G$ such that $S = A_1 \dots A_l$. We denote the set of all $\ell$ that are a factorization-length of $S$ by $\mathsf{L}(S)$. The set $\mathcal{L}(G) = \{\mathsf{L}(G) \colon B \in \mathcal{B}(G) \}$ is called the system of sets of lengths of $G$. Obvioulsy isomorphic groups have the same system of sets of lengths. The questions arises whether the converse is true, that is, whether $\mathcal{L}(G) = \mathcal{L}(G')$ implies that $G$ and $G'$ are isomorphic. The standing conjecture is that except for two couples of groups this is indeed true. We survey partial progress towards this problem. Relatedly, if $G \subset G'$ is a subgroup, then $\mathcal{L}(G) \subset \mathcal{L}(G')$. We also present recent results, obtained together with A. Geroldinger, on the problem of establishing (and ruling out) such inclusions in cases where $G$ is not a subgroup of $G'$.

A set A of integers is called 2-sum-free if it contains no elements x1, x2, x3 ∈ A satisfying x1+x2 = x3 where x1, x2 need not be distinct. Schur, in 1916, proved that, given a positive integer r, there exists a greatest positive integer N = S(2, 2, . . . , 2), where the number of 2’s equals r, and the 2’s are due to the two sums in the equation x1 +x2 = x3, with the property that the integer interval [1, N −1] can be partitioned into r 2-sum-free sets. The numbers S(2, 2, . . . , 2) are called Schur numbers. In 1982, Beutelspacher and Brestovansky, defined the generalized Schur number, denoted by M = S(k, k, . . . , k), where the number of k’s equals r, and the k’s are due to the k sums in the equation Ek : x1 + x2 + . . . + xk = xk+1, to be the least integer such that any r-coloring of [1, M] must admit a monochromatic solution to the equation Ek. Such numbers exist by Rado’s Theorem. Beutelspacher and Brestovansky showed that S(k, k) = k 2 + k − 1 for all k ≥ 2. In 2000, the following extension of the generalized Schur numbers, was defined by Robertson and Schaal. Let r ≥ 2 and ki ≥ 2 for i = 1, . . . , r, the r-color off-diagonal generalized Schur number, de- noted by S(k1, k2, . . . , kr), is defined as the least integer M such that any r-coloring of the integer interval [1, M] must admit a j-colored solution to equation Ekj : x1 + x2 + . . . + xkj = xkj+1 for some j with 1 ≤ j ≤ r. These numbers are given their name because of their sim- ilarity to the classical off-diagonal Ramsey numbers. Robertson and Schaal determined all values of the 2-color off-diagonal generalized Schur numbers. In this work, we show recent advances on Schur numbers and off- diagonal generalized Schur numbers.

For a Diophantine system of equalities or inequalities in $k$ variables, $\mathcal{L}$, we denote by $R(\mathcal{L}, r)$ the classical \emph{$r$-color Rado number}, that is, $R(\mathcal{L}, r)$ is the smallest integer, if it exist, such that for every $r$-coloring of $[1,R(\mathcal{L}, r)]$ there exist a monochromatic solution of $\mathcal{L}$. In 2003 Bialostocki, Bialostocki and Schaal studied the related parameter, $R(\mathcal{L}, \Z_r)$, defined as the smallest integer, if it exist, such that for every $(\Z_r)$-coloring of $[1,R(\mathcal{L}, \Z_r)]$ there exist a zero-sum solution of $\mathcal{L}$; in view of the Erd\H{o}s-Ginzburg-Ziv theorem, the authors state that the system $\mathcal{L}$ admits an EGZ-generalization if $R(\mathcal{L}, 2)= R(\mathcal{L}, \Z/k\Z)$. In this work we we prove that any linear inequality on three variables, $$\mathcal{L}_3: ax+by+cz+d<0,$$ where $a,b,c,d\in\Z$ with $abc\neq 0$, admits an EGZ-generalization except in the cases where there is no positive solution of the inequality. More over, we determine the corresponding $2$-color Rado numbers depending on the coefficients of $\mathcal{L}_3$. This is joint work with Amanda Montejano.

Folkman’s theorem asserts that in any red-blue colouring of [N], there is an n-set all of whose finite sums are the same colour. How large must N be in terms of n? Improving on Erdos—Spencer from the 80s, I’ll show that N must be at least doubly exponential in n.

For a graph $H$ and an integer $k\ge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $m\ge4$ vertices. For odd cycles, Bondy and Erd\H{o}s in 1973 conjectured that for all $k\ge1$ and $n\ge2$, $R_k(C_{2n+1})=n\cdot 2^k+1.$ Recently, this conjecture has been verified to be true for all fixed $k$ and all $n$ sufficiently large by Jenssen and Skokan; and false for all fixed $n$ and all $k$ sufficiently large by Day and Johnson. Even cycles behave rather differently in this context. Little is known about the behavior of $R_k(C_{2n})$ in general. In this talk we will present our recent results on Ramsey numbers of cycles under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. We prove that the aforementioned conjecture holds for all $k$ and all $n$ under Gallai colorings. We also completely determine the Ramsey number of even cycles under Gallai colorings. Joint work with Dylan Bruce, Christian Bosse, Yaojun Chen and Fangfang Zhang.

Let G be a graph on an even number of edges k and let n be a large integer. We will study under which conditions, if any, every {-1,1}-coloring of the edges of the complete graph on n vertices with certain minimum constraint on the number of edges of each color contains a zero-sum copy of G, that is, a copy of G such that the sum of its edges’ values is zero. The presented results include general unavoidable patterns, exact determination of the minimum constraints for certain graph families as well as a structural characterization of the graphs for which such a statement is possible. 

Let $G$ be an additive group. A subset of $G$ is \emph{sumfree} if it contains no solution of the equation $x+y-z=0$. For any finite subset $A \subseteq G$, we define its \emph{Schur degree} as the smallest number of sumfree subsets of $A$ covering it. For instance, the Schur number $S(n)$ can be described as the largest $N$ such that the integer interval $[1,N]$ has Schur degree $n$. In the first part of the talk, we shall extend the known relationship between $S(n)$ and the Ramsey number $R_n(3)$ by relating the latter with the Schur degree of certain special subsets of $G$. Despite more than a century in existence, the $S(n)$ remain poorly understood. The value $S(5)=160$ has recently been determined with massive computer help, while the best known theoretical upper bound on $S(5)$ remains at $305$. In the second part of the talk, we shall propose a new conjectural upper bound on $S(n)$ which, if true, would in particular imply $S(5) \le 225$. This is joint work with P. Revuelta.

A particular  weighted generalization of some classical zero-sum constants was first considered about fourteen years back. Many people got interested in this generalization and several conjectures and questions came up. Some of these  conjectures have been established and  some of the questions have been answered.  We give a survey of these. We also mention some applications and related open questions.

In this talk we discuss the following problems. $$\begin{enumerate} \item For a finite abelian group $G$ let $\mathsf s (G)$ denote the smallest integer $l$ such that every sequence $S$ over $G$ of length $|S| \ge l$ has a zero-sum subsequence of length $\exp (G)$. Specialising to $G=\mathbb{Z}_n^r$, the Erd\H{o}s-Ginzburg-Ziv theorem states that $\mathsf s (\mathbb{Z}_n)=2n-1$ and Reiher proved that $\mathsf s (\mathbb{Z}_n^2)=4n-3$. The speaker proved (some years ago) that for odd $n$ $\mathsf s (\mathbb{Z}_n^3)\geq 9n-8$ and (jointly with Edel, Geroldinger, Kubertin and Rackham) $\mathsf s (\mathbb{Z}_n^4)\geq 20n-19$. It is an open problem if possibly $\mathsf s (\mathbb{Z}_n^3)=9n-8$ holds for odd $n$, or not. \item Let $r_k(\mathbb{Z}_m^r)$ denote the maximal size of a set in $\mathbb{Z}_m^r$ without an arithmetic progression of $k$ distinct elements. There has been major progress in recent years. Croot, Lev and Pach considerably improved the upper bound of $r_3(\mathbb{Z}_4^r)$, and Ellenberg and Gijswijt extended this to $r_3(\mathbb{F}_q^r)$. This is the famous cap set problem. In joint work with Pach we considerably improved the constructions for lower bounds of $r_k(\mathbb{Z}_m^r)$. In particular $r_3(\mathbb{Z}_4^r)\geq \frac{9}{4\sqrt{\pi}} \cdot \frac{3^r}{\sqrt{r}}$. \end{enumerate}$$

An $n\times n$ matrix $S = \bmat s_{i,j} \emat$ with nonnegative coordinates is \emph{doubly stochastic} if all of its row and column sums are equal to 1, that is, if $$\rowsum_i(S) = \sum_{j=1}^n s_{i,j} = 1 \qquad\text{for $i= 1,\ldots, n$}$$ and $$\colsum_j(S) = \sum_{i=1}^n s_{i,j} = 1 \qquad\text{for $j = 1,\ldots, n$.}$$ Let $A = \bmat a_{i,j} \emat$ be an $n\times n$ matrix with positive coordinates. The alternate minimization algorithm of Sinkhorn-Knopp constructs sequences $(X_k)_{k=1}^{\infty}$ and $(Y_k)_{k=1}^{\infty}$ of positive diagonal matrices such that the limit matrix $$S = \lim_{k\rightarrow \infty} X_k A Y_k$$ exists and is doubly stochastic. The matrix $S$ is called the \emph{Sinkhorn-Knopp limit} of $A$. The attempt to compute explicit Sinkhorn-Knopp limits leads to problems involving Gr\" obner bases and algebraic number theory. In special cases we obtain sequences of rational numbers that converge rapidly to cubic irrationalities.

For a finite abelian group $(G,+)$ and $S= g_1 \dots g_k$ a sequence over $G$, we denote by $\sigma_\pm(S)$ the set of all $\pm$-weighted sums of $S$, that is, the set of all elements that can be written in the form $\sum_{i=1}^k w_i g_i$ with $w_i \in \{-1, +1\}$. We call $|S|=k$ the length of the sequence. We say that $S$ is a $\pm$-weighted zero-sum sequence if $0 \in \sigma_\pm(S)$ and we denote the set of all these sequences by $\mathcal{B}_\pm(G)$. It is easy to see that this set forms a submonoid of the monoid of all sequences over $G$. In this talk we present various results on the arithmetic of these monoids. We call a non-empty $\pm$-weighted zero-sum sequence $S$ a minimal $\pm$-weighted zero-sum sequence if $S$ cannot be factored into two non-empty $\pm$-weighted zero-sum sequence. These sequences are the irreducible elements, or atoms, of the monoid $\mathcal{B}_\pm(G)$; we denote this set by $\mathcal{A}(\mathcal{B}_\pm(G))$. As is common in factorization theory a particular focus is given to sets of lengths. For $S \in \mathcal{B}_\pm(G)$ we say that $l$ is a factorization-length of $S$ if there exist $A_1, \dots , A_l \in \mathcal{A}(\mathcal{B}_\pm(G))$ such that $S = A_1 \dots A_l$. We denote the set of all $l$ that are a factorization-length of $S$ by $\mathsf{L}(S)$. It is easy to see that for every non-empty $\pm$-weighted zero-sum sequence $S$ this is a finite set of positive integers, and the elasticity of $S$, denoted $\rho(S)$, is defined as $\max \mathsf{L}(S) / \min \mathsf{L}(S)$. The elasticity of the monoid $\mathcal{B}_\pm(G)$, denoted $\rho(\mathcal{B}_\pm(G))$, is defined as the maximum of all $\rho(S)$. We present a weighted form of the Davenport constant, which is different from the weighted Davenport constant that appears in the literature. Namely, we set $\mathsf{D}(\mathcal{B}_\pm(G)) = \max \{ |A| \colon A \in \mathcal{A}(\mathcal{B}_\pm(G))\}$. It can he shown that $\rho(\mathcal{B}_\pm(G)) = \mathsf{D}( \mathcal{B}_\pm(G) )/2$ for every non-trivial finite abelian group. We then proceed to investigate $\mathsf{D}( \mathcal{B}_\pm(G) )$. For groups of odd order this constant turns out to be equal to the classical Davenport constant \emph{without weights}. However, for groups of even order this is not necessarily true and we determine the exact value for cyclic groups of even order. In addition we study unions of sets of lengths. For some positive integer $k$, one considers the set $$\mathcal{U}_k( \mathcal{B}_\pm(G) ) = \bigcup_{S \in \mathcal{B}_{\pm}(G), \, k \in \mathsf{L}(S)} \mathsf{L}(S).$$ We show that these sets are intervals of integers. This joint work with S. Boukheche, K. Merito and W. Schmid.

In this talk we will discuss lower and upper bounds for the size of $k$-AP-free subsets of $\mathbb{Z}_m^n$, that is, for $r_k(\mathbb{Z}_m^n$, in certain cases. Specifically, we will discuss some lower bounds given by Elsholtz and myself. In the case $m=4,k=3$ we present a construction which gives the tight answer up to $n\leq 5$ and point out some connection with coding theory. We will also mention some open questions (and some partial answers) about related linear algebraic problems.

In this talk, we consider problems and results that go in the opposite direction of the classical theorems in the discrepancy theory. The following statement gives a flavor of our approach. Let $t$, $k$ and $q$ be integers such that $q \ge 0$, $0 \le t < k$, and $t \equiv k \,({\rm mod}\, 2)$, and take $s \in [0,t+1]$ as the unique integer satisfying $s \equiv q + \frac{k-t-2}{2} \,({\rm mod} \, (t+2))$. Then, for any integer $$n \ge \frac{1}{2(t+2)}k^2 + \frac{q-s}{t+2}k - \frac{t}{2} + s$$ and any function $f:[n]\to \{-1,1\}$ with $|\sum_{i=1}^nf(i)|\leq q$, there is a block of $k$ consecutive terms ($k$-block) $B\subset [n]$ with $|\sum_{x\in B}^nf(x)|\leq t$. Moreover, this bound is sharp for all the parameters involved and a characterization of the extremal sequences is given. This is a joint work with Yair Caro and Adriana Hansberg.

Let $\a=(a_1,\ldots,a_n)$ and $\b=(b_1,\ldots,b_m)$ be vectors whose entries are positive integers. Let $\S(\a,\b)$ denote the set of all nonnegative solutions $(\x,\y)$, where $\x=(x_1,\ldots,x_n)$ and $\y=(y_1,\ldots,y_m)$, of the linear Diophantine Diophantine equation $x_1a_1+\ldots x_na_n=y_1b_1+\ldots y_mb_m$. A solution is called {\em minimal} if it cannot be written as the sum of two nonzero solutions in $\S(\a,\b)$. The set of all minimal solutions, denoted by $\H(\a,\b)$, is called the {\em Hilbert basis} of the set of all solutions $\S(\a,\b)$. For $1\leq i\leq n$ and $1\leq j\leq m$, the solution $\g_{i,j}=(b_j\e_i,a_i\e_{n+j})$ of the above Diophantine equation, where $\e_k$ is the $k$th standard unit vector of $\R^{n+m}$, is called a {\em generator}. In this talk, we discuss a recent result which shows that every minimal solution in $\H(\a,\b)$ is a {\em convex combination} of the generators and the zero-solution.

The anti-Ramsey number of Erd\"os, Simonovits and S\'os from 1973 has become a classic invariant in Graph Theory. To extend this invariant to Matroid Theory, we use the  heterochromatic number $hc(H)$ of a non-empty hypergraph $H$. The  heterochromatic number  of $H$ is the smallest integer $k$ such that for every colouring of the vertices of $H$ with exactly $k$ colours, there is a totally multicoloured hyperedge of $H$.  Given a  matroid $M$, there are several hypergraphs over the ground set of $M$ we can consider, for example, $C(M)$, whose hyperedges are the circuits of $M$, or $B(M)$, whose hyperedges are the bases of $M$. We determine  $hc(C(M))$  for general matroids and characterise the matroids with the property that  $hc(B(M))$ equals   the rank of the matroid.  Finally, we extend the known result about   the anti-Ramsey number of 3-cycles in complete graphs to the heterochromatic number  of 3-circuits in  projective  geometries over finite fields, and we propose a problem very similar to the famous problem on the anti-Ramsey number of the $p$-cycles. joint work with  J.J. Montellano-Ballesteros.

Ramsey's theorem is a purely combinatorial result and it works for arbitrary colorings. However, the interesting colorings usually have some additional structure. For example, Ramsey's theorem easily implies the Erdős-Szekeres theorem but doesn't give a very good bound. Among other things, the coloring used is defined by some algebraic conditions and, as it turns out, for these colorings there is a stronger version of Ramesy's theorem. In this talk I will define these colorings and state what is know about these Ramsey numbers.

We say that a graph $H$ is {\it planar unavoidable} if there is a planar graph $G$ such that any red/blue coloring of the edges of $G$ contains a monochromatic copy of $H$, otherwise we say that $H$ is {\it planar avoidable}.  It follows from the Four-Color Theorem and a result of Gon\c{c}alves that if a graph is planar unavoidable then it is  bipartite and outerplanar.  We prove that the cycle on $4$ vertices and any path are planar unavoidable.  In addition, we prove that all trees of radius at most~$2$ are planar unavoidable and there are trees of radius~$3$ that are planar avoidable.  We also address the planar unavoidable notion in more than two colors. This is a joint work with Carsten Thomassen, Ursula Schade, and Torsten Ueckerdt.