Wednesday, 24 October 2018

How to sweep up your fusion reaction

Fusion energy may hold the key to a sustainable future of electricity production. However some technical stumbling blocks remain to be overcome. One central challenge of the fusion enterprise is how to effectively withstand the high heat load emanating from the core plasma. Even the sturdiest solid solutions suffer damage over time, which could be avoided by adding a thin liquid coating. This thin liquid-metal layer must be maintained in the presence of the strong magnetic field needed to confine the core plasma and under the influence of the hot particles that escape the confinement and strike the liquid. To reduce the effective heat load it has been proposed to sweep these incoming particles up and down the liquid layer. However it is unclear how this sweeping motion will affect the liquid.

In this work Oxford Mathematicians Davin Lunz and Peter Howell in collaboration with Tokamak Energy examine how the sweeping motion affects the deflections of the liquid layer. They find that there are effectively three regimes: one in which the sweeping motion's influence is neutral as it has little effect on the deflections, one in which the deflections are minimised (that is a positive outcome in the fusion context as the liquid provides a more uniform covering), and one in which the deflections are dangerously amplified (that is a negative outcome in this context, as large deflections can leave the underlying solid exposed and result in liquid particles detaching from the layer and impurities reaching the core plasma). To uncover this, they focus on the (appropriately normalised) governing equation, namely, \begin{align} \frac{\partial h}{\partial t} + \frac \partial{\partial x} \left[ Q(h) \left( 1 - \frac{\partial p}{\partial x} + \frac{\partial ^3 h}{\partial x^3} \right) \right] = 0, \end{align} where $x$ is a horizontal coordinate, $t$ denotes time, $h(x,t)$ is the liquid deflection, $p(x,t)$ is the oscillating pressure exerted on the layer from the impinging plasma, and $Q$ is a flux function. This is a thin film equation where the fluid is driven by gravity and the applied pressure while being modulated by surface tension. 

One key observation is that there are two independent time scales in the problem: the first is the time scale at which the surface equilibrates, and the second is the time scale at which the pressure completes one oscillation. Their work shows that if the pressure time scale is much longer than the deflection time scale (that is, if the sweeping is sufficiently slow) then the deflections are largely unaffected by the motion. In the opposite case - the moving pressure time scale is much shorter than the deflection time scale, that is, the sweeping motion is very fast - the load of the impacting particles is effectively averaged out and this more even distribution minimises deflections. When the two time scales are of similar order, the pressure can oscillate at a speed similar to the natural speed that deflections propagate along the free surface. This has the effect of dangerously amplifying the free-surface deflections and should be avoided in the context of confined fusion.

For more detali on the research please click here.

Monday, 22 October 2018

D-modules on rigid analytic spaces - where algebra and geometry meet number theory

Oxford Mathematician Andreas Bode talks about his work in representation theory and its lesson for the interconnectness of mathematics.

"In many cases, the borders between different areas of mathematical research are much less rigid, much more permeable than one might make out from a modular curriculum. A number theorist might borrow tools from analysis and adapt them for their purposes, a geometer might discover that structures from theoretical physics offer a more intuitive explaination for an interesting phenomenon. These connections, intersections and border-crossings are exciting not just because they are useful (having a more varied arsenal of tools can help you to prove more things), but primarily because these argumentative movements carry enormous potential for insight. A sudden shift of perspective, a reinterpretation of the original question in terms of another field can solve a problem by transforming it, crucially enriching how we view our objects of study.

Representation theory is the study of algebraic systems by way of their actions on other objects: if we consider a group $G$, we might ask how we can represent group elements by automorphisms of some finite-dimensional vector space (and thus by matrices), i.e. we study homomorphisms $G\to \text{GL}_n(\mathbb{C})$. In the same way, if $A$ is an algebra over some field $k$, an action of $A$ on some $k$-vector space $V$ is given by an algebra morphism $A\to \text{End}_k(V)$. The slogan is always the same: we understand groups, rings, algebras, ... by seeing what they do to other objects (usually vector spaces).

While a representation is by definition an algebraic notion, it turns out that many of the most common and interesting groups, rings, algebras, ... also have a very rich geometric structure - and this can often help us to get a handle on their representations. For example, matrix groups like $\text{GL}_n$, $\text{SL}_n$, $\text{SO}_n$ can be viewed as differentiable manifolds, or as algebraic varieties in algebraic geometry. They act on various other varieties in natural ways, and standard geometric procedures (cohomology) then prove to be a rich source of representations. Exploiting these geometric structures in representation theory is what we call, not surprisingly, geometric representation theory.

Here is an example: For groups $G$ like $\text{GL}_n(\mathbb{C})$, we can study the representation theory of $G$ by its 'linear approximation', the associated Lie algebra $\mathfrak{g}$. This is competely analogous to how we might approximate a function by the first terms in its Taylor expansion, or some geometric object by its tangent space (in fact, to say that this is an analogy is an understatement).

