A new solution for the roommate problem: The Q-stable matchings

The aim of this paper is to propose a new solution for the roommate problem with strict preferences. We introduce the solution of maximum irreversibility and consider almost stable matchings (Abraham et al. [2])and maximum stable matchings (Ta [30] [32]). We find that almost stable matchings are incompatible with the other two solutions. Hence, to solve the roommate problem we propose matchings that lie at the intersection of the maximum irreversible matchings and maximum stable matchings, which are called Q-stable matchings. These matchings are core consistent and we offer an effi cient algorithm for computing one of them. The outcome of the algorithm belongs to an absorbing set.

Synthesis, structure, and photophysics of polypyridophenazine transition-metal complexes

The condensation of phenanthroline-5,6-dione (phendione) with polyamines is a versatile synthetic route to a wide variety of chelating ligands. Condensation with 2,3- napthalene diamine gives benzo[i]dipyrido[3,2-a:2',3'-c]phenazine (bdppz) a ligand containing weakly-coupled orbitals of benzophenazine (bpz) and 2,2' -bipyridinde(bpy) character. The bpy character gives Re and Ru complexes excited-state redox properties; intramolecular electron transfer (ET) takes place to the bpz portion of the ligand. The charge-separated state so produced has an extraordinarily-long 50 µs lifetime. The slow rate of charge recombination arises from a combination of extremely weak coupling between the metal center and the bpz acceptor orbital and Marcus "inverted region" behavior. Molecular orbital calculations show that only 3% the electron density in the lowest unoccupied molecular orbital lies on the bpy atoms of bdppz, effectively trapping the transferred electron on the bpz portion. The rate of charge recombination decreases with increasing driving force, showing that these rates lie in the inverted region. Comparison of forward and back ET rates shows that donor-acceptor coupling is four orders of magnitude greater for photoinduced electron transfer than it is for thermal charge recombination.

Condensation of phendione with itself or tetramines gives a series of binucleating tetrapyridophenazine ligands of incrementally-varying coordination-site separation. When a photoredox-active metal center is attached, excited-state energy and electron transfer to an acceptor metal center at the other coordination site can be studied as a function of distance. A variety of monometallic and homo- and heterodimetallic tetrapyridophenazine complexes has been synthesized. Electro- and magnetochemistry show that no ground-state interaction exists between the metals in bimetallic complexes. Excited-state energy and electron transfer, however, takes place at rates which are invariant with increasing donor-acceptor separation, indicating that a very efficient coupling mechanism is at work. Theory and experiment have suggested that such behavior might exist in extended π-systems like those presented by these ligands.

Condensation of three equivalents of 4,5-dimethyl-1,2-phenylenediamine with hexaketocyclohexane gives the trinucleating ligand hexaazahexamethyltrinapthalene (hhtn). Attaching two photredox-active metal centers and a third catalytic center to hhtn provides means by which multielectron photocatalyzed reactions might be carried out. The coordination properties of hhtn have been examined; X-ray crystallographic structure determination shows that the ligand's constricted coordination pocket leads to distorted geometries in its mono- and dimetallic derivatives.

Conditional independence in quantum many-body systems

In this thesis, I will discuss how information-theoretic arguments can be used to produce sharp bounds in the studies of quantum many-body systems. The main advantage of this approach, as opposed to the conventional field-theoretic argument, is that it depends very little on the precise form of the Hamiltonian. The main idea behind this thesis lies on a number of results concerning the structure of quantum states that are conditionally independent. Depending on the application, some of these statements are generalized to quantum states that are approximately conditionally independent. These structures can be readily used in the studies of gapped quantum many-body systems, especially for the ones in two spatial dimensions. A number of rigorous results are derived, including (i) a universal upper bound for a maximal number of topologically protected states that is expressed in terms of the topological entanglement entropy, (ii) a first-order perturbation bound for the topological entanglement entropy that decays superpolynomially with the size of the subsystem, and (iii) a correlation bound between an arbitrary local operator and a topological operator constructed from a set of local reduced density matrices. I also introduce exactly solvable models supported on a three-dimensional lattice that can be used as a reliable quantum memory.

