L3

After a short introduction to the section conjecture, I plan to present a "minimalistic" form of the birational p-adic section conjecture. The result is related to both: Koenigsmann's proof of the birational p-adic section conjecture, and a "minimalistic" Galois characterisation of formally p-adic valuations.

I will speak about the CBP (canonical base property) for types of finite SU-rank. This property first appears in a paper by Pillay and Ziegler, who show that it holds for types of finite rank in differentially closed fields of characteristic 0, as well as in existentially closed difference fields. It is unknown whether this property holds for all finite rank types in supersimple theories. I will first recall the definition of a canonical base, and give some natural examples. I will then  talk about a reduction of the problem (which allows one to extend the Pillay-Ziegler result to existentially closed fields of any characteristic), and finally derive some consequences of the CBP, in particular the UCBP, thus answering a question of Moosa and Pillay.  If time permits, I will show an application of these results to difference

fields.

VC dimension and density are properties of a collection of sets which come from probability theory.  It was observed by Laskowski that there is a close tie between these notions and the model-theoretic property called NIP. This tie results in many examples of collections of sets that have finite VC dimension. In general, it is difficult to find upper bounds for the VC dimension, and known bounds are mostly very large. However, the VC density seems to be more accessible. In this talk, I will explain all of the above acronyms, and present a theorem which gives an upper bound (in some cases optimal) on the VC density of formulae in some examples of NIP theories. This represents joint work of myself with M. Aschenbrenner, A. Dolich, D. Macpherson and S.

Starchenko.

Let $G=(V,E)$ be a graph with weights $\{w_e : e \in E\}$, and assume all weights are distinct. If $G$ is finite, then the well-known Prim's algorithm constructs its minimum spanning tree in the following manner. Starting from a single vertex $v$, add the smallest weight edge connecting $v$ to any other vertex. More generally, at each step add the smallest weight edge joining some vertex that has already been "explored" (connected by an edge) to some unexplored vertex.

If $G$ is infinite, however, Prim's algorithm does not necessarily construct a spanning tree (consider, for example, the case when the underlying graph is the two-dimensional lattice ${\mathbb Z}^2$, all weights on horizontal edges are strictly less than $1/2$ and all weights on vertical edges are strictly greater than $1/2$).

The behavior of Prim's algorithm for *random* edge weights is an interesting and challenging object of study, even
when the underlying graph is extremely simple. This line of research was initiated by McDiarmid, Johnson and Stone (1996), in the case when the underlying graph is the complete graph $K_n$. Recently Angel et. al. (2006) have studied Prim's algorithm on regular trees with uniform random edge weights. We study Prim's algorithm on $K_n$ and on its infinitary analogue Aldous' Poisson-weighted infinite tree. Along the way, we uncover two new descriptions of the Poisson IIC, the critical Poisson Galton-Watson tree conditioned to survive forever.

Joint work with Simon Griffiths and Ross Kang.