Logical methods in Ramsey theory and related topics

10 Jul 2023, 00:10 → 11 Jul 2023, 23:00 Europe/Rome

Aula Magna (Dipartimento di Matematica)

Alessandro Berarducci (Università di Pisa), Lorenzo Luperi Baglini (Università degli studi di Milano), Rosario Mennuni, Moreno Pierobon (Università di Pisa), Mariaclara Ragosta (Università di Pisa)

This workshop is centered around the interplay between mathematical logic and combinatorics. The connections between these two areas have historically been fundamental for many of their developments; arguably, the most famous exemplification of this fact is Ramsey's Theorem.

Its main goals are to disseminate information about various logical techniques used in several areas of combinatorics and related topics, bring together researchers with different backgrounds, and encourage their collaborations and interactions, especially on topics connecting different areas of mathematics.

The covered topics include (but are not limited to):

• Nonstandard methods in combinatorics and Ramsey theory
• Model-theoretical methods in density theory for semigroups
• Reverse mathematics of combinatorial principles
• Set theory and ultrafilter methods
• Computational limits to finite provability and proof complexity
• Quasi-orders and applications

 

In order to foster diversity and facilitate the participation of those with limited funds, students, early career researchers, and participants from disadvantaged countries will be able to apply for financial support.

Participants travelling with young children will be able to apply for child care support.

This conference promotes gender equality.

 

A welcome cocktail will be held on Sunday the 9th, from 17 to 18:30, in the main hall of the Math Department (Largo Bruno Pontecorvo 5, Pisa).

 

 

Invited speakers: 

• Vieri Benci (Università di Pisa)
• Lorenzo Carlucci (Sapienza Università di Roma)
• Raphael Carroy (Università di Torino)
• Lorenzo Fiaschi (Università di Pisa)
• Francesco Fiorini (Università di Pisa)
• Mirna Džamonja (CNRS - Université de Paris)
• Marco Forti (Università di Pisa)
• Nicola Galesi (Sapienza Università di Roma)
• Karel Hrbáček (City College of New York)
• Renling Jin (College of Charleston)
• Steven Leth (University of Northern Colorado)
• Martino Lupini (Università di Bologna)

 

Organising committee:

• Alessandro Berarducci
• Lorenzo Luperi Baglini
• Rosario Mennuni
• Moreno Pierobon
• Mariaclara Ragosta

 

 

---

SCAM WARNING: Some partecipants have received false messages regarding travel for the conference. Please ignore these messages! 

We will not ask for payments or credit card numbers by e-mail.

We will communicate with partecipants only via the e-mail address ramsey2023@cs.dm.unipi.it

 

 

FINANCIALLY SUPPORTED BY: 

Università di Pisa, PRIN 2017: "Mathematical Logic: models, sets, computability", Associazione Italiana di Logica e sue Applicazioni (AILA)

 

        

Monday, 10 July

09:00 → 09:20 Registration

09:30 → 10:15 Continuous reducibility is a well-quasi-order on continuous functions with Polish 0-dimensional domains

Given topological spaces $X,X',Y,Y'$, and two functions $f:X\to Y$ and
$f':X'\to Y'$, we say that $f$ reduces continuously to $f'$ when there is a
pair $(\sigma,\tau)$ of continuous functions such that $f=\tau\circ f'\circ\sigma$.
This quasi-order has first been introduced by Weihrauch in the context of Computable
Analysis at the beginning of the 1990s. It has recently received interest in
Descriptive Set Theory.
With Yann Pequignot, we proved that on the class of continuous functions with Polish
0-dimensional domains, there are no infinite antichains and no infinite strictly
descending chains for continuous reducibility. In other words, continuous
reducibility is a well-quasi-order on this class of functions.
I will give some context for this result and outline the proof.

Speaker: Raphael Carroy (Università di Torino)

230710carroy.pdf

10:20 → 11:05 Capturing convergence through changing the logic

