Abstracts

Here are the abstracts of the talks. Click on the title for slides (when available)!

Ryan Alweiss (University of Cambridge) Monochromatic Sums and Products over Q 

Abstract: Hindman's finite sums theorem states that in any finite coloring of the naturals, there is an infinite sequence all of whose finite subset sums are the same color. In 1979, Hindman showed that there is a finite coloring of the naturals so that no infinite sequence has all of its pairwise sums and pairwise products the same color. Hindman conjectured that for any n, a finite coloring of the naturals contains nnumbers all of whose subset sums and subset products are the same color. In this paper we prove the version of this statement where we color the rationals instead of the integers. In other words, we show that the pattern {∑i∈Sxi,∏i∈Sxi}, where S ranges over all nonempty subsets of [n], is partition regular over the rationals.

Olaf Beyersdorff (Friedrich-Schiller University of Jena) Proofs and circuits for quantified polynomials

Abstract: We consider a quantified version of polynomial calculus and explore its proof complexity. This includes a tight characterisation by an algebraic version of decision lists and relations to algebraic circuits. Using this characterisation we obtain size-degree relation and show several new lower bounds. We also place these results into the wider context of proof complexity for quantified Boolean formulas.

Sam Buss (University of California, San Diego) Propositional Proof Complexity of the Kneser-Lovász Theorem 

David Conlon (California Institute of Technology) Off-diagonal Ramsey numbers  

Abstract: We discuss recent progress on the study of off-diagonal Ramsey numbers r(H, n), the smallest N such that every red/blue-coloring of K_N contains either a red copy of H or a blue copy of K_n. In particular, we describe a connection between such numbers and the classical Zarankiewicz problem and look at the analogous problem for hypergraphs. Joint work with (subsets of) Jacob Fox, Ben Gunby, Xiaoyu He, Sam Mattheus, Dhruv Mubayi, Andrew Suk, Jacques Verstraëte. 

Michele D'Adderio (University of Pisa) q,t-combinatorics and sandpiles 

Abstract: In 1987 Bak, Tang and Wiesenfeld introduced their famous sandpile model as a first system showing self-organized criticality. In 1988 Macdonald introduced his famous symmetric polynomials. Each of these two discoveries produced a huge amount of research that is still going on intensely today. But until recently, these two lines of research went on without any relevant communication. In this talk we show how the combinatorics generated by these two important mathematical objects come together in a surprising way, proving that a strong interaction between these two topics is now inevitable.

Noé de Rancourt (Université de Lille) On amalgamation-elementary functors

Abstract : Many classical finite Ramsey theorems can be expressed as the satisfaction of the so-called Ramsey property in a suitable category. Many proofs of implications between finite Ramsey theorems can be found in the litterature, and most of them can be translated in the categorical language as the construction of an amalgamation-elementary functor, a functor preserving the Ramsey property. Amalgamation-elementary functors can be defined as those being elementary for a certain class of formulas in the language of category theory. In this talk, I will discuss questions and possible research directions related to amalgamation-elementary functors; one of them is whether it would be possible to mimic classical methods from model theory in order to prove amalgamation-elementarity without exhibiting explicit witnesses.

Natasha Dobrinen (University of Notre Dame) Big Ramsey degrees: forcing, non-forcing, and computability-theoretic aspects

Abstract: The recent surge of research on big Ramsey degrees of homogeneous structures with forbidden substructures began with the speaker's theorem that the triangle-free Henson graph has finite big Ramsey degrees.  The method of forcing, applied to do an unbounded search for a finite homogeneous object (never going to a generic extension) was a key component of that proof.  In this talk, we will survey the current state of the art in big Ramsey degrees and big Ramsey structures and the various proof methods which are now available.  We will also discuss computability-theoretic aspects, including work of Cholak, Dobrinen, McCoy, and Towsner which makes central use of coding trees while bringing the forcing arguments into an ACA0 framework.

Mirna Džamonja (IRIF: CNRS et Université de Paris-Cité) Properties preserved by Chu transforms

Abstract: The category of Chu spaces was first investigated by Michael Barr and his student Po-Hsiang Chu in 1979. In 2000 Johan van Benthem shifted the perspective from the categorical point of view to the model-theoretic one. 

