Interlace polynomials: Enumeration, unimodality and connections to codes

The interlace polynomialq was introduced by Arratia, Bollobás, and Sorkin. It encodes many properties of the orbit of a graph under edge local complementation (ELC). The interlace polynomial Q, introduced by Aigner and van der Holst, similarly contains information about the orbit of a graph under local complementation (LC). We have previously classified LC and ELC orbits, and now give an enumeration of the corresponding interlace polynomials of all graphs of order up to 12. An enumeration of all circle graphs of order up to 12 is also given. We show that there exist graphs of all orders greater than 9 with interlace polynomials q whose coefficient sequences are non-unimodal, thereby disproving a conjecture by Arratia et al. We have verified that for graphs of order up to 12, all polynomials Q have unimodal coefficients. It has been shown that LC and ELC orbits of graphs correspond to equivalence classes of certain error-correcting codes and quantum states. We show that the properties of these codes and quantum states are related to properties of the associated interlace polynomials.     

Directed graph representation of half-rate additive codes over GF(4)

We show that (n, 2 ⁿ ) additive codes over GF(4) can be represented as directed graphs. This generalizes earlier results on self-dual additive codes over GF(4), which correspond to undirected graphs. Graph representation reduces the complexity of code classification, and enables us to classify additive (n, 2 ⁿ ) codes over GF(4) of length up to 7. From this we also derive classifications of isodual and formally self-dual codes. We introduce new constructions of circulant and bordered circulant directed graph codes, and show that these codes will always be isodual. A computer search of all such codes of length up to 26 reveals that these constructions produce many codes of high minimum distance. In particular, we find new near-extremal formally self-dual codes of length 11 and 13, and isodual codes of length 24, 25, and 26 with better minimum distance than the best known self-dual codes.     

Granular Rayleigh-Taylor instability: experiments and simulations

A granular instability driven by gravity is studied experimentally and numerically. The instability arises as grains fall in a closed Hele-Shaw cell where a layer of dense granular material is positioned above a layer of air. The initially flat front defined by the grains subsequently develops into a pattern of falling granular fingers separated by rising bubbles of air. A transient coarsening of the front is observed right from the start by a finger merging process. The coarsening is later stabilized by new fingers growing from the center of the rising bubbles. The structures are quantified by means of Fourier analysis and quantitative agreement between experiment and computation is shown. This analysis also reveals scale invariance of the flow structures under overall change of spatial scale.     

A tensor product matrix approximation problem in quantum physics

We consider a matrix approximation problem arising in the study of entanglement in quantum physics. This notion represents a certain type of correlations between subsystems in a composite quantum system. The states of a system are described by a density matrix, which is a positive semidefinite matrix with trace one. The goal is to approximate such a given density matrix by a so-called separable density matrix, and the distance between these matrices gives information about the degree of entanglement in the system. Separability here is expressed in terms of tensor products. We discuss this approximation problem for a composite system with two subsystems and show that it can be written as a convex optimization problem with special structure. We investigate related convex sets, and suggest an algorithm for this approximation problem which exploits the tensor product structure in certain subproblems. Finally some computational results and experiences are presented.     

The selfnegadual properties of generalised quadratic Boolean functions

We define and characterise selfnegadual generalised quadratic Boolean functions by establishing a link, both to the multiplicative order of symmetric binary matrices, and also to the Hermitian self-dual ${\mathbb{F}_4}$ -linear codes. This facilitates a novel way to classify Hermitian self-dual ${\mathbb{F}_4}$ -linear codes.