In recent years we have witnessed an unprecedented confluence of methods from discrete and continuous mathematics, especially in subjects having to do with logic and topology. One can cite fields such as continuous model theory, homotopy type theory and, most relevant to this talk, combinatorial limits. The latter have started from the notion of graphons and have been generalised to other objects, including the very general Stone pairings. In this subject one looks at uncountable limits of a countable sequence of finite objects, with various logical properties that carry through. In the context of first order logic, one can think of Los’s theorem for ultraproducts, but various other transfer theorems have been obtained in this other contexts. In this talk we shall review some of these notions, including a Ramsey theorem about ultraproducts, and then connect them with the study of abstract logics through new satisfaction relations.

Speaker: Mirna Džamonja (CNRS - Université de Paris)

Dzamonja.pdf

11:10 → 11:40 Coffee break

11:40 → 12:05 Numerical Non-standard Calculus: Applications and Software Implementation

Non standard analysis and engineering applications have long remained two separate things. More recently, new computational paradigms have been proposed that seem able to close this gap. One of them is the non standard model built upon Benci and Di Nasso’s Alpha Theory, within which in 2021 Benci and Cococcioni introduced a fixed length binary encoding (along with truncation operators) for non standard numbers [1]. This achievement paved the way for an efficient implementation of non standard computations within computers, that is the numerical representation and manipulation of non standard numbers. Even if the journey through numerical, non standard computations is still at the beginning, the research has already showed encouraging benefits of their application, especially in the context of deterministic and stochastic multi objective lexicographic optimization. The present talk will provide an overview of them, focusing on two relevant engineering applications where the efficacy of a non standard computational framework has already been tested: multi objective convex quadratic programming based on the interior point method [2] and deep reinforcement learning.
Work partially funded by the Italian Ministry of Education and Research (MUR), ForeLab project (Departments of Excellence), and by PNRR M4C2 Investimento 1.3, Partenariato Esteso PE00000013 ”FAIR Future Artificial Intelligence Research”

[1] Benci, V. and Cococcioni, M. (2021) “The Algorithmic Numbers in Non Archimedean Numerical Computing Environments”, Descrete And Continuous Dynamical Systems Series S, 14(5):1673 1692, https://doi.org/10.3934/dcdss.2020449
[2] Fiaschi, L. and Cococcioni, M. (2022) “A Non Archimedean Interior Point Method and Its Application to the Lexicographic Multi Objective Quadratic Programming”, Mathematics, 10(23):4536, https://doi.org/10.3390/math10234536

Speaker: Lorenzo Fiaschi (Università di Pisa)

Slide_Fiaschi.pdf

12:10 → 12:30 Initial Applications of Alpha Theory in Telecommunication Engineering

Heavy-tailed distributions with infinite variance are crucial in telecommunication engineering as they can model real-world phenomena accurately. They describe various traffic characteristics, such as file sizes on web servers and corresponding transmission times, CPU times, idle times, peak rates and connection times. However, simulating these distributions presents numerical challenges due to infinite variance and slow convergence. To address these issues, we developed a Matlab toolbox based on the Alpha Theory developed by Benci and Di Nasso (and the associated concept of Euclidean numbers). This approach allows for a new Euclidean Heavy-Tailed Lognormal distribution with finite mean and numerically verifiable infinite variance, recently appeared in [1]. Finally we will discuss its use in Queueing Theory, where numerous estimation and performance prediction formulations for queues have inherent mathematical limitations when considering infinite or infinitesimal values. As an example, we will show how the Euclidean LogNormal distribution could be used in combination with the Pollaczek-Khinchin formula in M/G/1 queues, even when the variance is infinite, provided that it is a computable value (and not a value diverging towards $+\infty$). We expect that this will also allow us to perform asymptotic analyses numerically in Matlab (instead of using paper and pencil or symbolic software like Mathematica).
Work partially funded by the Italian Ministry of Education and Research (MUR), ForeLab project (Departments of Excellence), and by PNRR - M4C2 - Investimento 1.3, Partenariato Esteso PE00000013 - ”FAIR - Future Artificial Intelligence Research” - Spoke 1 ”Human-centered AI” (the PNRR program is funded by the European Commission under the NextGeneration EU programme).

[1] Cococcioni, M., Fiorini, F. and Pagano, M. (2023) “Modelling Heavy Tailed Phenomena Using a LogNormal Distribution Having a Numerically Verifiable Infinite Variance”, Mathematics, 11(7):1758, https://doi.org/10.3390/math11071758