Mathematical study of complex networks : brain, internet, and power grid

The dissertation is concerned with the mathematical study of various network problems. First, three real-world networks are considered: (i) the human brain network (ii) communication networks, (iii) electric power networks. Although these networks perform very different tasks, they share similar mathematical foundations. The high-level goal is to analyze and/or synthesis each of these systems from a “control and optimization” point of view. After studying these three real-world networks, two abstract network problems are also explored, which are motivated by power systems. The first one is “flow optimization over a flow network” and the second one is “nonlinear optimization over a generalized weighted graph”. The results derived in this dissertation are summarized below.

Brain Networks: Neuroimaging data reveals the coordinated activity of spatially distinct brain regions, which may be represented mathematically as a network of nodes (brain regions) and links (interdependencies). To obtain the brain connectivity network, the graphs associated with the correlation matrix and the inverse covariance matrix—describing marginal and conditional dependencies between brain regions—have been proposed in the literature. A question arises as to whether any of these graphs provides useful information about the brain connectivity. Due to the electrical properties of the brain, this problem will be investigated in the context of electrical circuits. First, we consider an electric circuit model and show that the inverse covariance matrix of the node voltages reveals the topology of the circuit. Second, we study the problem of finding the topology of the circuit based on only measurement. In this case, by assuming that the circuit is hidden inside a black box and only the nodal signals are available for measurement, the aim is to find the topology of the circuit when a limited number of samples are available. For this purpose, we deploy the graphical lasso technique to estimate a sparse inverse covariance matrix. It is shown that the graphical lasso may find most of the circuit topology if the exact covariance matrix is well-conditioned. However, it may fail to work well when this matrix is ill-conditioned. To deal with ill-conditioned matrices, we propose a small modification to the graphical lasso algorithm and demonstrate its performance. Finally, the technique developed in this work will be applied to the resting-state fMRI data of a number of healthy subjects.

Communication Networks: Congestion control techniques aim to adjust the transmission rates of competing users in the Internet in such a way that the network resources are shared efficiently. Despite the progress in the analysis and synthesis of the Internet congestion control, almost all existing fluid models of congestion control assume that every link in the path of a flow observes the original source rate. To address this issue, a more accurate model is derived in this work for the behavior of the network under an arbitrary congestion controller, which takes into account of the effect of buffering (queueing) on data flows. Using this model, it is proved that the well-known Internet congestion control algorithms may no longer be stable for the common pricing schemes, unless a sufficient condition is satisfied. It is also shown that these algorithms are guaranteed to be stable if a new pricing mechanism is used.

Electrical Power Networks: Optimal power flow (OPF) has been one of the most studied problems for power systems since its introduction by Carpentier in 1962. This problem is concerned with finding an optimal operating point of a power network minimizing the total power generation cost subject to network and physical constraints. It is well known that OPF is computationally hard to solve due to the nonlinear interrelation among the optimization variables. The objective is to identify a large class of networks over which every OPF problem can be solved in polynomial time. To this end, a convex relaxation is proposed, which solves the OPF problem exactly for every radial network and every meshed network with a sufficient number of phase shifters, provided power over-delivery is allowed. The concept of “power over-delivery” is equivalent to relaxing the power balance equations to inequality constraints.

Flow Networks: In this part of the dissertation, the minimum-cost flow problem over an arbitrary flow network is considered. In this problem, each node is associated with some possibly unknown injection, each line has two unknown flows at its ends related to each other via a nonlinear function, and all injections and flows need to satisfy certain box constraints. This problem, named generalized network flow (GNF), is highly non-convex due to its nonlinear equality constraints. Under the assumption of monotonicity and convexity of the flow and cost functions, a convex relaxation is proposed, which always finds the optimal injections. A primary application of this work is in the OPF problem. The results of this work on GNF prove that the relaxation on power balance equations (i.e., load over-delivery) is not needed in practice under a very mild angle assumption.

