Faster Algorithms for Incremental Topological Ordering.Robert Tarjan

We present two online algorithms for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm takes O(m 1/2) amortized time per arc and our second algorithm takes O(n 2.5/m) amortized time per arc, where n is the number of vertices and m is the total number of arcs. For sparse graphs, our O(m 1/2) bound improves the best previous bound by a factor of logn and is tight to within a constant factor for a natural class of algorithms that includes all the existing ones. Our main insight is that the two-way search method of previous algorithms does not require an ordered search, but can be more general, allowing us to avoid the use of heaps (priority queues). Instead, the deterministic version of our algorithm uses (approximate) median-finding; the randomized version of our algorithm uses uniform random sampling. For dense graphs, our O(n 2.5/m) bound improves the best previously published bound by a factor of n 1/4 and a recent bound obtained independently of our work by a factor of logn. Our main insight is that graph search is wasteful when the graph is dense and can be avoided by searching the topological order space instead. Our algorithms extend to the maintenance of strong components, in the same asymptotic time bounds.

Provider-Customer Coalitional Games

Efficacy of commercial wireless networks can be substantially enhanced through large-scale cooperation among involved entities such as providers and customers. The success of such cooperation is contingent upon the design of judicious resource allocation strategies that ensure that the individuals' payoffs are commensurate to the resources they offer to the coalition. The resource allocation strategies depend on which entities are decision-makers and whether and how they share their aggregate payoffs. Initially, we consider the scenario where the providers are the only decision-makers and they do not share their payoffs. We formulate the resource allocation problem as a nontransferable payoff coalitional game and show that there exists a cooperation strategy that leaves no incentive for any subset of providers to split from the grand coalition, i.e., the core of the game is nonempty. To compute this cooperation strategy and the corresponding payoffs, we subsequently relate this game and its core to an exchange market setting and its equilibrium, which can be computed by several efficient algorithms. Next, we investigate cooperation when customers are also decision-makers and decide which provider to subscribe to based on whether there is cooperation. We formulate a coalitional game in this setting and show that it has a nonempty core. Finally, we extend the formulations and results to the cases where the payoffs are vectors and can be shared selectively.

Spin-polarized STM spectra of Dirac electrons on the surface of a topological insulator

We provide a theory for the tunneling conductance G(V) of Dirac electrons on the surface of a topological insulator as measured by a spin-polarized scanning tunneling microscope tip for low-bias voltages V. We show that if the in-plane rotational symmetry on the surface of the topological insulator is broken by an external field that does not couple to spin directly (such as an in-plane electric field), G(V) exhibits an unconventional dependence on the direction of the magnetization of the tip, i.e., it acquires a dependence on the azimuthal angle of the magnetization of the tip. We also show that G(V) can be used to measure the magnitude of the local out-of-plane spin orientation of the Dirac electrons on the surface. We explain the role of the Dirac electrons in this unconventional behavior and suggest experiments to test our theory.

Charge Density Analysis of a Pentaborate Ion in an Ammonium Borate: Toward the Understanding of Topological Features in Borate Minerals

Structural and charge density distribution studies have been carried out on a single crystal data of an ammonium borate, [C(10)H(26)N(4)][B(5)O(6)(OH)(4)](2), synthesized by solvothermal method. Further, the experimentally observed geometry is used for the theoretical charge density calculations using the B3LYP/6-31G** level of theory, and the results are compared with the experimental values. Topological analysis of charge density based on the Atoms in Molecules approach for B-O bonds exhibit mixed covalent/ionic character. Detailed analysis of the hydrogen bonds in the crystal structure in the ammonium borate provides insights into the understanding of the reaction pathways that net atomic charges and electrostatic potential isosurfaces also give additional such systems. could result in the formation of borate minerals. The input to evaluate chemical and physical properties in such systems.

Topological analysis of general linear networks

A new method of network analysis, a generalization in several different senses of existing methods and applicable to all networks for which a branch-admittance (or impedance) matrix can be formed, is presented. The treatment of network determinants is very general and essentially four terminal rather than three terminal, and leads to simple expressions based on trees of a simple graph associated with the network and matrix, and involving products of low-order, usually(2 times 2)determinants of tree-branch admittances, in addition to tree-branch products as in existing methods. By comparison with existing methods, the total number of trees and of tree pairs is usually considerably reduced, and this fact, together with an easy method of tree-pair sign determination which is also presented, makes the new method simpler in general. The method can be very easily adapted, by the use of infinite parameters, to accommodate ideal transformers, operational amplifiers, and other forms of network constraint; in fact, is thought to be applicable to all linear networks.

Raman signatures of pressure induced electronic topological and structural transitions in Bi2Te3