One can then show that representations of $\mathfrak{g}$ can be (essentially) identified with a category of geometric objects: $\mathcal{D}$-modules on the flag variety associated to $G$ (we ignore certain twists here). This equivalence, originally due to Beilinson-Bernstein and Brylinski-Kashiwara, is important not because it is an equivalence (mathematics is not an exercise in expressing the same thing in as many different ways as possible), but because it is a particularly illuminating equivalence. Using the language of $\mathcal{D}$-modules and viewing representations through this prism, we can translate some really hard algebraic questions into relatively straightforward geometric ones! The proof of the Kazhdan-Lusztig conjectures, describing the character of simple $\mathfrak{g}$-representations, is a prime example: Replace $\mathfrak{g}$-representations by $\mathcal{D}$-modules, replace $\mathcal{D}$-modules by perverse sheaves via the Riemann-Hilbert correspondence (see below), and everything follows relatively explicitly from the geometry of the flag variety.

So what is a $\mathcal{D}$-module? It is a module over the sheaf of differential operators $\mathcal{D}_X$ on a variety $X$. If you know about $\mathcal{O}$-modules (modules over the sheaf of functions), you can think of $\mathcal{D}$-modules as a non-commutative, differential analogue. Instead of dwelling on a more formal definition, two points are worth making here: Firstly, there are conceptual similarities between $\mathcal{D}_X$ and the enveloping algebra $U(\mathfrak{g})$ of a Lie algebra (both clearly encode infinitesimal, tangential information, the tangent sheaf on $X$ playing very much the same role as $\mathfrak{g}$ in $U(\mathfrak{g})$). In fact, the globally defined differential operators on the flag variety are isomorphic to a quotient of $U(\mathfrak{g})$ so the Beilinson-Bernstein equivalence we mentioned is not an abstract identification, but displays an intrinsic connection between the two concepts. Secondly, the term 'differential operators' rightly suggests a connection to differential equations on $X$: given a system of differential equations, we can form an associated $\mathcal{D}$-module, and there is even an operation of 'solving' this $\mathcal{D}$-module by taking what is called the solution complex. If the differential equation is sufficiently nice, we end up with rather special complexes called perverse sheaves. This is what the Riemann-Hilbert correspondence mentioned above is about.

Thus the theory of $\mathcal{D}_X$-modules establishes valuable connections between algebraic, representation-theoretic questions and much more geometric objects, encoding subtle topological information of the space $X$ (in this case the flag variety). We now also bring number theory into the mix. One main aim of my research is to study $\mathcal{D}$-modules in the setting of nonarchimedean analytic geometry, using what are called rigid analytic varieties (developed by Tate). Can we understand how $\text{GL}_n(\mathbb{Q}_p)$ acts on $\mathbb{Q}_p$-vector spaces (imposing suitable restrictions of continuity or analyticity) by considering $\mathcal{D}$-modules on a rigid analytic flag variety? Can we use this geometric picture to make further progress towards a $p$-adic local Langlands correspondence (which is so far only settled for $\text{GL}_2(\mathbb{Q}_p)$)? What can we say about the relation between $\mathcal{D}$-modules in this $p$-adic setting and $p$-adic differential equations? What form would a $p$-adic Riemann-Hilbert correspondence take?