We extend that perspective, answering some of his questions and introducing new paradigms. In particular, van Benthem isolated a class of properties, the flow formulas,which are preserved by all Chu transforms. However, in 2021 Džamonja and Väänänen considered a special kind of Chu transforms, satisfying a density condition, and used them to compare abstract logics, in particular showing that they preserve compactness. Furthermore, Chu transforms between graphs do always satisfy this density condition. This motivates the problem of characterising which properties are preserved by dense Chu transforms.

We solve this problem by isolating the class of inconsistency-flow formulas, which are flow formulas with an added predicate to express inconsistency. Our main result thus characterizes exactly what is preserved by the sublogic relation, at least for the first-order fragment. We also discuss further applications to topological spaces and and graph colourings. 

Damir Dzhafarov (University of Connecticut) The Ginsburg-Sands theorem and computability

Abstract: In their 1979 paper ``Minimal Infinite Topological Spaces'', Ginsburg and Sands proved that every infinite topological space has an infinite subspace homeomorphic to exactly one of the following five topologies on $\omega$: indiscrete, discrete, initial segment, final segment, and cofinite. The proof, while nonconstructive, features an interesting application of Ramsey's theorem for pairs (RT22). We analyze this principle in computability theory and reverse mathematics, using Dorais's formalization of CSC spaces. Among our results are that the Ginsburg-Sands theorem for CSC spaces is equivalent to ACA0, while for Hausdorff spaces it is provable in RCA0. Furthermore, if we enrich a CSC space by adding the closure operator on points, then the Ginsburg-Sands theorem turns out to be equivalent to the Chain-antichain principle (CAC). The most surprising case is that of the Ginsburg-Sands theorem restricted to T_1 spaces. Here, we show that the principle lies strictly between ACA0 and RT22, yielding perhaps the first natural theorem of ordinary mathematics (i.e., conceived outside of logic) to occupy this interval. I will discuss the proofs of both the implications and separations, which feature several novel combinatorial elements, and survey a new class of purely combinatorial principles below ACA0 and not implied by RT22 revealed by our investigation. 

This is joint work with Heidi Benham, Andrew DeLapo, Reed Solomon, and Java Darleen Villano.

David Fernández-Bretón  (Instituto Politécnico Nacional, Mexico City) Owings-like theorems for infinitely many colours or finite monochromatic sets

Abstract: An old unsolved question by Owings asks whether for every colouring of the natural numbers in two colours, it is possible to obtain an infinite set X such that X+X={x+y|x,y ∈ X} is monochromatic (an old theorem of Hindman states that the answer is "no" with three colours, but the original question remains unsolved). Inspired by this, we ponder the analogous question for an arbitrary Abelian group, varying the number of colours and the size of the monochromatic set required. The main results obtained are:

1. (finitely many colours, finite monochromatic set) For an Abelian group G, for every finite n,r it is the case that every colouring of G in r colours admits a set X of cardinality n such that X+X is monochromatic if and only if G/G_2 is infinite, where G_2={x ∈ G|2x=0}.

2. (infinitely many colours, infinite monochromatic set) For every infinite Abelian group G there exists a colouring of G with countably many colours such that for no infinite subset X can the set X+X be monochromatic.

3. (infinitely many colours, finite monochromatic set) If G is an infinite Abelian group which is either countable, or without elements of order 2, or a torsion group without elements of order 4, then there exists a colouring of G with countably many colours such that for no subset X with more than one element can the set X+X be monochromatic. On the other hand, we find examples of infinite Abelian groups (uncountable, with many elements of order 2 and 4) for which the previous statement is false.

This is joint work with E. Sarmiento Rosales and G. Vera.

Jeffry L. Hirst (Appalachian State University) Pigeonhole:  Old and preliminary results

Abstract: The infinite pigeonhole principle (Ramsey’s theorem for singletons) asserts that whenever the natural numbers are finitely colored, some color must appear infinitely often.  For a given coloring, one might ask how many colors or exactly which colors appear infinitely often.  This talk will include old and recent results from reverse mathematics, higher order reverse mathematics, and Weihrauch analysis.

Maria-Romina Ivan (University of Cambridge) Euclidean Ramsey sets and the block sets conjecture 

