Computable combinatorics has a long history, but has seen a recent surge of interest highlighting the fact that computability-theoretically natural notions tend to be combinatorially natural, and vice-versa. The summer school and conference will explore recent developments in combinatorics, computability theory, and adjacent areas of logic.
The summer school will consist of three tutorials, of four lectures each, focusing in the intersection of combinatorics with each of computability theory, model theory, and set theory.
The complexity of inside/outside Ramsey theorems Paul Shafer
We analyze the computational and axiomatic strength of the following two theorems of Rival and Sands (1980), both of which are inspired by Ramsey's theorem for pairs.
Rival–Sands theorem for graphs. Every infinite graph $G$ contains an infinite subset $H$ such that every vertex of $G$ is adjacent to precisely zero, one, or infinitely many vertices of $H$.
Rival–Sands theorem for partial orders. Every infinite partial order $P$ of finite width contains an infinite chain $C$ such that every element of $P$ is comparable with precisely zero or infinitely many elements of $C$.
We think of the Rival–Sands theorem for graphs as an inside/outside version of Ramsey's theorem for pairs. Ramsey's theorem for pairs produces and infinite subgraph $H$ that is either a clique or an independent set in a given countable graph. However, Ramsey's theorem gives no information about the relation between the vertices inside $H$ and the vertices outside $H$. The Rival–Sands theorem for graphs balances this situation by producing an infinite set of vertices $H$ that is not necessarily a clique or an independent set, but for which there is information about the relationship between the vertices inside $H$ and the vertices outside $H$. In the Rival–Sands theorem for graphs, the zero, one, and infinitely many alternatives in the conclusion are all necessary. The Rival–Sands theorem for partial orders is a similar result where the one alternative can be removed.
The Rival–Sands theorems are interesting cases in effective combinatorics and reverse mathematics because their strength is unusual in certain respects. We aim to discuss the following results of Fiori Carones, Shafer, and Soldà (2022) and Forio Carones, Marcone, Shafer, and Soldà (2022) and we will introduce the necessary background along the way.
In reverse mathematics, the Rival–Sands theorem for graphs is equivalent to ${\sf ACA}_0$. Thus the Rival–Sands theorem for graphs is stronger than Ramsey's theorem for pairs.
In the Turing degrees, in general a degree that is ${\sf PA}$ relative to $G''$ is required to compute an $H$ as in the conclusion of the Rival–Sands theorem for the graph $G$. Moreover, the correspondence is uniform: in the Weihrauch degrees, the Rival–Sands theorem for graphs is equivalent to the double-jump of weak König's lemma. The Rival–Sands theorem for graphs is the first example of a theorem from the literature exhibiting exactly this computational strength.
Back in reverse mathematics, the Rival–Sands theorem for partial orders is equivalent to the ascending/descending sequence principle (which is a weak consequence of Ramsey's theorem for pairs) plus the $\Sigma^0_2$ induction scheme. The Rival–Sands theorem for partial orders is the first example of a theorem from the literature exhibiting exactly this axiomatic strength.
In fact, the Rival–Sands theorem for partial orders generalizes to infinite partial orders that do not have infinite antichains. This generalization is equivalent to ${\sf ACA}_0$.
Model-theoretic constructions of random combinatorial structures Rehana Patel
Probabilistic constructions of countable objects play an important role in combinatorics and logic. Perhaps the most well known such construction is the Erdös-Rényi process, in which edges on pairs of distinct natural numbers are determined by independent tosses of a fair coin, producing the Rado graph up to isomorphism with probability 1. The Erdös-Rényi process has the symmetry property of "exchangeability", that is, it does not depend on the order in which pairs of distinct natural numbers are considered. This tutorial will aim to give students a taste of probabilistic constructions that arise in model theory, with a focus on ones that are exchangeable. Topics will include first order zero-one laws, invariant measures via sampling from Borel structures, and sparse random graphs; these may be modified given time constraints and student interest.
Constructive solutions to combinatorial problems Anton Bernshteyn
Most research in combinatorics focuses on finite structures. Part of the reason is that infinite combinatorial problems can often be reduced to the finite case via a compactness argument. However, due to their reliance on the Axiom of Choice, such reductions are inherently non-constructive. In this tutorial we will investigate classical combinatorial problems—such as graph coloring or perfect matching—that can be solved on infinite graphs of certain types in a satisfactorily "constructive" manner. Along the way, we will encounter tools from such diverse areas as descriptive set theory, probability theory, general topology, and—surprisingly—computer science.
Physical space at the conference is limited. If you would like to attend the meeting in person, please register by emailing comp2023@computability.org with the subject "Conference Registration".
Marta Fiori-Carones The strength of the existence of positive, Friedberg and minimal numberings Video | Slides
10am–10:30am
Break
10:30am–11:30pm
Natasha Dobrinen Ramsey theory on infinite structures Video | Slides
11:30am–12:30pm
Dilip Raghavan Borel order dimension Video | Slides
Titles and abstracts
▶ Nate Ackerman (Harvard University)
Ramsey theory on infinite structures
Computability of Algebraic and Definable Closure
The notions of algebraic closure and definable closure provide an abstract notion of "neighborhood" of a point. In this talk we will review the model theoretic notion of both algebraic and definable closures before introducing a formula-by-formula wise version. With this formula wise version in hand we will study computability theoretic bounds on identifying these two closures.
This is joint work with Cameron Freer and Rehana Patel.
▶ Chris Conidis (CUNY–College of Staten Island)
The computability of the Tree Antichain Theorem
We will introduce and analyze the computability-theoretic content of a combinatorial principle that asserts the existence of infinite antichains in computably enumerable trees with infinitely many branchings. We will also describe how this principle arises naturally in the context of Commutative Algebra.
▶ Natasha Dobrinen (University of Notre Dame)
Ramsey theory on infinite structures
The simplest form of the Infinite Ramsey Theorem states that, given any coloring of all pairs of natural numbers into two colors, there is an infinite subset of natural numbers in which all pairs have the same color. When moving from sets to structures, some surprising phenomena occur: For example, there is a coloring of pairs of rational numbers into two colors such that both colors persist in any subset of the rationals forming a dense linear order (Sierpinski 1933). Likewise for colorings of edges in the Rado graph (Erdos-Hajnal-Posa 1975). The study of optimal bounds for colorings of copies of a finite substructure inside an infinite structure is the subject of "big Ramsey degrees". This talk will give an introduction to the components intrinsic to characterizations of big Ramsey degrees and survey the current state of the art for countable homogeneous structures. We will discuss proof methods ranging from Milliken's theorem to forcing pigeonhole principles on coding trees (in $\mathsf{ZFC}$) to Ramsey theorems for parameter words, methods which are central to all current work. We will conclude with some recent work on infinite-dimensional Ramsey theory on homogeneous structures of Dobrinen (2022) and of Dobrinen–Zucker (2023).
▶ Benedict Eastaugh (University of Warwick)
Arrow's theorem and the reverse mathematics of social choice theory
Arrow's impossibility theorem is a foundational result in social choice theory. It establishes strong limits on the possibility of aggregating individual preferences via a social welfare function: if the set of voters in a society is finite, then any way of aggregating individual preferences that respects Arrow's axioms of unanimity and independence will be dictated by a single voter.
Arrow's theorem can be proved constructively, but later developments in social choice theory in the 1970s brought in highly non-constructive methods. Fishburn showed, relative to the existence of non-principal ultrafilters, that there are infinitary counterexamples to Arrow's theorem. Kirman and Sondermann then proved that every social welfare function can be characterised in terms of an associated ultrafilter of decisive coalitions which is non-principal if and only if the social welfare function is non-dictatorial.
In this talk I will sketch how to formalise some basic notions from social choice theory within second-order arithmetic, and do some reverse mathematics of social choice theory. One of the main results is that much of the Kirman–Sondermann analysis of social welfare functions can, when restricted to countable societies, be carried out in $\mathsf{RCA}_0$, and this approach yields a proof of Arrow's theorem in $\mathsf{RCA}_0$. I prove a countable version of the Kirman–Sondermann theorem in $\mathsf{ACA}_0$, and show that Fishburn's possibility theorem for countable societies is equivalent to $\mathsf{ACA}_0$ over $\mathsf{RCA}_0$.
▶ Marta Fiori Carones (Sobolev Institute of Mathematics)
The strength of the existence of positive, Friedberg and minimal numberings
(Joint work with Nikolay Bazhenov and Manat Mustafa) The talk is devoted to the analysis of some basic statements about numberings from the point of view of reverse mathematics and Wiehrauch reducibility. A numbering is a surjective map from the naturals to a family of sets. A numbering is called Friedberg if the map is injective. A numbering is called positive if the set of pairs of numbers which enumerate the same set is c.e. Different numberings of a certain family can be compared thanks to a certain relation, which orders the numberings into a upper semilattice called the Rogers semilattice. It is so possible to speak about minimal numberings with respect to this relation. After introducing appropriate definitions of a numbering in the language of second order arithmetic, we analyse the strength, both under the reverse mathematics perspective and the Weihrauch one, of statements like "for each numbering there exists a Friedberg/positive/minimal numbering of the same family".
▶ Marcia Groszek (Dartmouth College)
Ordinal suprema and second-order arithmetic
Jeffry Hirst showed that, over the base theory $\mathsf{RCA}_0$, the statement that every well-ordered sequence of ordinals has a supremum is equivalent to $\mathsf{ATR}_0$. In joint work with Ben Logsdon and Justin Miller, we show that the same equivalence holds over the weaker base theory $\mathsf{RCA}_0^*$. We also find equivalences with $\mathsf{ACA}_0$ and $\mathsf{B}\Sigma^0_2$, and explore ordinal suprema in the absence of induction for $\Sigma^0_1$ formulas.
▶ Alberto Marcone (University of Udine)
Provable better partial orders in reverse mathematics
A partial order is a well-partial order (wpo) if it does not contain infinite descending chains and infinite antichains. In the 1960s Nash–Williams introduced a strengthening of this notion, called better partial order (bpo), which has better closure properties than wpo and was therefore used to show that many partial orders are wpo. In this talk we deal with the foundations of bpo theory from the viewpoint of reverse mathematics. From this perspective, even the statement that finite partial orders are bpo is nontrivial. About twent years ago I showed that "2 is bpo" (where 2 is the antichain with two elements) is provable in $\mathsf{RCA}_0$, the base theory of reverse mathematics, and asked about the strength of "3 is bpo". No progress was made on the question until last year, when Anton Freund showed that "3 is bpo" implies $\mathsf{ACA}_0^+$, providing a nontrivial lower bound for the strength of the statement. The question is not settled yet (the upper bound is $\mathsf{ATR}_0$), but Freund's result leads to ask: which partial orders are proved to be bpos by a theory such as $\mathsf{ACA}_0$ which does not prove that 3 is bpo? In recent work with Freund, Pakhomov and Soldà, we answered this question.
▶ Dilip Raghavan (National University of Singapore)
Borel order dimension
We introduce a notion of Borel order dimension for Borel partial orders. Several interesting differences between the classical notion and Borel notion will be pointed out. For instance, the Borel order dimension of the Turing degrees is usually different from its classical order dimension. A dichotomy, which is similar in spirit to the ${G}_{0}$-dichotomy, will be established for a Borel partial order to have countable Borel order dimension. We will examine the case of locally countable Borel orders in more detail and show that it is consistent that the Borel order dimension of all locally countable Borel partial orders is strictly smaller than the continuum. This is joint work with Ming Xiao.
▶ Richard Shore (Cornell University)
Reverse Mathematics: A Global View
We view the structure of reverse mathematics as a degree structure similar to that of the Turing degrees, $\mathcal{D}_{T}$ with the ordering of Turing reducibility, $\leq_{T}$.
We define an ordering $\leq_{P}$ on sets of sentences of second order arithmetic containing $\mathsf{RCA}_0$: $S\leq_{P}T\Leftrightarrow T\vdash\varphi$ for every $\varphi\in S$. As usual we consider the induced ordering $\leq_{P}$ on the equivalence classes $\mathbf{s}$ and $\mathbf{t}$ and the resulting structure $\mathcal{D}_{P}$. Important substructures are $\mathcal{F}_{P}$ and $\mathcal{R}_{P}$ consisting of the degrees of finitely and recursively axiomatizable sets of sentences. We prove a number of global results about $\mathcal{D}_{P}$ that differ remarkably from those for the analogous questions about $\mathcal{D}_{T}$ and other degree structures. The results include the following:
Theorem: $\mathcal{D}_{P}$ is a complete algebraic lattice (with $0$ and $1$) and not only pseudocomplemented but relatively so, i.e. it is a Heyting algebra. $\mathcal{R}_{P}$ is an incomplete algebraic lattice. For each of them the compact elements are those in $\mathcal{F}_{P}$ and the relative pseudocomplement of $T$ in $\mathcal{D}_{P}$ with respect to $S$, $\mathbf{t}\rightarrow\mathbf{s}$, is $\vee\{\varphi|\varphi\wedge T\leq S\}$. $\mathcal{F}_{P}$ is the atomless Boolean algebra.
Theorem: The (first order) theories of $\mathcal{F}_{P}$ and $\mathcal{D}_{P}$ with $\leq_{P}$ (and so with $\vee$, $\wedge$, $0$, and $1$) are decidable by applying major results of Tarski and Rabin.
Theorem: $\mathcal{D}_{P}$ and $\mathcal{F}_{P}$ have exactly $2^{\omega}$ many automorphisms.
Theorem: There are only eight countable sets which are definable in $\mathcal{D}_{P}$: $\emptyset,\{0),\{1\},\{0,1\},\mathcal{F}_{P}$, $\mathcal{F}_{P}-\{0\}$, $\mathcal{F}_{P}-\{1\}$ and $\mathcal{F}_{P}-\{0,1\}$. No other countable sets are fixed under all automorphisms of $\mathcal{D}_{P}$.
Theorem: We can characterize the cones $\mathcal{D}_{P}^{\mathbf{s}}=\{\mathbf{t}|\mathbf{s}\leq_{P}\mathbf{t\}}$ in $\mathcal{D}_{P}$. In particular, for every axiomatizable theory $S$ extending $\mathsf{RCA}_0$, $\mathcal{D}_{P}^{\mathbf{s}}\cong\mathcal{D}_{P}$.
Much to our surprise, after we had worked out most of these results we discovered that Tarski had proven many of them and some others almost ninety years ago and so long before the rise of reverse mathematics.
▶ Henry Towsner (University of Pennsylvania)
From Saturated Embeddings to Explicit Algorithms
The earliest quantifier elimination theorems were explicit algorithms: given an arbitrary formula in Presburger arithmetic, or the theory of algebraically closed fields, or dense linear orders, for instance, we know how to transform it into an equivalent quantifier-free formula.
Many modern quantifier elimination theorems, however, are proven through saturated embedding tests, which use the existence of certain kinds of embeddings between uncountable models to prove, indirectly, that each formula is equivalent to a quantifier-free formula. We discuss how the method of proof mining can be used to transform these proofs into explicit algorithms. Since proof mining typically deal with countable objects, we have to reinterpret the saturated embedding test itself in a more computational way before we can hope to extract an algorithm.
▶ Wei Li (National University of Singapore)
Mathematical induction in the tree ramsey theorem for pairs
Let $\mathsf{TT}^2_k$ denote the combinatorial principle stating that every k-coloring of pairs of compatible nodes in the full binary tree has a homogeneous solution, i.e. an isomorphic subtree in which all pairs of compatible nodes have the same color. In this talk, we will focus on the inductive strength of $\mathsf{TT}^2_k$. We will show a weaker version of $\mathsf{TT}^2_k$ does not imply $Sigma^0_2$ induction.
The studies of Weihrauch degrees and reverse mathematics share many
ideas, and many similar results and close relations are known. The
studies of Weihrauch degrees of the arithmetical transfinite recursion
($\mathsf{ATR}$) and their relation to reverse mathematics are developed, e.g.,
in [1,2,3]. Typically, principles which are provable from $\mathsf{ATR}_0$ (in
the setting of reverse mathematics) by way of the pseudo-hierarchy
method have various strengths. In this talk, we overview these
situations and study the structure between ATR and the choice
principle on the Baire space. This is joint work with Yudai Suzuki.
T. Kihara, A. Marcone and A. Pauly. Searching for an analogue of
$\mathsf{ATR}_0$ in the Weihrauch lattice. J. Symb. Log., 85(3):1006–1043, 2020.
Jun Le Goh. Some computability-theoretic reductions between
principles around $\mathsf{ATR}_0$. arXiv preprint arXiv:1905.06868, 2019.
Paul-Elliot Angl\`{e}s d'Auriac. Infinite Computations in Algorithmic
Randomness and Reverse Mathematics. PhD thesis, Université Paris-Est,
2019.
Y. Suzuki and K. Yokoyama. Searching problems above arithmetical
transfinite recursion. in preparation.
The summer school will take place in Room HTB 208. The conference will take place in Room HTB 145
Travel
Hartford is served by Bradley International Airport (BDL), which is about 20 minutes from the Hartford campus. The Bradley Flyer bus connects directly to the Connecticut Convention Center, next to campus.
Train service between Hartford and New York is provided by CT Rail (Hartford Line/Metro North). Bus service between Hartford and Boston, and between Hartford and New York, is provided by Megabus and Peter Pan Bus.
Please note: if the conference is reimbursing any portion of your travel, your flights must comply with the Fly America Act.
This is bold and this is strong. This is italic and this is emphasized.
This is superscript text and this is subscript text.
This is underlined and this is code: for (;;) { ... }. Finally, this is a link.
Heading Level 2
Heading Level 3
Heading Level 4)
Heading Level 5
Heading Level 6
Blockquote)
Fringilla nisl. Donec accumsan interdum nisi, quis tincidunt felis sagittis eget tempus euismod. Vestibulum ante ipsum primis in faucibus vestibulum. Blandit adipiscing eu felis iaculis volutpat ac adipiscing accumsan faucibus. Vestibulum ante ipsum primis in faucibus lorem ipsum dolor sit amet nullam adipiscing eu felis.
Preformatted)
i = 0;
while (!deck.isInOrder()) {
print 'Iteration ' + i;
deck.shuffle();
i++;
}
print 'It took ' + i + ' iterations to sort the deck.';
