L6

The tunnel number of a graph embedded in a 3-dimensional manifold is the fewest number of arcs needed so that the union of the graph with the arcs has handlebody exterior. The behavior of tunnel number with respect to connected sum of knots can vary dramatically, depending on the knots involved. However, a classical theorem of Scharlemann and Schultens says that the tunnel number of a composite knot is at least the number of factors. For theta graphs, trivalent vertex sum is the operation which most closely resembles the connected sum of knots. The analogous theorem of Scharlemann and Schultens no longer holds, however. I will provide a sharp lower bound for the tunnel number of composite theta graphs, using recent work on a new knot invariant which is additive under connected sum and trivalent vertex sum. This is joint work with Maggy Tomova.

Decision problems – those in which the goal is to return an answer of “YES" or “NO" – are at the heart of the theory of computational complexity, and remain the most studied problems in the theoretical algorithms community. However, in many real-world applications it is not enough just to decide whether the problem under consideration admits a solution: we often want to find all solutions, or at least count (either exactly or approximately) their  total number. It is clear that finding or counting all solutions is at least as computationally difficult as deciding whether there exists a single solution, and  indeed in many cases it is strictly harder (assuming P is not equal NP) even to count approximately the number of solutions than it is to decide whether there exists at least one.

In this talk I will discuss a restricted family of problems, in which we are interested in solutions of a given size: for example, solutions could be copies of a specific k-vertex graph H in a large host graph G, or more generally k-vertex subgraphs of G that have some specified property (e.g. k-vertex subgraphs that are connected). In this setting, although exact counting is strictly harder than decision (assuming standard assumptions in parameterised complexity), the methods typically used to separate approximate counting from decision break down. Indeed, I will demonstrate a method that, subject to certain additional assumptions, allows us to transform an efficient decision algorithm for a problem of this form into an approximate counting algorithm with essentially the same running time.

This is joint work with John Lapinskas (Bristol) and Holger Dell (ITU Copenhagen).

I will give a brief survey of some problems in curvature free geometry and sketch

a new proof of the following:

Theorem (Guth). There is some $\delta (n)>0$ such that if $(M^n,g)$ is a closed aspherical Riemannian manifold and $V(R)$ is the volume of the largest ball of radius $R$ in the universal cover of $M$, then $V(R)\geq \delta(n)R^n$ for all $R$.

I will also discuss some recent related questions and results.

The relationship between the large-scale geometry of a group and its algebraic structure can be studied via three notions: a group's quasi-isometry class, a group's abstract commensurability class, and geometric actions on proper geodesic metric spaces. A common model geometry for groups G and G' is a proper geodesic metric space on which G and G' act geometrically. A group G is action rigid if every group G' that has a common model geometry with G is abstractly commensurable to G. For example, a closed hyperbolic n-manifold group is not action rigid for all n at least three. In contrast, we show that free products of closed hyperbolic manifold groups are action rigid. Consequently, we obtain the first examples of Gromov hyperbolic groups that are quasi-isometric but do not virtually have a common model geometry. This is joint work with Daniel Woodhouse.

Charles Babbage (1791–1871) was Lucasian Professor of mathematics in Cambridge from 1828–1839. He displayed a fertile curiosity that led him to study many contemporary processes and problems in a way which emphasised an analytic, data driven view of life.

In popular culture Babbage has been celebrated as an anachronistic Victorian engineer. In reality, Babbage is best understood as a figure rooted in the enlightenment, who had substantially completed his core investigations into 'mechanisation of thought' by the mid 1830s: he is thus an anachronistic Georgian: the construction of his first difference engine design is contemporary with the earliest public railways in Britain.

A fundamental question that must strike anybody who examines Babbage's precocious designs is: how could one individual working alone have synthesised a workable computer design, designing an object whose complexity of behaviour so far exceeded that of contemporary machines that it would not be matched for over a hundred years?

We shall explore the extent to which the answer lies in the techniques Babbage developed to reason about complex systems. His Notation which shows the geometry, timing, causal chains and the abstract components of his machines, has a direct parallel in the Hardware Description Languages developed since 1975 to aid the design of large scale electronics. In this presentation, we shall provide a basic tutorial on Babbage's notation showing how his concepts of 'pieces' and 'working points' effectively build a graph in which both parts and their interactions are represented by nodes, with edges between part-nodes and interaction-nodes denoting ownership, and edges between interaction-nodes denoting the transmission of forces between individual assemblies within a machine. We shall give examples from Babbage's Difference Engine 2 for which a complete set of notations was drawn in 1849, and compare them to a design of similar complexity specified in 1987 using the Inmos HDL.

In the speaker's previous joint work with Hans-Joachim Hein, a mass formula for asymptotically locally Euclidean (ALE) Kaehler manifolds was proved, assuming only relatively weak fall-off conditions on the metric. However, the case of real dimension four presented technical difficulties that led us to require fall-off conditions in this special dimension that are stronger than the Chrusciel fall-off conditions that sufficed in higher dimensions. This talk will explain how a new proof of the 4-dimensional case, using ideas from symplectic geometry, shows that Chrusciel fall-off suffices to imply all our main results in any dimension. In particular, I will explain why our Penrose-type inequality for the mass of an asymptotically Euclidean Kaehler manifold always still holds, given only this very weak metric fall-off hypothesis.