Abstract: A set $X$ is called Euclidean Ramsey if, for any $k$ and sufficiently large $m$, any $k$-colouring of $\mathbb{R}^m$ contains a monochromatic congruent copy of $X$. This notion was introduced by Erd\H{o}s, Graham, Montgomery, Rothschild, Spencer and Straus. They asked if a set is Ramsey if and only if it is spherical, meaning that it lies on the surface of a sphere. It is not too difficult to show that if a set is not spherical, then it is not Euclidean Ramsey either, but the converse is very much open despite extensive research over the years. On the other hand, the block sets conjecture is a purely combinatorial, Hales-Jewett type of statement. It was introduced in 2010 by Leader, Russell and Walters. If true, the block sets conjecture would imply that every transitive set (a set whose symmetry group acts transitively) is Euclidean Ramsey. Similarly to the first question, the block sets conjecture remains very elusive. In this talk we discuss recent developments on the block sets conjecture and their implications to Euclidean Ramsey sets.

Imre Leader (University of Cambridge) Sparse Partition Regularity

Abstract: A system of equations is called `partition regular' if, whenever the natural numbers are finitely coloured, there is a monochromatic solution to the system of equations. In `sparse' versions, we attempt to replace the natural numbers with a set having less structure. The talk will start with background on finite systems (where a lot is known) and will then move on to infinite systems (where essentially nothing is known). No knowledge of any of these concepts will be assumed.

Ludovic Levy Patey (CNRS, IMJ-PRG-Université Paris Cité) Partial conservation of Ramsey's theorem for pairs

Abstract: Ramsey's theorem for pairs (RT22) states that for every finite coloring of the edges of the infinite clique, there exists an infinite subclique whose edges are monochromatic. The quest for the characterization of the first-order part of RT22 is an important part of modern reverse mathematics. It is known to follow from Sigma^0_2-induction and to imply Sigma^0_2-collection. In this talk, we review some important results about this question, and outline the proof that RT22 is Pi04 conservative over RCA0 + BSigma2 using an elaboration of the indicator method.

This is a joint work with Quentin Le Houérou and Keita Yokoyama.

Alberto Marcone (Università di Udine) The barrier Ramsey theorem

Abstract: This talk deals with generalizations of the classic finite Ramsey theorem that substitute "set of cardinality n" with some notion of "large set". The prototype of these results is of course the statement that Paris and Harrington showed unprovable in PA in 1977. Since then several extensions were considered, typically using notions of α-largeness for α an ordinal below ε_0. Our results extend this approach by dealing with notions of largeness encapsulated by barriers (one of the combinatorial ingredients of better quasi-order theory). We use these largeness notions almost everywhere in the statements (the only cardinality left is the number of colors). Quite surprisingly, in many cases we obtain tight bounds on these "generalized Ramsey numbers", in contrast with the classic finite case where tight bounds are known only for very few cases involving very small numbers.

This is joint work with Antonio Montalbán and Andrea Volpi.

Amador Martin-Pizarro (Albert-Ludwigs-Universität Freiburg) On three arithmetic progressions for definable sets

Abstract: Roth's famous theorem studies whether a subset A of positive density of 1, ..., N contains an arithmetic progression of length three (in short 3-AP), that is, an element a in A as well as some g ≠ 0 with a, a+g and a+2g all in A.  Most of the combinatorial proofs of this theorem yield not only the existence of a 3-AP but rather a dense proportion of such.

In this talk, we will introduce an ongoing work with D. Palacín (UCMadrid) on model-theoretic methods in order to study variations of Roth's theorem, among others regarding uniform results for finite fields.

Rosario Mennuni (University of Pisa) Ultrafilters, congruences, and profinite groups

Abstract: It is a well-known fact, with important applications in additive combinatorics and Ramsey theory, that the usual sum of integers may be extended to the space of ultrafilters over Z, yielding a compact right topological semigroup. The analogous construction also goes through for the product.

Recently, B. Šobot introduced two (ternary) notions of congruence on the space above. I will talk about joint work with M. Di Nasso, L. Luperi Baglini, M. Pierobon and M. Ragosta, in which the study of these congruences led us to isolate a class of ultrafilters enjoying characterisations in terms of tensor products, directed sets, profinite groups, and more.

Jaroslav Nešetřil (Charles University, Prague) Structural Ramsey Theory

Abstract: Ramsey classes and A-Ramsey classes are studied intensively both in finite and infinite. We survey the recent development.