Speaker: Francesco Fiorini (Università di Pisa)

Presentazione10Luglio_Fiorini.pdf

12:30 → 12:35 Conference photo

14:30 → 15:15 The complexity of proving Ramsey principles

We say that a graph with $n$ vertices is $c$-Ramsey if there is no set of $c \log n$ vertices which form in $G$ either a clique or an independent set. In other words a $c$-Ramsey graph over $n$ nodes is a witness of the fact that $r(c\log n) > n$, where $r(k)$ is the least $N$ such that every graph of size at least $N$ contains a clique or independent set of size $k$.
In searching for hard formulas to prove, proof complexity has often focused on Ramsey principles, by studying upper bounds for $r(k)$, that is on the complexity of certifying that a graph $G$ of size $n$ is $c$-Ramsey.

After reviewing what is known about the complexity of proving Ramsey principles we discuss the case the of $k$-clique Principle, an instantiation of Ramsey principles stating the a graph on $n$ vertices does not contain a $k$-clique. We will present a recent result of ours on the complexity of proving such principle in systems related to the Resolution and when the graph $G$ is a random graph and we discuss why its exact proof complexity in Resolution represents a major open problem.

Speaker: Nicola Galesi (Sapienza Università di Pisa)

Galesi.pdf

15:20 → 16:05 Problem session

Tuesday, 11 July

09:30 → 10:15 Numbers and numerosities

In this talk we analyze the notion of number and we define the structure of counting system. In this context, we present the notion of numerosity as a natural extension of the cardinality. This presentation is possible thanks to a theorem which has been recently proved.

Speaker: Vieri Benci (Università di Pisa)

Benci.pdf

10:20 → 11:05 Applications of nonstandard methods to partition regularity

In this talk, I will give an overview of applications of nonstandard methods to partition regularity for solutions to Diophantine equations and other combinatorial configurations.

Speaker: Martino Lupini (Università di Bologna)

11:10 → 11:40 Coffee break

11:40 → 12:25 Euclidean integers, Eucledean ultrafilters, and Euclidean numerosities

We introduce axiomatically, for any cardinal $\kappa$, the ordered domain $\mathbf{Z}_\kappa$ of the Euclidean integers, characterized as the collection of the transfinite sums of all $\kappa$-sequences of integers. Most relevant is the algebraic characterization of the ordering: a Euclidean integer is positive if and only if it is the transfinite sum of natural numbers. The ring $\mathbf{Z}_\kappa$ is obtained by taking the ultrapower of the ring of all finite partial sums modulo special ultrafilters (also named Euclidean ), here introduced to this end. (So $\mathbf{Z}_\kappa$ is actually a ring of hyperintegers.)

The existence of Euclidean ultrafilters follows from a new form of the Erdős-Dushmill-Miller partition property $\kappa\to(\omega,\kappa)$, namely $\ [A^{<\omega}]^2_\subset \to(\omega,\text{cofinal})^2_\subset,\ $ meaning that "for every 2-partition $G:[A^{<\omega}]^2_\subset\to\{0,1\}$ of all $\subset$-comparable pairs of finite subsets of $A$, there exists a $0$-homogeneous countable $\subset$-increasing sequence $C\subset A^{<\omega}$,or there exists a $\subset$-cofinal set $H\subset A^{<\omega}$ such that $[H]^2_\subset=\{(b,c)\in H^2\mid b\subset c\}$ is $1$-homogeneous for $G$.''