Generalized Weighted Graphs: Motivated by power optimizations, this part aims to find a global optimization technique for a nonlinear optimization defined over a generalized weighted graph. Every edge of this type of graph is associated with a weight set corresponding to the known parameters of the optimization (e.g., the coefficients). The motivation behind this problem is to investigate how the (hidden) structure of a given real/complex valued optimization makes the problem easy to solve, and indeed the generalized weighted graph is introduced to capture the structure of an optimization. Various sufficient conditions are derived, which relate the polynomial-time solvability of different classes of optimization problems to weak properties of the generalized weighted graph such as its topology and the sign definiteness of its weight sets. As an application, it is proved that a broad class of real and complex optimizations over power networks are polynomial-time solvable due to the passivity of transmission lines and transformers.

Lattice quantum codes and exotic topological phases of matter

This thesis addresses whether it is possible to build a robust memory device for quantum information. Many schemes for fault-tolerant quantum information processing have been developed so far, one of which, called topological quantum computation, makes use of degrees of freedom that are inherently insensitive to local errors. However, this scheme is not so reliable against thermal errors. Other fault-tolerant schemes achieve better reliability through active error correction, but incur a substantial overhead cost. Thus, it is of practical importance and theoretical interest to design and assess fault-tolerant schemes that work well at finite temperature without active error correction.

In this thesis, a three-dimensional gapped lattice spin model is found which demonstrates for the first time that a reliable quantum memory at finite temperature is possible, at least to some extent. When quantum information is encoded into a highly entangled ground state of this model and subjected to thermal errors, the errors remain easily correctable for a long time without any active intervention, because a macroscopic energy barrier keeps the errors well localized. As a result, stored quantum information can be retrieved faithfully for a memory time which grows exponentially with the square of the inverse temperature. In contrast, for previously known types of topological quantum storage in three or fewer spatial dimensions the memory time scales exponentially with the inverse temperature, rather than its square.

This spin model exhibits a previously unexpected topological quantum order, in which ground states are locally indistinguishable, pointlike excitations are immobile, and the immobility is not affected by small perturbations of the Hamiltonian. The degeneracy of the ground state, though also insensitive to perturbations, is a complicated number-theoretic function of the system size, and the system bifurcates into multiple noninteracting copies of itself under real-space renormalization group transformations. The degeneracy, the excitations, and the renormalization group flow can be analyzed using a framework that exploits the spin model's symmetry and some associated free resolutions of modules over polynomial algebras.

Caprate: un sistema de interpretación de problemas en lenguaje natural

199 p.

Oxygen isotopes and volatiles in martian meteorites

Oxygen isotopes were measured in mineral separates from martian meteorites using laser fluorination and were found to be remarkably uniform in both δ18O and Δ17O, suggesting that martian magmas did not assimilate aqueously altered crust regardless of any other geochemical variations.

Measurements of Cl, F, H, and S in apatite from martian meteorites were made using the SIMS and NanoSIMS. Martian apatites are typically higher in Cl than terrestrial apatites from mafic and ultramafic rocks, signifying that Mars is inherently higher in Cl than Earth. Apatites from basaltic and olivine-phyric shergottites are as high in water as any terrestrial apatite from mafic and utramafic rocks, implying the possibility that martian magmas may be more similar in water abundance to terrestrial magmas than previously thought. Apatites from lherzolitic shergottites, nakhlites, chassignites, and ALH 84001 (all of which are cumulate rocks) are all lower in water than the basaltic and olivine-phyric shergottites, indicating that the slow-cooling accumulation process allows escape of water from trapped melts where apatite later formed. Sulfur is only high in some apatites from basaltic and olivine-phyric shergottites and low in all other SNCs from this study, which could mean that cumulate SNCs are low in all volatiles and that there are other controlling factors in basaltic and olivine-phyric magmas dictating the inclusion of sulfur into apatite.