Konstantin Ardakov, with whom I am working here in Oxford, has initiated this project together with Simon Wadsley, by establishing a well-behaved notion of $\stackrel{\frown}{\mathcal{D}}$-modules on rigid analytic spaces and proving an analogue of the Beilinson-Bernstein equivalence. So far, much of my own work has concentrated on parallels between this new $p$-adic picture and the classical setting: just as $\mathcal{D}$ shares many features with a polynomial algebra, so $\stackrel{\frown}{\mathcal{D}}$ is rather similiar to the algebra of analytic functions on a vector space (but of course non-commutative). Moreover, one can prove a finiteness result for the pushforward along proper morphisms, heavily inspired both by the complex and the commutative non-archimedean case (Kiehl's Proper Mapping Theorem). As Ardakov's equivalence can be realized as a pushforward from the flag variety to a point, this generalizes some of the previous results and places them in a broader geometric context.

But this is not the end of the story. In particular when it comes to regular holonomic $\mathcal{D}$-modules (corresponding to the 'nice' differential equations in the classical picture), recent work suggests that the subtleties of nonarchimedean analysis allow for rather unexpected behaviour, making the theory both more complicated and potentially richer than in the complex case. For example, even for innocent equations like $xf'=\lambda f$ for some scalar $\lambda$, the behaviour of the associated $\stackrel{\frown}{\mathcal{D}}$-module on a punctured $p$-adic disc depends crucially on certain arithmetic properties of the parameter $\lambda$. Much more work is needed to fully develop a language of $\mathcal{D}$-modules as powerful as in the classical case, and to let their flexibility bear on questions from representation theory, number theory and $p$-adic geometry alike."

For more detailed discussion of the work please click here and here.

Wednesday, 17 October 2018

Categorification and Quantum Field Theories

Oxford Mathematician Elena Gal talks about her recently published research.

"Categorification is an area of pure mathematics that attempts to uncover additional structure hidden in existing mathematical objects. A simplest example is replacing a natural number $n$ by a set with $n$ elements: when we attempt to prove a numerical equation, we can think about it in terms of sets, subsets and one-to-one correspondences rather than just use algebraic manipulations. Indeed this is the natural way to think about the natural numbers - this is how children first grasp rules of arithmetic by counting stones, coins or sea shells. In modern mathematics we often encounter far more complicated objects which intuitively we suspect to be "shadows" of some richer structure - but we don't immediately know what this structure is or how to construct or describe it. Uncovering such a structure gives us access to hidden symmetries of known mathematical entities. There is reasonable hope that this will eventually enrich our understanding of the physical world. Indeed the object our present research is concerned with originates in quantum physics.

The term "categorification" was introduced about 15 years ago by Crane and Frenkel in an attempt to construct an example of 4-dimensional Topological Quantum Field Theory (TQFT for short). TQFTs are a fascinating example of the interaction between modern physics and mathematics. The concept of quantum field theory was gradually developed by theoretical physicists to describe particle behavior. It was later understood that it can also be used to classify intrinsic properties of geometric objects. The state of the art for now is that mathematicians have a way of constructing TQFTs in 3 dimensions, but not higher. The key to rigorous mathematical constructions of 4-dimensional TQFTs is thought to lay in categorification.

The kind of structure that sets (rather than numbers!) form is called a category. This concept was first introduced in 1945 by Eilenberg and Mac Lane. It is now ubiquitous in pure mathematics and appears to find its way into more "applied sciences", like computer science and biology. A category is a collection of objects and arrows between them, satisfying certain simple axioms. For example the objects of the category $\mathbf{Sets}$ are sets and the arrows are the maps between them. The arrows constitute the additional level of information that we obtain by considering $\mathbf{Sets}$ instead of numbers.

Suppose we are given two sets: $A$ with $n$ elements and $B$ with $m$ elements - what is the number of different ways to combine them into one set within the category Sets? We must take a set with $n+m$  elements $C$ and count the number of arrows $A \hookrightarrow C$ that realize $A$ as a subset of $C$. The number of such arrows is given by a binomial coefficient $n+m\choose n$. We can now consider a new operation $\diamond$ given by the rule $n\diamond m = {n+m\choose m}(n+m)$. In this way given a sufficiently nice category $\mathcal{C}$ we can define a mathematical object called the Hall algebra of $\mathcal{C}$. Remarkably, if instead of the category $\mathbf{Sets}$ we consider the category $\mathbf{Vect}$ of vector spaces, we obtain a quantization of this operation where the binomial coefficient $n+m\choose m$ is replaced by its deformation with a parameter $q$. The result is the simplest example of a mathematical object called a quantum group. Quantum groups were introduced by Drinfeld and Jimbo 30 years ago, and as it later turned out they (or more precisely the symmetries of vector spaces that they encode their categories of representations) are precisely what is needed to construct 3-dimensional TQFTs. The upshot is that to move one dimension up we need to categorify Hall algebras.

In our joint project Adam GalKobi Kremnitzer and I use a geometric approach to quantum groups pioneered by Lusztig. The categorification of quantum groups is given by performing the Hall algebra construction we saw above for mathematical objects called sheaves. Using sheaves allows us to remember more information about the category. In our recent work we define an algebra structure on the dg-category of constructible sheaves. This recovers the existing work on categorification of quantum groups by Khovanov, Lauda and Rouquier in a different language. The advantage of our approach is that it incorporates the categorification of the "dual" algebra structure that every Hall algebra has. This should lead to an understanding of the class of symmetries that it generates (in mathematical language, to the construction of the monoidal category of its representations). 

This is the key step to constructing 4-dimensional TQFTs. For more details and updates please click here."

This work is funded by an Engineering and Physical Sciences Research Council (EPSRC) grant.

Monday, 15 October 2018

What happens when aircraft fly through clouds? From high speed drop impact to icing prevention

As you settle into your seat for a flight to a holiday destination or as part of yet another business trip, it is very easy to become absorbed by the glossy magazines or the novel you've been waiting forever to start reading. Understandably, the phrase "safety features on board this aircraft" triggers a rather unenthusiastic response. But you may be surprised by some of the incredible technology just a few feet away that is there to make sure everything goes smoothly.


Figure 1: Aircraft flying through high liquid water content environment. Custom-made watercolor painting by graphic designer Anca Pora.


On a cloudy or rainy day (of which there are no shortages here in the United Kingdom), airplanes have to navigate the local crowded airspace and fly through very humid conditions. Tiny drops of water hit the surface of the aircraft and start accumulating, forming thin liquid films and rivulets. Once a certain altitude is reached, temperatures fall sharply and these patches of water may quickly freeze and become a real danger. In fact, after human error and mechanical failure, weather-related incidents are next in line and icing is one of the main culprits. The build-up of ice can affect both flight efficiency (fuel economy) and safety, especially as it tends to form near wings and nacelles, where the engines are located. Right now, protocols are in place to divert energy from the engines and heat up specific problem regions and avoid potential issues. But this is a largely inefficient process and still very little is known about what the liquid on the surface actually does. In fact, even the brilliant engineers of fiction have given this some thought. In one of the action-packed scenes of the 2008 Iron Man movie, Tony Stark lures his metal-suited opponent high up into the atmosphere and triumphantly asks the frosted figure behind him: "How'd you solve the icing problem?" We're still working on it in the real world Tony.

Figure 2: Schematic of a typical aircraft component such as a wingtip or nacelle lipskin interacting with liquid droplets in the atmosphere.


Attempting to understand the detailed effects in this scenario leads to what applied mathematicians call a multi-scale problem (see Figure 2 for a schematic). On the one hand one needs to model and account for the complex high speed air flow around specialised geometries (the aircraft itself or aircraft parts). On the other hand, one would like to investigate the detailed dynamics surrounding physical processes such as violent drop impact, with features changing at the sub-micron scale inside the capture region on the aircraft surface. Add to the above further multi-physics effects (such as temperature) and an incredibly rich and difficult landscape emerges, which cannot be dealt with by sheer brute force.

Presently most commercial software used by engineers focus on the larger of the two scales in order to include manufacturer-specific geometries, while the fluid mechanics of the splash itself is severely simplified. As outlined by Gent et al (2000), some of the key building blocks are to assume the drops themselves are solid, non-deformable spheres that do not affect the air flow and follow simple particle-based trajectory updates as a result of them being acted on by the air velocity. Consequently full coupling with the background air flow, drop deformation, collision, coalescence and microdrop ejection and dynamics are all typically neglected or empirically modelled, even in close vicinity to the surface. While this may be reasonable (up to a certain extent) for the very smallest of drops, it is no longer accurate for the larger supercooled droplets.

With regulatory agencies such as the EASA and FAA recently updating flight safety certification standards, the issue of liquid build-up leading to aircraft icing is currently at the forefront of aerospace research. The topic underpinned several work packages within the recently completed SANTANA Innovate UK grant, with Bombardier Aerospace UK Ltd. Belfast as lead industrial partner.

Figure 3: Geometry of interest for drop impact process, with drop velocity $U_\infty$, drop diameter $D$ and impingement angle $\theta$ as main parameters. Determining what proportion of the drop volume remains on the surface (stick) and how much is ejected away in the form of secondary microdroplets (blow-off) is a one of the key problems in improving water collection efficiency measures.


Oxford Mathematician Radu Cimpeanu together with collaborators from Imperial College London led by Demetrios Papageorgiou and engineers at Bombardier Aerospace have recently looked at the problem of drop impact onto aircraft surfaces from a different perspective.

First, the opportunity to take advantage of the disparity in lengthscales between the drops and the solids being impacted has been identified and the complex system was reduced to a canonical problem, illustrated in Figure3. Even in the worst case scenarios, the drops will meet what can be accurately approximated as flat surfaces. The drop size, velocities and impacting angle need to be taken into account, however locally the variations in the aircraft shape are not significant. Next, the air flow around the solid itself was accounted for using the framework of oblique stagnation-point flow. This analytically tractable flow model provides both a simple way of introducing the impact angle in a stable manner, while also producing the near surface boundary layer structures which are known to occur at these large speeds. The timescale of the event (just a few hundredths of a second) allowed further simplifications and ultimately enabled the researchers to focus on the detailed process of the impact itself in the target conditions, without introducing artificial restrictions.

The resulting model accounts for the full coupling between the air and the liquid, solving the Navier-Stokes equations (the partial differential equations governing the motion of fluids) using state-of-the-art computational tools that capture the physics behind violent dynamics in detail as opposed to resorting to the traditional parameter fitting exercises. This was only possible by reducing the problem to a smaller, more approachable setting. Even so, large scale high performance computing facilities were required to elucidate the flow characteristics, with tens of thousands of CPU hours needed to span the parameter space of interest and link the setup to the few experimental studies of this scenario, e.g. Papadakis et al. (2004), NASA.

Figure 4: Top view of a small $D=200\ \mu$m drop (left) and a relatively large $D=200\ \mu$m drop (right) after having impacted the solid surface at an angle of $\theta = 90^{\circ}$.


The main findings may be analysed by considering three distinct stages:

1. Pre-impact: As the drops approach the surface, the transition from spherical to ellipsoidal drop shapes and eventual break-up was observed, quantified and compared to the experimental setup of Sor and Garcia-Magarino (2015). Early on in the deformation process the good qualitative and quantitative agreement between experiment and model was confirmed, while later on the computational platform allowed closer inspection and quantitative understanding of the disintegrating drop beyond the capabilities of the laboratory imaging equipment.

2. Impact: To gain insight into the immediate aftermath of the impact itself, together with Dr. Matthew Moore (previously Imperial College London, now Oxford Mathematics), techniques involving complex and matched asymptotic analysis have been employed in a similar large velocity context to study the formation of the high speed jet resulting from the splash and its properties, which underlie the subsequent drop formation and ejection.

3. Post-impact: The microdrops resulting from the violent splash would be very difficult to visualise experimentally due to the limited resources of even the most modern laboratories, let alone in the noisy environment of a real flight data collection exercise. Purely analytically this is also intractable, primarily due to the subtleties surrounding the continuous topological changes (rupture of the main drop into multiple small drops) in the flow. However the developed numerical approach comes to the rescue and allows the extraction of interesting dynamics transitioning from the neat spreading (or pancaking) motion of small drops to the violent splash of large drops, as shown in Figure 4. Finally spatio-temporal maps of the secondary drop movement are provided and quantities such as secondary drop volume distributions (with an example illustrated in Figure 5) or surface areas which characterise the regions susceptible to freezing may be calculated.

Figure 5: Secondary drop size distribution as a function of time for a relatively large $D \approx 200\ \mu$m drop impinging onto a solid surface at $\theta = 90^{\circ}$. An initially log-normal distribution develops a secondary local maximum as a result of the secondary drop dynamics (movement, break-up, coalescence) after the impact. Reproduced from Cimpeanu and Papageorgiou (2018).

Through this work, the researchers described fluid dynamical processes beyond the reach of previous simplified models, taking into account significantly more of the underlying physics. The first stages of the investigation have recently been published, with several extensions currently ongoing. The multi-scale coupling means that the proposed methodology can be embedded into the design pipeline for a large range of flow conditions and/or aircraft prototypes, with the challenging effects shifted to the local splashing problem and the behaviour being transmitted back to the larger scale seamlessly and flexibly.

The presented drop impact model addresses key questions at a fundamental level. However, the conclusions of the study extend towards the advancement of understanding of liquid dynamics on aircraft surfaces in a practical manner. It potentially leads to improvements in anti-icing techniques, which have important implications for aircraft safety at a time when both the numbers and types of machines flying up above are expanding at an unprecedented rate.



Friday, 12 October 2018

Are there generic features of diseases such as Alzheimer's that can be explained from simple mechanistic models?

Neurodegenerative diseases such as Alzheimer’s or Parkinson’s are devastating conditions with poorly understood mechanisms and no known cure. Yet a striking feature of these conditions is the characteristic pattern of invasion throughout the brain, leading to well-codified disease stages visible to neuropathology and associated with various cognitive deficits and pathologies.

The similarities between these diseases has led to the hypothesis that they are prion-like: their evolution is driven by some toxic form of a protein spreading through the brain similar to the better characterized prion diseases (such as scrapie in sheep and Creutzfeldt-Jakob disease). As toxic proteins spread, they accumulate and form aggregates. Eventually, these aggregates form tissue lesions, initiate cell death and induce tissue atrophy, leading invariably to a loss of cognitive functions and, ultimately, death.

This prion-like hypothesis is simple enough that it can be tested mathematically and used as a postulate for modelling the invasion of neurodegenerative diseases. In an article published in Physical Review Letters, Oxford Mathematics's Alain Goriely and a team of fellow scientists from Stanford University and Stevens Institute of Technology, has shown that these patterns can be explained from a mathematical model based on generic effects combining the production of new toxic proteins from native ones and the preferential diffusion along axonal pathways in the brain.

Top row: evolution of the toxic protein through the brain
Middle row: MRI of a patient with Alzheimer’s disease in three successive years
Bottom row: shrinking pattern predicted from the mathematical model

The team ran the mathematical model simulated in full brain geometry obtained from MRI scans but with different initial seeding regions characteristic of each disease. Remarkably, this model reproduces the characteristic evolution of different neurodegenerative diseases, the evolution of the total toxic protein load, as well as the typical atrophy patterns associated with tissue removal. This initial model provides a better qualitative understanding of the mechanisms at work during the evolution of these diseases and opens the door to a new quantitative and physics-based approach to studying the propagation of neurodegenerative diseases and identifying new therapeutic targets.

As Alain Goriely says: "Despite the complexity of these diseases, there are some generic features that can be explained from simple mechanistic models. The evolution of the disease in time through the brain is the result of simple underlying mechanisms. The breakthrough in understanding is that it can, in principle, help us identify the key factors affecting this propagation and give us new ideas for therapeutic targets."


Thursday, 11 October 2018

Random minimum spanning trees

Christina Goldschmidt from the Department of Statistics in Oxford talks about her joint work with Louigi Addario-Berry (McGill), Nicolas Broutin (Paris Sorbonne University) and Gregory Miermont (ENS Lyon) on random minimum spanning trees. 

"One of the most basic problems in combinatorial optimisation is the problem of finding the minimum spanning tree of a graph. We are given a connected graph $G = (V, E)$ whose edges are endowed with weights $(w_e, e \in E)$, where $w_e \ge 0$ for all $e \in E$. The weight of a subgraph of $G$ is the sum of the weights on its edges, and we seek a connected spanning subgraph of $G$ of minimal weight; it's easy to see that this must be a tree, called the minimum spanning tree (MST). (If the weights are all distinct then the MST is unique.) For example, we might think of the graph as representing a collection of cities and the edge-weights as representing the cost of building a road between its end-points; the MST is then the lowest-cost way of building a road-network which connects all of the cities.

The minimum spanning tree problem turns out to be easy to solve algorithmically, via one of several greedy algorithms. We will describe two of these algorithms, which are in some sense opposites. The first is known as Kruskal's algorithm, and proceeds as follows. List the edges as $e_1, e_2, \ldots$ in increasing order of weight (breaking ties arbitrarily), so that $w_{e_1} \le w_{e_2} \le \ldots$ We now construct the MST: go through the edges in the given order, and include an edge in the subgraph if and only if it does not create a cycle. The other algorithm (which we might call the reverse Kruskal algorithm, or the cycle-breaking algorithm) starts by listing the edges in decreasing order of weight, so that $w_{e_1} \ge w_{e_2} \ge \ldots$, and then goes through the edges one by one in this order, removing an edge if and only if it sits in a cycle. It's a nice exercise to check that these two procedures both yield the MST.

Let's now start with one of the simplest possible graphs: the complete graph on $n$ vertices (with vertices labelled from 1 to $n$), in which every possible edge between two vertices is present. What does a 'typical' MST of a large complete graph look like? In order to make sense of this question, we need a model. Let us assign the edges independent and identically distributed random weights, with uniform distribution on the interval $[0,1]$. (It doesn't actually matter which distribution we choose as long as it has the property that the probability of two edges having the same weight is 0, because the MST depends only on the induced ordering of the edges.) What can we say about the MST, $M_n$ given by this procedure, which is now a random tree with vertices labelled by 1 up to $n$? We're mostly going to be interested in asymptotics as $n \to \infty$.

