L3

Consider the complete graph on n vertices with independent and identically distributed edge-weights having some absolutely continuous distribution. The minimum spanning tree (MST) is simply the spanning subtree of smallest weight. It is straightforward to construct the MST using one of several natural algorithms. Kruskal's algorithm builds the tree edge by edge starting from the globally lowest-weight edge and then adding other edges one by one in increasing order of weight, as long as they do not create any cycles. At each step of this process, the algorithm has generated a forest, which becomes connected on the final step. In this talk, I will explain how it is possible to exploit a connection between the forest generated by Kruskal's algorithm and the Erd\"os-R\'enyi random graph in order to prove that $M_n$, the MST of the complete graph, possesses a scaling limit as $n$ tends to infinity. In particular, if we think of $M_n$ as a metric space (using the graph distance), rescale edge-lengths by $n^{-1/3}$, and endow the vertices with the uniform measure, then $M_n$ converges in distribution in the sense of the Gromov-Hausdorff-Prokhorov distance to a certain random measured real tree.

This is joint work with Louigi Addario-Berry (McGill), Nicolas Broutin (INRIA Paris-Rocquencourt) and Grégory Miermont (ENS Lyon).

The ``k-commodity flow problem'' is: we are given k pairs of vertices of a graph, and we ask whether there are k flows in the graph, where the ith flow is between the ith pair of vertices, and has total value one, and for each edge, the sum of the absolute values of the flows along it is at most one. We may also require the flows to be 1/2-integral, or indeed 1/p-integral for some fixed p.

If the problem is feasible (that is, the desired flows exist) then it is still feasible after contracting any edge, so let us say a flow problem is ``critical'' if it is infeasible, but becomes feasible when we contract any edge. In many special cases, all critical instances have only two vertices, but if we ask for integral flows (that is, p = 1, essentially the edge-disjoint paths problem), then there arbitrarily large critical instances, even with k = 2. But it turns out that p = 1 is the only bad case; if p>1 then all critical instances have bounded size (depending on k, but independent of p), and the same is true if there is no integrality requirement at all.

The proof gives rise to a very simple algorithm for the k edge-disjoint paths problem in 4-edge-connected graphs.

Since graph-coloring is an NP-complete problem in general, it is natural to ask how the complexity changes if the input graph is known not to contain a certain induced subgraph H. Due to results of Kaminski and Lozin, and Hoyler, the problem remains NP-complete, unless H is the disjoint union of paths. Recently the question of coloring graphs with a fixed-length induced path forbidden has received considerable attention, and only a few cases of that problem remain open for k-coloring when k>=4. However, little is known for 3-coloring. Recently we have settled the first open case for 3-coloring; namely we showed that 3-coloring graphs with no induced 6-edge paths can be done in polynomial time. In this talk we will discuss some of the ideas of the algorithm.

This is joint work with Peter Maceli and Mingxian Zhong.

We consider two decision problems for linear recurrence sequences(LRS) over the integers, namely the Positivity Problem (are all terms of a given LRS positive?) and the Ultimate Positivity Problem (are all but finitely many terms of a given LRS positive?). We show decidability of both problems for LRS of order 5 or less, and for simple LRS (i.e. whose characteristic polynomial has no repeated roots) of order 9 or less. Moreover, we show by way of hardness that extending the decidability of either problem to LRS of order 6 would entail major breakthroughs in analytic number theory, more precisely in the field of Diophantine approximation of transcendental numbers.
This talk is based on a recent paper, available at
http://www.cs.ox.ac.uk/people/joel.ouaknine/publications/positivity13ab…
joint with James Worrell and Matt Daws.

The recently completed auction for 4G mobile spectrum was the most importantcombinatorial auction ever held in the UK.  In general, combinatorial auctions allow bidders to place individual bids on packages of items,instead of separate bids on individual items, and this feature has theoretical advantages for bidders and sellers alike.  The accompanying challenges of implementation have been the subject of intense work over the last few years, with the result that the advantages of combinatorial auctions can now be realised in practice on a large scale.  Nowhere has this work been more prominent than in auctions for radio spectrum.  The UK's 4G auction is the most recent of these and the publication by Ofcom (the UK's telecommunications regulator) of the auction's full bidding activity creates a valuable case study of combinatorial auctions in action.

I'll discuss questions about the structure of long sums of

Dirichlet characters --- that is, sums of length comparable to the modulus.

For example: How often do character sums get large? Where do character sums

get large? What do character sums "look like" when then get large? This will

include some combination of theorems and experimental data.

I will discuss conjectures relating cup products of cyclotomic units and modular symbols modulo an Eisenstein ideal. In particular, I wish to explain how these conjectures may be viewed as providing a refinement of the Iwasawa main conjecture. T. Fukaya and K. Kato have proven these conjectures under certain hypotheses, and I will mention a few key ingredients. I hope to briefly mention joint work with Fukaya and Kato on variants.

We will discuss arithmetic restriction phenomena and its relation to Waring's problem, focusing on how recent work of Wooley implies certain restriction bounds.

I will discuss some p-adic (and mod p) criteria ensuring that an elliptic curve over the rationals has algebraic and analytic rank one, as well as some applications.