Sulfur Kα X-rays were measured in SNC apatites using the electron probe. None of the peaks in the SNC spectra reside in the same position as anhydrite (where sulfur is 100% sulfate) or pyrite (where sulfur is 100% sulfide), but instead all SNC spectra peaks lie in between these two end member peaks, which implies that SNC apatites may be substituting some sulfide, as well as sulfate, into their structure. However, further work is needed to verify this hypothesis.

Ordinary mod p representations of the metaplectic cover of p-adic SL_2

We classify the genuine ordinary mod p representations of the metaplectic group SL(2,F)-tilde, where F is a p-adic field, and compute its genuine mod p spherical and Iwahori Hecke algebras. The motivation is an interest in a possible correspondence between genuine mod p representations of SL(2,F)-tilde and mod p representations of the dual group PGL(2,F), so we also compare the two Hecke algebras to the mod p spherical and Iwahori Hecke algebras of PGL(2,F). We show that the genuine mod p spherical Hecke algebra of SL(2,F)-tilde is isomorphic to the mod p spherical Hecke algebra of PGL(2,F), and that one can choose an isomorphism which is compatible with a natural, though partial, correspondence of unramified ordinary representations via the Hecke action on their spherical vectors. We then show that the genuine mod p Iwahori Hecke algebra of SL(2,F)-tilde is a subquotient of the mod p Iwahori Hecke algebra of PGL(2,F), but that the two algebras are not isomorphic. This is in contrast to the situation in characteristic 0, where by work of Savin one can recover the local Shimura correspondence for representations generated by their Iwahori fixed vectors from an isomorphism of Iwahori Hecke algebras.

Geometric quantization and foliation reduction

A standard question in the study of geometric quantization is whether symplectic reduction interacts nicely with the quantized theory, and in particular whether “quantization commutes with reduction.” Guillemin and Sternberg first proposed this question, and answered it in the affirmative for the case of a free action of a compact Lie group on a compact Kähler manifold. Subsequent work has focused mainly on extending their proof to non-free actions and non-Kähler manifolds. For realistic physical examples, however, it is desirable to have a proof which also applies to non-compact symplectic manifolds.

In this thesis we give a proof of the quantization-reduction problem for general symplectic manifolds. This is accomplished by working in a particular wavefunction representation, associated with a polarization that is in some sense compatible with reduction. While the polarized sections described by Guillemin and Sternberg are nonzero on a dense subset of the Kähler manifold, the ones considered here are distributional, having support only on regions of the phase space associated with certain quantized, or “admissible”, values of momentum.

We first propose a reduction procedure for the prequantum geometric structures that “covers” symplectic reduction, and demonstrate how both symplectic and prequantum reduction can be viewed as examples of foliation reduction. Consistency of prequantum reduction imposes the above-mentioned admissibility conditions on the quantized momenta, which can be seen as analogues of the Bohr-Wilson-Sommerfeld conditions for completely integrable systems.

We then describe our reduction-compatible polarization, and demonstrate a one-to-one correspondence between polarized sections on the unreduced and reduced spaces.

Finally, we describe a factorization of the reduced prequantum bundle, suggested by the structure of the underlying reduced symplectic manifold. This in turn induces a factorization of the space of polarized sections that agrees with its usual decomposition by irreducible representations, and so proves that quantization and reduction do indeed commute in this context.

A significant omission from the proof is the construction of an inner product on the space of polarized sections, and a discussion of its behavior under reduction. In the concluding chapter of the thesis, we suggest some ideas for future work in this direction.

Energy Supply and the Sustainability of Endogenous Growth

29 p.

Crystals that count! Physical principles and experimental investigations of DNA tile self-assembly