At first sight, you might think that the tree will just be uniform on the set of possibilities. Cayley's formula tells us that there are $n^{n-2}$ different trees on $n$ labelled vertices, and you might imagine that we are getting each of those with the same probability. This turns out to be very far from the truth! (Actually, you can check that they're not the same for, say, $n=4$, by a direct calculation). But we're mostly interested in what's happening for large $n$.) One way to characterise the difference is to ask how far apart two vertices typically are in these two trees. In the uniform random tree, $T_n$, if we pick two vertices uniformly at random, their distance apart is a random variable $D_n$ which is such that $n^{-1/2}D_n$ converges in distribution to a random variable $D$ as $n \to \infty$. So for a large instance of $T_n$, distances are typically varying in $n^{1/2}$. If you ask the same question in the MST, $M_n$, the answer turns out to be that typical distances vary in $n^{1/3}$.


Figure 1: A large uniform random tree

The best way to see this turns out to be via a connection with one of the most famous models from probabilistic combinatorics: the Erdős–Rényi random graph, $G(n,p)$. This is one of the simplest random graph models imaginable: take $n$ vertices, labelled from 1 to $n$, and for every possible edge include it with probability $p$ and don't include it otherwise, independently for different possible edges. It turns out that this model undergoes a so-called phase transition, a term we borrow from physics to mean a huge change in behaviour for a small change in some underlying parameter. Here, it turns out that the right parameterisation to take is $p = c/n$, where $c$ is a constant. For such a value of $p$, each vertex has a binomial number of neighbours with parameters $n-1$ and $c/n$, which has mean approximately $c$. Now, if $c < 1$, the graph contains only relatively small connected components, of size at most a constant multiple of $\log n$. On the other hand, if $c > 1$, the largest component occupies a positive proportion of the vertices, and all of the others are at most logarithmic in size. We refer to this phenomenon as the emergence of the giant component.

