L3

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.

The talk will survey some results about smooth and topological 4-manifolds obtained via surgery, and discuss some contrasting information provided by gauge theory about smooth finite group actions on 4-manifolds.