We call $\mathbf{Z}_\kappa$ the ring of the Euclidean integers because it arises in a theory of size of sets ("numerosity''), whose main aim is to save all the Euclidean common notions, including the fifth "the whole is greater than the part'', but still maintaining the Cantorian definitions of ordering, addition and multiplication of sets. Having at disposal transfinite sums of integers, the numerosity of a set may be the transfinite sums of its characteristic function, which is an Euclidean integer after an appropriate labelling of sets by ordinals. Then, in contrast to the awkward Cantorian cardinal arithmetic, numerosities are a positive semiring of hypernatural numbers, the non-negative part of the ring $\mathbf{Z}_\kappa$.

In particular, the algebraic order of $\mathbf{Z}_\kappa$ yields the "difference property'' asserting that the difference of the numerosities of any two sets is itself the numerosity of some set. This property has been the ``most wanted'' property of the Euclidean theory of size since its origin at the beginning of the century. Moreover one obtains the supplementary benefits that every set is equinumerous to a set of ordinals, and conversely that every nonnegative Euclidean integer is the numerosity of a set $X$ of ordinals, namely the transfinite sum of the characteristic function $\chi_X$.

Speaker: Marco Forti (Università di Pisa)

Forti.pdf

14:30 → 15:15 Many Levels of Infinities and Multidimensional van der Waerden's Theorem

There could be more than one elementary embedding between a model and its elementary extension. We develop a nonstandard analysis framework by iterating ultrapower constructions and present two different elementary embeddings at each stage. We hope that this framework gives powerful tools in applications. As a testing case we give a nonstandard proof of multidimensional van der Waerden's theorem by a single induction within this framework.

Speaker: Renling Jin (College of Charleston)

Jin.pdf

15:20 → 16:05 More thoughts on the use of nonstandard methods to extend Roth's Theorem

In this talk I will continue to explore some possibilities and some challenges in attempting to use nonstandard methods to extend Roth's theorem to sparser sets. Jin's recent proof of Roth's and Szemerédi's theorem provided new clarity on the combinatorial methods used by Szemerédi, and it is still unclear whether these techniques can be used to obtain stronger results. Meanwhile, some amazing new developments have taken place in regard to generalizations of Roth's Theorem. Recently Bloom and Sisask showed that any subset of the natural numbers with no 3-term arithmetic progression must have asymptotic density less than $\frac{1}{\log(n)^{1+c}}$ for some constant $c>0$. Then, in the last few months, this bound was significantly improved by Kelley and Meka, who showed that much sparser sets than this must contain 3-term arithmetic progressions, and their result is in close to "best possible." While I will discuss these results, I will not attempt to provide any insight into these groundbreaking proofs.

Speaker: Steven Leth (University of Northern Colorado)

Leth.pdf

16:10 → 16:40 Coffee break

16:40 → 17:25 Nonstandard methods without the axiom of choice

Model-theoretic frameworks for nonstandard methods entail the existence of nonprincipal ultrafilters over $\mathbb{N}$, a strong version of the Axiom of Choice ($\mathbf{AC}$). While $\mathbf{AC}$ is instrumental in many abstract areas of mathematics, such as general topology or functional analysis, its use in infinitesimal calculus or number theory should not be necessary.
In [1], Mikhail Katz and I have formulated a set theory $\mathbf{SPOT}$ in the $\mathbf{st}$-$\in$-language. The theory has three simple axioms, Transfer, Nontriviality and Standard Part. It is a subtheory of the nonstandard set theories $\mathbf{IST}$ and $\mathbf{HST}$, but unlike them, it is a conservative extension of $\mathbf{ZF}$. Arguments carried out in $\mathbf{SPOT}$ thus do not depend on any form of $\mathbf{AC}$. Infinitesimal calculus can be developed in $\mathbf{SPOT}$ as far as the global version of Peano's Theorem (the usual proofs of which use $\mathbf{ADC}$, the Axiom of Dependent Choice). The existence of upper Banach densities can be proved in $\mathbf{SPOT}$. The conservativity of $\mathbf{SPOT}$ over $\mathbf{ZF}$ is established by a construction that combines and extends the methods of forcing developed by A. Enayat and M. Spector.
A stronger theory $\mathbf{SCOT}$ is a conservative extension of $\mathbf{ZF} + \mathbf{ADC}$. It is suitable for handling such features as an infinitesimal approach to the Lebesgue measure.
I will also explore the possibilities for extending these theories to multiple levels of standardness and the relevance of such extensions to infinitesimal calculus and R. Jin's proof of Szemerédi's Theorem.

[1] K. Hrbacek and M. G. Katz, Infinitesimal analysis without the Axiom of Choice, Ann. Pure Appl. Logic 172, 6 (2021).
https://doi.org/10.1016/j.apal.2021.102959
https://arxiv.org/abs/2009.04980

Speaker: Karel Hrbáček (City College of New York)

Hrbacek.pdf