The behaviour is much more delicate at the point of the phase transition, $c = 1$. Here, there is an intermediate component size which appears: the largest components (and there are many of them!) have sizes on the order of $n^{2/3}$. In fact, this is true slightly more generally: we can take $p = 1/n + \lambda/n^{4/3}$ for any $\lambda \in \mathbb{R}$, and the same size-scaling occurs. This range of $p$-values is known as the critical window. For any point inside the critical window, if we let $C_1^n, C_2^n, \ldots$ be the sizes of the components, listed in decreasing order, then a beautiful result of David Aldous from 1997 says that $n^{-2/3} (C_1^n, C_2^n, \ldots)$ converges in distribution to a limit sequence $(C_1, C_2, \ldots)$ which is related to the lengths of the intervals of time which a Brownian motion with drift spends strictly above its running minimum. He also proved that the components are quite 'tree-like', in that each only has finitely many more edges than a tree on the same vertex-set. In joint work with Louigi Addario-Berry and Nicolas Broutin from 2012, I extended this result to give a full description of the limiting component structures. The right way to think about a limiting component is as a metric space: the vertices are the points of the metric space, and the distance between two vertices is the so-called graph distance, namely the number of edges traversed in the shortest path between them. Such a component has size on the order of $n^{2/3}$ (with a random pre-factor), so that in order to have any hope of getting a limit, we're going to need to rescale in some way. It turns out that we need to rescale the graph distance by $n^{-1/3}$ in order to get a nice limit metric space. The limiting components are sort of continuum analogues of tree-like connected graphs. (They're quite closely related to the limit of a large uniform random tree.)