Algorithmic DNA tiles systems are fascinating. From a theoretical perspective, they can result in simple systems that assemble themselves into beautiful, complex structures through fundamental interactions and logical rules. As an experimental technique, they provide a promising method for programmably assembling complex, precise crystals that can grow to considerable size while retaining nanoscale resolution. In the journey from theoretical abstractions to experimental demonstrations, however, lie numerous challenges and complications.

In this thesis, to examine these challenges, we consider the physical principles behind DNA tile self-assembly. We survey recent progress in experimental algorithmic self-assembly, and explain the simple physical models behind this progress. Using direct observation of individual tile attachments and detachments with an atomic force microscope, we test some of the fundamental assumptions of the widely-used kinetic Tile Assembly Model, obtaining results that fit the model to within error. We then depart from the simplest form of that model, examining the effects of DNA sticky end sequence energetics on tile system behavior. We develop theoretical models, sequence assignment algorithms, and a software package, StickyDesign, for sticky end sequence design.

As a demonstration of a specific tile system, we design a binary counting ribbon that can accurately count from a programmable starting value and stop growing after overflowing, resulting in a single system that can construct ribbons of precise and programmable length. In the process of designing the system, we explain numerous considerations that provide insight into more general tile system design, particularly with regards to tile concentrations, facet nucleation, the construction of finite assemblies, and design beyond the abstract Tile Assembly Model.

Finally, we present our crystals that count: experimental results with our binary counting system that represent a significant improvement in the accuracy of experimental algorithmic self-assembly, including crystals that count perfectly with 5 bits from 0 to 31. We show some preliminary experimental results on the construction of our capping system to stop growth after counters overflow, and offer some speculation on potential future directions of the field.

Der Verlauf der Nordseetemperaturen seit Ende Oktober 1988 in Abhängigkeit vom Wettergeschehen

Die Auswirkungen des milden Winters 1988/89 auf die chemischen und biologischen Prozesse in der Nordsee werden von Fachleuten, aber auch von Politikern und der Presse lebhaft diskutiert. Schon im März wurden Befürchtungen geäußert, eine ähnliche kräftige und eventuell für andere marine Lebewesen schädigende Planktonblüte wie im Vorjahr stünde bevor. Dazu kam es jedoch nicht. Für das Vorjahresereignis wird diskutiert, ob als Grund ein Zusammenwirken von anomaler Zirkulation, kräftiger Frühjahrserwärmung, erhöhtem Festlandabfluß und damit verbundener kräftiger Nährstoffzufuhr in Frage kommt. Eine mögliche Erklärung für die diesjährige "normale" Planktonblüte wäre: Es lag zwar durchaus wieder eine ausgeprägte Zirkulationsanomalie in der Nordsee vor, jedoch fehlte die übermäßige "Düngung" durch Festlandabfluß, da es im vergangenen Frühjahrzu wenig Niederschläge gegeben hatte. Von einer "ganz normalen" Planktonblüte kann man in diesem Jahr allerdings auch nicht sprechen. Das erhöhte winterliche Temperaturniveau ließ einige Planktonarten sich bereits im Februar, also sehr früh, kräftig vermehren.

How far from Jerusalem? Tropical customs and the question of race in the Book of John Mandeville

The Book of John Mandeville, while ostensibly a pilgrimage guide documenting an English knight’s journey into the East, is an ideal text in which to study the developing concept of race in the European Middle Ages. The Mandeville-author’s sense of place and morality are inextricably linked to each other: Jerusalem is the center of his world, which necessarily forces Africa and Asia to occupy the spiritual periphery. Most inhabitants of Mandeville’s landscapes are not monsters in the physical sense, but at once startlingly human and irreconcilably alien in their customs. Their religious heresies, disordered sexual appetites, and monstrous acts of cannibalism label them as fallen state of the European Christian self. Mandeville’s monstrosities lie not in the fantastical, but the disturbingly familiar, coupling recognizable humans with a miscarriage of natural law. In using real people to illustrate the moral degeneracy of the tropics, Mandeville’s ethnography helps shed light on the missing link between medieval monsters and modern race theory.