Talks

I'll give concrete examples to show how one very simple lemma can be used to build counterexamples to many reasonable conjectures about the partition regularity of infinite systems of linear equations.

On the strength of some natural restrictions of Hindman's Finite Sums Theorem

Hindman, Leader and Strauss posed the following problem in 2003: Is there a proof of Hindman's Finite Sums Theorem restricted to sums of one or two distinct elements that does not also prove the full version of the theorem? One way to make this question precise is to use concepts from reverse and computable mathematics. After fixing a reasonable base theory one can formally study implications and non-implications between theorems. Equivalently, one can measure the complexity of solutions (e.g., homogeneous sets) to instances of a combinatorial theorem (e.g. finite colorings of the positive integers). The strength of Hindman's Finite Sums Theorem in this framework has been studied since the 1987, but a huge gap remains between the known lower and upper bounds. I will present some recent results on various restrictions of Hindman's Finite Sums Theorem in this framework. In particular I will show that the known lower bound for the full theorem is already satisfied by its restriction to sums of one or two distinct elements and I will present some natural variants that also admit a much better upper bound than the full theorem. I will mostly focus on results that can be obtained by combinatorial reasoning.

Twisted recurrence via polynomial walks

We will show how polynomial walks can be used to establish a twisted recurrence for sets of positive density in Z^d. In particular, we will demonstrate that if Γ ≤ GL_d(Z) is finitely generated by unipotents and acts irreducibly on R^d, then for any set B ⊂ Z^d of positive density, there exists k ≥ 1 such that for any v ∈ kZ^d one can find γ ∈ Γ with γv ∈ B − B. Also we will show a non-linear analog of Bogolubov's theorem – for any set B ⊂ Z^2 of positive density, and p(n) ∈ Z[n], p(0) = 0, deg p ≥ 2, there exists k ≥ 1 such that kZ ⊂ {x − p(y) | (x, y) ∈ B − B}. Joint work with Kamil Bulinski.

Arithmetic structure in independent sets of triangle-free graphs

David Gunderson, University of Manitoba

By Ramsey's theorem, triangle-free graphs on many vertices have large independent sets. In 1995, Erd\H{o}s asked if independent sets in triangle-free graphs on the integers are rich enough to solve $x+y=z$. This talk reviews the work of a number of authors in answering this question, its extensions, and similar questions for other graphs on vertices with an algebraic structure.

SAT and Ramsey Theory

Many problems from Ramsey theory can be translated into propositional logic and attacked by SAT solvers (satisfiability solvers -- solving propositional logic). The most recent success' were the solution of the Boolean Pythagorean Triples Problem, showing that a^2 + b^2 = c^2 is 2-regular, and the determination of the Schur Number Five as (indeed) 160. For the former, and a general introduction into the field, see the CACM article "The science of brute force" https://cacm.acm.org/magazines/2017/8/219606-the-science-of-brute-force , for the latter see https://arxiv.org/abs/1711.08076 .

Both solutions involved massive computations, resulting in proofs of sizes 200TB resp. 2000TB, and both are based on a general SAT solving paradigm discovered by me when computing van der Waerden type numbers . This paradigm, Cube-and-Conquer, is also succesful on industrial problems, and thus could be considered as a crossover industrial application of Ramsey theory.

In my talk I will first give an introduction into SAT, and how to handle (certain) problems from Ramsey theory. Then follows a discussion on the usefulness of such computations of Ramsey type numbers, from various perspectives. I'll finish with speculations on deeper mathematical connections of SAT and Ramsey theory.

Hindman's Finite Sums Theorem states that for every finite coloring of the set N of positive integers there exist infinitely many positive integers x_1 < x_2 < ... such that all their finite nonempty sums without repetitions are colored the same. We consider a variation of this result looking at k-term sums, k fixed, and the summands have coefficients according to a fixed vector (a_1, ... , a_k). In Hindman's Finite Sums Theorem the coefficients are all one.

Suppose that N is 2-coloured. We show that then there are infinitely many monochromatic solutions to x+y=z^2. The proof uses various results from additive combinatorics and analytic number theory. In particular we make use of the arithmetic regularity lemma to find a long monochromatic AP. By assuming that we have no monochromatic solutions to x+y=z^2 we can apply an iterative argument to find longer and longer monochromatic AP's, until we eventually reach a contradiction. This is joint work with Ben Green.

Rado's criterion over higher powers

Sean Prendiville, University of Manchester

Schur's theorem states that however one finitely colours the positive integers, there is always a solution to the equation x+y = z in which each variable receives the same colour. Rado completely characterised which linear equations possess this property and which do not. We discuss analogues of these results for certain non-linear Diophantine equations.

A famous result of van der Waerden states that any finite coloring of the naturals has arbitrarily long monochromatic arithmetic
sequences. We will discuss some Ramsey related problems concerning the structure of the sets of differences which can not be avoided. This is a joint work with João Guerreiro and Imre Ruzsa.

Partition regular matrices play a significant role in Ramsey Theory, as several of the important classical theorems of Ramsey Theory are equivalent
to the statement that certain matrices are partition regular. I shall talk about some of the well-known results in this area, and discuss some recent new results.

After Luca Zamboni's talk about the caracterisation of periodicity of infinite word through the existence of coloring avoiding monochromatic factorisation, we will deal with a more recent question about the links beetween ultimate periodicity of a word x and existence of coloring such that x admits no suffix having a monochromatic factorisation, with the extra condition that the ordered concatenation of two factors of this factorisation belongs to the monochromatic set.

Hindman's theorem implies that there always exists such an infinite word y in the subshift of x, and the goal is to make it impossible that this is a suffix of x. We will show an example, and present some reductions for the problem, and a final construction.

This kind of problems shows the limits of Ramsey theory in combinatorics of words, by building some explicit coloring, with sometimes optimal number of colors, forbidding the apparition of monochromatic substructures.

In 2006 T. Brown asked the following question in the spirit of Ramsey theory: Given a non-periodic infinite word $x=x_1x_2x_3\cdots$ with values in a set $A,$ does there exist a finite colouring $\varphi$ of the free semigroup $A^+$ relative to which $x$ does not admit a monochromatic factorisation. , i.e., a factorisation of the form $x=u_1u_2u_3\cdots$ with $\varphi(u_i)=\varphi(u_j)$ for all $i,j\geq 1$? I will discuss this and related questions leading to an (optimal) affirmative answer to Brown's question.

Online user: 1