Figure 2: A large component of a critical Erdős–Rényi random graph. Picture by Nicolas Broutin.

How does this help us to understand the MST? Firstly, let's introduce a particular way of building the Erdős–Rényi random graph $G(n,p)$. Start from the complete graph and use the same independent uniform edge-weights that we used to construct the MST, but now do something slightly different: simply keep every edge whose weight is less than or equal to $p$. Since a uniform random variable on $[0,1]$ is less than or equal to $p$ with probability $p$, this gives a realisation of $G(n,p)$. Moreover, we have a nice monotonicity in $p$, in that if we increase $p$, we include more edges. In other words, we can think of a process evolving in time, where 'time' is given by the value $p$, which varies from 0 to 1. Notice that this does something very similar to Kruskal's algorithm: as we increase $p$, every so often we reach the weight of the next edge on the list, it's just that in the Erdős–Rényi random graph setting we always include the edge, whereas in Kruskal's algorithm we only include it if it doesn't create a cycle. In particular, if we imagine doing both procedures simultaneously, then the difference between the two is that Kruskal's algorithm yields a forest at every step until its very final one when the subgraph becomes connected, whereas the Erdős–Rényi random graph process has more edges. But the vertex-sets of the components of the forest and graph are the same in the two cases: the only difference is edges which lie in cycles. If we take a snapshot of both processes at $p = 1/n + \lambda/n^{4/3}$ then the graph is still quite forest-like, in that each component only has a few more edges than the Kruskal forest.

