# SCIENTIFIC PROGRAMS AND ACTIVITIES

April 27, 2017

## November 9-10, 2007 The Fields Institute

Conference Organizers:
Arthur Apter, awapter<at>alum.mit.edu
Claude Laflamme, laf<at>math.ucalgary.ca
Juris Steprans, steprans<at>fields.utoronto.ca
Stevo Todorcevic, stevo<at>logique.jussieu.fr
Yi Zhang, yizhang<at>umich.edu

Organized by

Supported by the
National Science Foundation

 Schedule Participant List Hotels Visitor Information Audio and Slides of Talks

This two day conference is in honour of the 60th anniversary of Professor Andreas R. Blass, from the Department of Mathematics at the University of Michigan.

Since his doctoral thesis at Harvard University in 1970, Dr. Blass’ prolific research contributions have focused on mathematical logic, especially set theory, and extend into other areas including finite combinatorics, category theory, and theoretical computer science. The various presentations will provide a brief overview of some of the main ideas arising from these accomplishments, and the impact they have had throughout the mathematical community.

The conference is foremost a tribute to Dr. Blass’ legendary patience, guidance and inspiration not only to his many students, but also to innumerable collaborators from all over the world.

### Schedule

 Friday - November 9 Saturday - November 10 9:00 Neil Hindman Joerg Brendle 10:00 Alan Dow Heike Mildenberger 11:00 Tomek Bartoszynski Rudiger Goebel 13:15 TBA Bart Kastermans 14:10 Todd Eisworth Gary Weiss 15:00 Tea Tea 15:45 Andre Scedrov Yuri Gurevich 16:45 Bruce Sagan Arnold Miller

Tomek Bartoszynski, Boise State University
Around the Borel Conjecture

In 1919 Borel attempted to characterize all measure zero sets with respect to their open covers. In particular he came across a notion that he called a strong measure zero - a set of reals X is of strong measure zero if for every sequence epsilon_n there are open sets U_n of diameter epsilon_n whose union covers X. Borel conjectured that the only strong measure zero sets are countable sets, and as Laver showed in 1976 this was not without merit. Today the Borel Conjecture is a prototype of a characterization of countable/uncountable using topological or metric terms. In this talk I will survey the Borel Conjecture and related statements and their current status.

Alan Dow, University of North Carolina
Maps and special points of remainders

We discuss recent applications of forcing and the Proper Forcing Axiom to the study mappings and images of the Stone-Cech remainder of the real line and of the integers.

Todd Eisworth, Ohio University
Club-guessing and Coloring Theorems

We will some new (and old) results outlining the connections between club-guessing and coloring theorems proved using minimal walks. We will concentrate on successors of singular cardinals, but small'' large cardinals might very well make an appearance as well.

Rüdiger Göebel, Universität Duisburg-Essen
Decompositions of reflexive groups and Martin's axiom

Andreas Blass exhibited in several papers very interesting properties of subgroups of the Baer-Specker group, the group of all integer valued functions.
Here is another feature of this group. Assuming Martin's axiom, we will show the following

Theorem: For a fixed integer $m \geq 2$, we construct a slender reflexive group $G$ such that for all positive integers $n$, $G \cong G \oplus \Z ^n$ if and only if $m$ divides $n$.