We report Raman signatures of electronic topological transition (ETT) at 3.6 GPa and rhombohedral (alpha-Bi2Te3) to monoclinic (beta-Bi2Te3) structural transition at similar to 8 GPa. At the onset of ETT, a new Raman mode appears near 107 cm(-1) which is dispersionless with pressure. The structural transition at similar to 8 GPa is marked by a change in pressure derivative of A(1g) and E-g mode frequencies as well as by appearance of new modes near 115 cm(-1) and 135 cm(-1). The mode Grilneisen parameters are determined in both the alpha and beta-phases. (C) 2011 Elsevier Ltd. All rights reserved.

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m(3/2)) time. For sparse graphs (m/n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(n(5/2)) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Omega(n(2)2 root(2lgn)) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Theta (n(2) log n) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

Junction between surfaces of two topological insulators

We study the properties of a line junction which separates the surfaces of two three-dimensional topological insulators. The velocities of the Dirac electrons on the two surfaces may be unequal and may even have opposite signs. For a time-reversal invariant system, we show that the line junction is characterized by an arbitrary parameter alpha which determines the scattering from the junction. If the surface velocities have the same sign, we show that there can be edge states which propagate along the line junction with a velocity and spin orientation which depend on alpha and the ratio of the velocities. Next, we study what happens if the two surfaces are at an angle phi with respect to each other. We study the scattering and differential conductance through the line junction as functions of phi and alpha. We also find that there are edge states which propagate along the line junction with a velocity and spin orientation which depend on phi. Finally, if the surface velocities have opposite signs, we find that the electrons must transmit into the two-dimensional interface separating the two topological insulators.

Synchronous and asynchronous Mott transitions in topological insulator ribbons

We address how the nature of linearly dispersing edge states of two-dimensional (2D) topological insulators evolves with increasing electron-electron correlation engendered by a Hubbard-like on-site repulsion U in finite ribbons of two models of topological band insulators. Using an inhomogeneous cluster slave-rotor mean-field method developed here, we show that electronic correlations drive the topologically nontrivial phase into a Mott insulating phase via two different routes. In a synchronous transition, the entire ribbon attains a Mott insulating state at one critical U that depends weakly on the width of the ribbon. In the second, asynchronous route, Mott localization first occurs on the edge layers at a smaller critical value of electronic interaction, which then propagates into the bulk as U is further increased until all layers of the ribbon become Mott localized. We show that the kind of Mott transition that takes place is determined by certain properties of the linearly dispersing edge states which characterize the topological resilience to Mott localization.

Zero-Sum Risk-Sensitive Stochastic Differential Games

We study zero-sum risk-sensitive stochastic differential games on the infinite horizon with discounted and ergodic payoff criteria. Under certain assumptions, we establish the existence of values and saddle-point equilibria. We obtain our results by studying the corresponding Hamilton-Jacobi-Isaacs equations. Finally, we show that the value of the ergodic payoff criterion is a constant multiple of the maximal eigenvalue of the generators of the associated nonlinear semigroups.

Existence of Value in Stochastic Differential Games of Mixed Type

In this article, we address stochastic differential games of mixed type with both control and stopping times. Under standard assumptions, we show that the value of the game can be characterized as the unique viscosity solution of corresponding Hamilton-Jacobi-Isaacs (HJI) variational inequalities.

Continuum theory of edge states of topological insulators: variational principle and boundary conditions

We develop a continuum theory to model low energy excitations of a generic four-band time reversal invariant electronic system with boundaries. We propose a variational energy functional for the wavefunctions which allows us to derive natural boundary conditions valid for such systems. Our formulation is particularly suited for developing a continuum theory of the protected edge/surface excitations of topological insulators both in two and three dimensions. By a detailed comparison of our analytical formulation with tight binding calculations of ribbons of topological insulators modelled by the Bernevig-Hughes-Zhang (BHZ) Hamiltonian, we show that the continuum theory with a natural boundary condition provides an appropriate description of the low energy physics.

Topological electron density analysis and electrostatic properties of aspirin: an experimental and theoretical study

The topological and the electrostatic properties of the aspirin drug molecule were determined from high-resolution X-ray diffraction data at 90 K, and the corresponding results are compared with the theoretical calculations. The electron density at the bond critical point of all chemical bonds induding the intermolecular interactions of aspirin has been quantitatively described using Bader's quantum theory of ``Atoms in Molecules''. The electrostatic potential of the molecule emphasizes the preferable binding sites of the drug and the interaction features of the molecule, which are crucial for drug-receptor recognition. The topological analysis of hydrogen bonds reveals the strength of intermolecular interactions.

General-sum stochastic games: Verifiability conditions for Nash equilibria

Unlike zero-sum stochastic games, a difficult problem in general-sum stochastic games is to obtain verifiable conditions for Nash equilibria. We show in this paper that by splitting an associated non-linear optimization problem into several sub-problems, characterization of Nash equilibria in a general-sum discounted stochastic games is possible. Using the aforementioned sub-problems, we in fact derive a set of necessary and sufficient verifiable conditions (termed KKT-SP conditions) for a strategy-pair to result in Nash equilibrium. Also, we show that any algorithm which tracks the zero of the gradient of the Lagrangian of every sub-problem provides a Nash strategy-pair. (c) 2012 Elsevier Ltd. All rights reserved.