What happens as we move through the critical window i.e. as we increase $\lambda$? The largest components gradually join together (they will eventually all be part of the giant) and we also insert more and more edges which create cycles. As we move through the critical window, whether a particularly vertex is contained in the current largest component is something that can be true for a bit and then cease to be true, or vice versa, as the components randomly aggregate. But if we take $\lambda$ to be large enough then eventually one component 'wins the race': its vertices remain within the largest component forever more. It turns out that the metric structure of the MST of this component is a good approximation to the metric structure of the MST of the whole graph: the difference between the two consists of a whole bunch of tiny trees which are glued on at points which are reasonably uniformly spread across the component, and thus don't make a huge difference to, for example, distances between typical vertices. There is a subtlety here, though: the vast majority of the vertices in the graph (an asymptotic proportion 1) are, at this point, still outside the largest component!

To get from the largest component of the Erdős–Rényi random graph process to its MST, we apply the cycle-breaking algorithm. We will only ever remove edges in cycles, so we can restrict our attention to the set $S$ of edges lying in cycles. If we just observe the component but not its edge-weights then the highest-weight edge lying in a cycle is simply uniformly distributed on $S$. Once we remove the highest-weight edge, we update $S$ to contain only the edges that still lie in cycles, and repeat the procedure of removing a uniform edge and updating until $S$ is empty. (Since we only have finitely many more edges than a tree, this procedure terminates.) This procedure turns out to pass nicely to the limit, and so we can make sense of the limiting MST of the largest component.

Making this argument rigorous takes quite a lot of work, but the upshot is we get the existence of a random compact metric tree-like space $M$ (the technical term is an $\mathbb{R}$-tree) such that if we rescale distances in $M_n$ by $n^{-1/3}$, we have convergence in distribution to $M$.


Figure 3: A realisation of the minimum spanning tree of the complete graph. Picture by Louigi Addario-Berry. 

Lots of questions remain open about $M$. For example, in a uniform random tree $T_n$, we saw that the distance between two uniform points converges on rescaling by $n^{-1/2}$ to a limit $D$, which has an explicit distribution: we have $\mathbb{P}(D > x) = \exp(-x^2/2), x \ge 0$. This is just one aspect of a much more general result: the tree $T_n$, considered as a metric space with the graph distance rescaled by $n^{-1/2}$, converges in distribution to a limit $T$ which is known as the Brownian continuum random tree, and whose distributional properties are very well-understood. $D$ is the distance between two uniform points of $T$. The corresponding 'two-point distance' in $M$ is currently unknown. Understanding the distribution of this distance would be the first step in characterising the law of $M$. We do know some intriguing things about it, though. For example, $M$ is a random fractal, which turns out to be 3-dimensional: its Minkowski (or box-counting) dimension is 3 almost surely. This contrasts with $T$, which has Minkowski dimension 2 almost surely."

For more on this topic follow the links:

David Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent, Annals of Probability 25, 2 (1997), pp.812-854.

Louigi Addario-Berry, Nicolas Broutin and Christina Goldschmidt, The continuum limit of critical random graphs, Probability Theory and Related Fields 152, 3-4 (2012), pp.367-406. 

Louigi Addario-Berry, Nicolas Broutin, Christina Goldschmidt and Gregory Miermont, The scaling limit of the minimum spanning tree of the complete graph, Annals of Probability 45, 5 (2017), pp.3075-3144.

Monday, 8 October 2018

Oxford Mathematicians Vicky Neale and Ursula Martin nominated for Suffrage Science awards

Congratulations to Oxford Mathematicians Vicky Neale and Ursula Martin who have been nominated for Suffrage Science awards. The awards celebrate women in science and encourage others to enter science and reach senior leadership roles. The 11 awardees are chosen by the previous award holders and the awards themselves are items of jewellery, inspired by the Suffrage movement, and are passed on as heirlooms from one female scientist to the next. 

Ursula was nominated by Professor Dame Wendy Hall, University of Southampton and Vicky was nominated by Professor Dame Celia Hoyles, University College London.

Friday, 5 October 2018

Using smartphones for detecting the symptoms of Parkinson’s disease

Oxford Mathematician Siddharth Arora talks about his and his colleagues' research in to using smartphone technology to anticipate the symptoms of Parkinson’s disease.

"Parkinson’s disease (PD) is the second most common neurodegenerative disease, the hallmarks of which include tremor, stiffness, and slowness of movement. Existing tests for the assessment of Parkinson’s require in-clinic examination of symptoms by a clinician. This can sometimes cause a delay in diagnosis. It is believed that there are changes in the brain 5 to 10 years before the symptoms of PD become evident.

To try and facilitate early diagnosis of Parkinson’s, together with the Oxford Parkinson's Disease Centre (OPDC) we investigated if smartphones can be used to detect any potential differences in motor symptoms associated with PD and REM Sleep Behaviour Disorder (RBD). It is now increasingly recognised that having RBD may be a risk factor for developing future Parkinson’s. In this study, we used a smartphone app featuring 7 motor tests to measure: (1) Voice, (2) Balance, (3) Gait, (4) Finger tapping, (5) Reaction time, (6) Rest tremor, and (7) Postural tremor. Recordings were collected both in-clinic and at home. Using the smartphone recordings, we extracted key features of interest and used machine learning to quantify patterns of motor impairment that are specific to RBD, PD, and Controls. In one of the largest cohorts of deeply phenotyped participants, we report that smartphones can be used to discriminate between participant groups with a high level of accuracy (84.6% to 91.9% mean sensitivity and specificity). Our research paper focussing on ‘detecting the early motor symptoms’ of Parkinson’s is published here. A pilot study on ‘monitoring the severity of PD symptoms’ can also be accessed here, while a large-scale study using the mPower data to understand the ‘longitudinal characteristics’ of Parkinson's through the analysis of finger tapping and memory tests is published here.

