Vertex splitting and connectivity augmentation in hypergraphs

We consider problems of splitting and connectivity augmentation in hypergraphs. In a hypergraph G = (V +s, E), to split two edges su, sv, is to replace them with a single edge uv. We are interested in doing this in such a way as to preserve a defined level of connectivity in V . The splitting technique is often used as a way of adding new edges into a graph or hypergraph, so as to augment the connectivity to some prescribed level. We begin by providing a short history of work done in this area. Then several preliminary results are given in a general form so that they may be used to tackle several problems. We then analyse the hypergraphs G = (V + s, E) for which there is no split preserving the local-edge-connectivity present in V. We provide two structural theorems, one of which implies a slight extension to Mader’s classical splitting theorem. We also provide a characterisation of the hypergraphs for which there is no such “good” split and a splitting result concerned with a specialisation of the local-connectivity function. We then use our splitting results to provide an upper bound on the smallest number of size-two edges we must add to any given hypergraph to ensure that in the resulting hypergraph we have λ(x, y) ≥ r(x, y) for all x, y in V, where r is an integer valued, symmetric requirement function on V*V. This is the so called “local-edge-connectivity augmentation problem” for hypergraphs. We also provide an extension to a Theorem of Szigeti, about augmenting to satisfy a requirement r, but using hyperedges. Next, in a result born of collaborative work with Zoltán Király from Budapest, we show that the local-connectivity augmentation problem is NP-complete for hypergraphs. Lastly we concern ourselves with an augmentation problem that includes a locational constraint. The premise is that we are given a hypergraph H = (V,E) with a bipartition P = {P1, P2} of V and asked to augment it with size-two edges, so that the result is k-edge-connected, and has no new edge contained in some P(i). We consider the splitting technique and describe the obstacles that prevent us forming “good” splits. From this we deduce results about which hypergraphs have a complete Pk-split. This leads to a minimax result on the optimal number of edges required and a polynomial algorithm to provide an optimal augmentation.

Studying reactive processes with classical dynamics: rebinding dynamics in MbNO

A new surface-crossing algorithm suitable for describing bond-breaking and bond-forming processes in molecular dynamics simulations is presented. The method is formulated for two intersecting potential energy manifolds which dissociate to different adiabatic states. During simulations, crossings are detected by monitoring an energy criterion. If fulfilled, the two manifolds are mixed over a finite number of time steps, after which the system is propagated on the second adiabat and the crossing is carried out with probability one. The algorithm is extensively tested (almost 0.5 mu s of total simulation time) for the rebinding of NO to myoglobin. The unbound surface ((FeNO)-N-...) is represented using a standard force field, whereas the bound surface (Fe-NO) is described by an ab initio potential energy surface. The rebinding is found to be nonexponential in time, in agreement with experimental studies, and can be described using two time constants. Depending on the asymptotic energy separation between the manifolds, the short rebinding timescale is between 1 and 9 ps, whereas the longer timescale is about an order of magnitude larger. NO molecules which do not rebind within 1 ns are typically found in the Xenon-4 pocket, indicating the high affinity of NO to this region in the protein.

Spectacle and value in classical Hollywood cinema

This is a primarily meta-critical essay and is in direct dialogue with the argument presented in my essay on Gone with the Wind (published in 'Screen'). Here, however, the emphasis is much more on the challenge my definition of spectacle represents for important traditions of film analysis, particularly ‘mise-en-scène criticism’. I argue for the possibility of spectacle to form part of the ‘organic’ whole of a film’s texture and form, while noting the challenge the concept represents (by dint of certain ideological associations and its taint of commercialism) with ‘organicist’ traditions of interpretative film analysis.

Meteorological phenomena in Western classical orchestral music

Depictions of the weather are common throughout the arts. Unlike in the visual arts, however, there has been little study of meteorological inspiration in music. This article catalogues and analyzes the frequencies with which weather is depicted in a sample of classical orchestral music. The depictions vary from explicit mimicry using traditional and specialized orchestral instruments, through to subtle suggestions. It is found that composers are generally influenced by their own environment in the type of weather they choose to represent. As befits the national stereotype, British composers seem disproportionately keen to depict the UK's variable weather patterns and stormy coastline

A simple analysis of thermodynamic properties for classical plasmas: I. theory

By eliminating the short range negative divergence of the Debye–Hückel pair distribution function, but retaining the exponential charge screening known to operate at large interparticle separation, the thermodynamic properties of one-component plasmas of point ions or charged hard spheres can be well represented even in the strong coupling regime. Predicted electrostatic free energies agree within 5% of simulation data for typical Coulomb interactions up to a factor of 10 times the average kinetic energy. Here, this idea is extended to the general case of a uniform ionic mixture, comprising an arbitrary number of components, embedded in a rigid neutralizing background. The new theory is implemented in two ways: (i) by an unambiguous iterative algorithm that requires numerical methods and breaks the symmetry of cross correlation functions; and (ii) by invoking generalized matrix inverses that maintain symmetry and yield completely analytic solutions, but which are not uniquely determined. The extreme computational simplicity of the theory is attractive when considering applications to complex inhomogeneous fluids of charged particles.

A comparison between classical techniques and eigenstructure assignment in the design of a longitudinal instrument landing system

Although modern control techniques such as eigenstructure assignment have been given extensive coverage in control literature there is a reluctance to use them in practice as they are often not believed to be as `visible' or as simple as classical methods. A simple aircraft example is used, and it is shown that eigenstructure assignment can be used easily to produce a more viable controller than with simple classical techniques.