Pavel Pudlák (Mathematical Institute of the Czech Academy of Sciences) Colorings of k-sets with low discrepancy

Abstract: According to Ramsey theorem, for every k and n, if N is sufficiently large, then for every 2-coloring ψ of k-element subsets of [N] there exists a monochromatic set S⊂ [N] |S|=m. The least such number is denoted by R_k(m) and fairly good bounds on this number are well-known. Whereas Ramsey theorem ensures the existence of monochromatic subsets, in this talk we will be interested in a question which is in a sense opposite. We want to know for which parameters k,m and N, there are colorings γ of {[N]\choose k} by two colors with the property that the restriction of γ on any set S ⊂ [N] of size ≥m has low discrepancy. We will show that even if N is not much smaller than R_k(m) and m is only slightly larger than k, there exist colorings with low discrepancy.

This is a joint work with Vojtech Rodl.

Mariaclara Ragosta (Università di Pisa) Central sets and infinite monochromatic exponential patterns

Abstract: Schur's Theorem (1916) states that for every finite coloring of N there exists a monochromatic triple a, b, a+b Several decades later, Folkman extended this statement by including in a same color arbitrarily long sequences and all finite sums from them. A breakthrough was made in 1974 by Hindman, who showed, in the same setting, the existence of a unique infinite sequence such that all finite sums are monochromatic, and one year later the theorem was extended to all associative operations.

In this talk we explore the case of exponentiation, first investigated by Sisto (2011) and recently by Sahasrabudhe (2018). The latter proved a version of Folkman's Theorem for product and exponentiation at the same time. In our main theorem we realise for the exponentiation the passage from finite to infinite made by Hindman for the sum, by showing that for every finite coloring of N there exists an infinite sequence such that all finite exponentiations are monochromatic.

We finally extend the theorem to a larger class of binary non-associative operations which somehow behave in the same manner as exponentiation.

This is joint work with Mauro Di Nasso.

Salvatore Scamperti (Università di Torino) Injective continuous quasi-order

Abstract: Given topological spaces A, B, we say A ≤_inj B if and only if there exists an injective continuous function f : A → B. We prove  that continuous injectability is a linear well quasi-order of length ω _1 + 3 on subsets of R that are either countable or that contain an isomorphic copy of the Cantor space.

Among spaces not contained in R, it is already known that continuous injectability on [0, 1]^2 is an analytic complete  quasi-order. The situation for spaces between R and [0, 1]^2 is unknown. We explore continuous injective quasi-order on closed subsets of one of them: the Cantor fence 2^N x [0, 1]. In particular, we identify some special points, called trouble witnesses, and show that continuous injectability is a well quasi-order on closed subsets of the Cantor fence that do not have trouble witnesses. 

This is joint work with Raphaël Carroy.

Philippe Schnoebelen (LSV, CNRS, ENS Paris-Saclay) Reasoning about subwords and subsequences

Abstract: In formal languages, a subsequence of a word is called a subword - or sometimes a "scattered subword" - and should not be confused with a factor which is a contiguous block of letters extracted from the original word.

Subwords do not behave as nicely as factors and many interesting problems in logic, combinatorics and algorithmics are harder for subwords than for factors.  In this talk I shall consider two instances of this phenomenon: the Post embedding problem and the decidability of subword constraints.

Dmitry Sokolov (Steklov Institute of Mathematics) Random log(n)-CNF are Hard for Cutting Planes (Again)

Abstract: In this talk, we will try to present a self-contained simplified proof of the hardness of random log(n)-CNF formulas in Cutting Planes. This result was proven by Hrubes, Pudlak, and independently by Fleming, Pankratov, Pitassi and Robere. In both papers, the authors reduce the considered question to the lower bound on monotone circuits and use Jukna's criteria to show the desired result. Instead of it, we do some direct bottleneck counting and discuss related open problems.

Navid Talebanfard (University of Sheffield) Local Enumeration and Majority Lower Bounds

Abstract: What is the largest number of satisfying assignments of minimum Hamming weight in a k-CNF with no satisfying assignment of Hamming weight less than n/2? This problem is intimately related to the exact complexity of k-SAT as well as depth-3 circuit complexity of the Majority function. We give a new randomized algorithm to enumerate these satisfying assignments for k = 3.

Joint work with Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, and Michael Saks