Moreover, we also investigated potential vocal deficits in people who are at an increased risk of Parkinson’s (carriers of LRRK2 mutation). Our preliminary findings suggest that vocal deficits in LRRK2-associated PD may be different than those in idiopathic Parkinson’s. This research could help develop an inexpensive remote screening test for assessing the risk LRRK2-associated Parkinson’s based on voice - click here for the article.

These findings provide an exciting and growing consensus for the utility of digital biomarkers in early and pre-symptomatic Parkinson’s."

Friday, 5 October 2018

Understanding the complicated behaviour of free liquid sheets

Free suspended liquid films or sheets are often formed during industrial production of sprays as well as in natural processes such as sea spray. Early experimental and theoretical investigations of them were done by French physicist Felix Savart, who observed liquid sheets forming by a jet impact on a solid surface, or by two jets impacting each other (1833), and British physicist Arthur Mason Worthington, a pioneer in investigation of the crown splash forming after impact of a drop onto a liquid surface. Worthington observed free liquid fims forming in splashes in the form of ejecta sheets (1908).

The industrial production of sprays proceeds typically via the formation of sheets, which break up at the edges to form ribbons. Ribbons are susceptible to the Rayleigh-Plateau instability, and quickly break up into drops. Liquid sheets also happen to puncture far from their boundaries, nucleating a hole or a collection of adjacent holes on the plane of the film. An intriguing example of such hole formation in a crown splash was observed experimentally. Here the whole liquid sheet forming initially the crown breaks up into soap network of filaments. 

It is therefore of crucial importance to understand the mechanisms leading to the breakup of sheets. In contrast to jets and liquid threads there is no obvious linear mechanism for sheet breakup. Average thickness of a sheet at breakup start has been measured to lie between 100nm and 100μm, depending on the purity of the liquid, and therefore, van der Waals force cannot play a significant role for breakup formation except perhaps in its very last stages.

Figure 1: This image is a watercolor painting by illustrator Anca Pora following the experimental work of Thoroddsen et al (J. Fluid Mech., 557, 63-72) and provided by Dr. Radu Cimpeanu (Oxford Mathematics).


Figure 2: Typical profiles of the height (black), velocity (blue) and temperature (red) for a free liquid sheet


Figure 3: Height profiles in the thinning patch (left) and the sharp forming jump in the temperature (right).

Oxford Mathematician Georgy Kitavtsev together with his collaborators at the University of Bristol and ICMAT, Madrid confirmed recently that variations of temperature or alternatively impurities at the sheet free surfaces (such as diffusing surfactants) promote breakup, because they produce Marangoni forces, which lead to non-steady flows. Intriguingly, even slight variations of  temperature or surfactant distribution can lead to formation of sharp gradients of them that promote consequently sheet rupture in an infinite time at an exponential fast rate (see Figs. 3-4). Using matched asymptotic analysis of the underlying nonlinear system of coupled PDEs the researchers were able to derive analytically the corresponding structure of the liquid sheet undergoing rupture. Consistent with the above experimental observations the found solution demonstrates formation of an exponentially thinning patch inside of the sheet and accumulation of the fluid mass into the forming filaments.

In two subsequent papers the researchers looked now at evolution of pure viscous sheets and showed that generic solutions to a PDE system describing their evolution rather exponentially asymptotically decay to the flat profile. By that they provided a proof of the conjecture formally accepted in the physical literature that a viscous sheet cannot rupture in a finite time in the absence of external forcing. In this proof, a transformation of the PDE system into Lagrangian coordinates turned out to be very useful. Furthermore, in the absence of or for negligible surface tension the Lagrange system is given by a single singular diffusion equation with a source term determined solely by the initial height and velocity distribution in the sheet. In this case, an exponential asymptotic convergence of solutions to the latter equation to the non-homogeneous limit profiles was observed firstly numerically (see Fig. 5) and understood analytically.


Figure 4: Log-linear plot of the minimum height of the sheet as function of time.


Figure 5: Convergence to non-homogeneous stationary height profiles of free viscous liquid sheets in the absence of surface tension.

In summary, these mathematical results open several new perspectives for future industrial applications of free thin liquid sheets and understanding of
their complicated behaviour.

Thursday, 4 October 2018

A mathematical puzzle - 180 men, 93 women, 33 nationalities. Who are they?

Okay it's not so hard.

Welcome to our new undergraduate students, young mathematicians of diverse nationalities from Afghan to Kazakh, Syrian to Pakistani, Malaysian to Greek. And 70% of UK students from state schools. Welcome to Oxford Mathematics, all of you.

And watch out for a snippet or two from their lectures next week on our Twitter and Facebook pages. We hope it will inspire those of you who hope to join them in the future.