Without the restriction to reflexive groups, this result was obtained by Eklof and Shelah, answering a problem by Gabriel Sabbagh (see P. Eklof, S. Shelah, `On groups $A$ such that $A\oplus \Z^n \cong A$?, Abelian group theory (Oberwolfach, 1985)(1987) 149--163). The case - "m=2 (one implication)" also assuming Martin's axiom and reflexivity - was considered in R. G\"obel, S. Shelah (Reflexive subgroups of the Baer-Specker group and Martin's axiom, Proc. Perth Conference (2001) 145--158.)

Answering a problem in the book by P. Eklof, A. Mekler (Almost free modules, Set-theoretic methods, North-Holland, Amsterdam 1990.) we constructed at that time such reflexive groups $G$ with $G\oplus \Z \not\cong G$. Thus our new theorem unifies and strengthens both of these results. It remains a challenging open problem if Martin's axiom can be removed!

Yuri Gurevich, Microsoft Research
Zero-one laws in discrete mathematics

The fraction of n-vertex graphs that are connected, that is the probability that an n-vertex graph is connected when all n-vertex graphs have the same probability, grows to 1 as n grows to infinity. In that sense almost all finite graphs are connected. Similarly almost all graphs are Hamiltonian, not 3-colorable, rigid, etc. Is there a general phenomenon behind results of that sort? It turns out that much depends on the logical form of the property in question. In particular, every first-order sentence in purely relational vocabulary is almost surely true or almost surely false on finite structures. This zero-one law for first-order logic was generalized in various directions: richer logics, non-uniform probability distributions, special classes of structures, etc. We will explain some of the results including a geometric zero-one law of Bob Gilman, Alexei Miasnikov and the speaker.

Neil Hindman, Howard University
A New and Stronger Central Sets Theorem
(Joint with Dibyendu De and Dona Strauss)

Furstenberg's original {\em Central Sets Theorem\/} applied to {\em central\/} subsets of $\mathbb N$ and finitely many specified sequences in $\mathbb Z$. In this form it was already strong enough to derive some very strong combinatorial consequences, such as the fact that a central subset of $\mathbb N$ contains solutions to all partition regular systems of homogeneous equations. Subsequently the Central Sets Theorem was extended to apply to arbitrary semigroups and countably many specified sequences. In this paper we derive a new version of the Central Sets Theorem for arbitrary semigroups $S$ which applies to {\em all\/} sequences in $S$ at once. We show that the new version is strictly stronger than the original version applied to the semigroup $(\mathbb R,+)$. And we show that the noncommutative versions are strictly increasing in strength.

Generating sets for cofinitary groups.

We will explain a question on generating sets for cofinitary groups, and give an outline of an approximation to the answer:

Cofinitary groups are subgroups of the symmetric group on the natural numbers where all nonidentity elements have only finitely many fixed points. Towards answering the question of their possible complexities there are two results on the upper bounds. The question is whether these are actually different. We'll give an approximation to the answer that is of recursion theoretic nature.

Arnold W. Miller, University of Wisconsin-Madison
The axiom of choice and the Borel hierarchy

How is the axiom of choice used in the set theory of the real line? I will describe a result concerning the hierarchy of Borel sets in a model of set theory in which the axiom of choice fails very badly. Recall that a set of reals is Borel if it is in the smallest family of sets containing the open sets and closed under countable unions and complements.

Bruce Sagan, Michigan State University
Monotonic Sequence Games
(Joint work with the Otago Theory Group)

A permutation $\pi=a_1a_2\ldots a_n$ in the symmetric group $S_n$ has an {\it increasing subsequence of length $m$\/} if there are indices $i_1<i_2<\ldots<i_m$ such that $a_{i_1}<a_{i_2}<\ldots<a_{i_m}$. Decreasing subsequences are defined similarly. A famous theorem of Erd\H{o}s and Szekeres states that any permutation in S_{mn+1}$has either an increasing subsequence of length$m+1$or a decreasing subsequence of length$n+1$. In a monotonic sequence game, two players form a sequence by alternately choosing distinct elements from the set$\{1,2,\ldots,mn+1\}$. The game ends when the resulting sequence contains either an increasing subsequence of length$m+1$or a decreasing one of length$n+1$. By the Erd\H{o}s-Szekeres Theorem, this must happen at some point. Harary, Sagan, and West were the first ones to investigate this game and determine who wins when either$m$or$n\$ is sufficiently small. We investigate the behaviour of this game when played by choosing elements from other partially ordered sets. In particular, using rational numbers yields interesting results via a variant of the Robinson-Schensted-Knuth correspondence.

Andre Scedrov, University of Pennsylvania
Formal Analysis of Kerberos 5 Authentication Protocol

The design and security analysis of protocols that use cryptographic primitives is one of the most fundamental and challenging areas of computer security research. Relatively succinct but subtle authentication, key exchange, negotiation, authorization, and related protocols are the building blocks for secure distributed systems. Protocol analysis is a successful scientific area with two important but historically independent foundations, one based on symbolic computation and one based on computational complexity theory. Here we highlight joint work with Cervesato, Jaggard, Tsay, and Walstad on the formal analysis of the Kerberos 5 authentication protocol suite. This work
discovered a serious vulnerability in the Kerberos public-key extension and caused a Microsoft security patch for Windows 2000 and Windows XP operating systems. The work contributed to the reformulation of the IETF standard for Kerberos public-key extension and provided security proofs of the corrected version of the protocol, the latter jointly with Backes. The flaw discovered is not a flaw in implementation or in cryptography, but a protocol-level, structural flaw, which is present even when the underlying cryptographic operations and network infrastructure operate normally. The methodology developed in this work is applicable to a wide range of network security protocols. We also discuss current joint work with Blanchet on mechanized proofs of authentication and key secrecy properties of Kerberos 5, both with and without its public-key extension.

Gary Weiss, University of Cincinnati
B(H)-Ideals: Recent Advances and Questions beyond Blass-Weiss
In 1978 we proved that assuming CH, every noncountably generated two-sided ideal in B(H) is the sum of two proper ideals. The particular case of the ideal of compact operators settled a 1971 problem of Pearcy-Topping. Some of Blass' subsequent work evolved from this. This lecture presents recent advances, motivated by this early work, on the lattice of B(H) ideals and some distinguished sublattices. I will explore density questions (whether or not between two ideals in a lattice lies another), characterize gaps in the general lattice, and will present some open questions. This work is joint with Victor Kaftal.

### Participant List as of November 10, 2007

 Fullname University Name Ackerman, Nate University of Pennsylvania Adams, Talmalie University of Toronto Bartoszynski, Tomek National Science Foundation Bjorndahl, Adam University of Toronto Blass, Andreas University of Michigan Bourke, John Dartmouth College Brendle, Joerg Kobe University Brodsky, Ari University of Toronto Broverman, Sam University of Toronto Dow, Alan University of North Carolina Eisworth, Todd Ohio University Farah, Ilijas York University Fischer, Arthur University of Toronto Fischer, Vera York University Frankiewicz, Ryszard IM PAN Goebel, Ruediger Universitaet Duisburg Essen Groft, Chad University of Toronto Grzech, Magdalena Cracow University of Technology Gurevich, Yuri Microsoft Research Hindman, Neil Howard University Hoehn, Logan University of Toronto Kastermans, Bart University of Wisconsin-Madison Klein, Moses Koenig, Bernhard University of Toronto Krautzberger, Peter Free University Berlin, Germany Mildenberger, Heike Universitaet Wien Miller, Arnold W. University of Wisconsin-Madison Sagan, Bruce Michigan State University Scedrov, Andre University of Pennsylvania Steprans, Juris York University Szeptycki, Paul York University Tall, Franklin University of Toronto Tornquist, Asger University of Toronto Weiss, Gary University of Cincinnati Weiss, William University of Toronto Zamora-Aviles, Beatriz York University