Efficient algorithms for computing Reeb graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our algorithm maintains connected components of the two dimensional levels sets as a dynamic graph and constructs the Reeb graph in O(nlogn+nlogg(loglogg)3) time, where n is the number of triangles in the tetrahedral mesh representing the 3-manifold and g is the maximum genus over all level sets of the function. We extend this algorithm to construct Reeb graphs of d-manifolds in O(nlogn(loglogn)3) time, where n is the number of triangles in the simplicial complex that represents the d-manifold. Our result is a significant improvement over the previously known O(n2) algorithm. Finally, we present experimental results of our implementation and demonstrate that our algorithm for 3-manifolds performs efficiently in practice.

Hydrodynamics from the D1-brane

We study the hydrodynamic properties of strongly coupled SU(N) Yang-Mills theory of the D1-brane at finite temperature in the framework of gauge/gravity duality. The only non-trivial viscous transport coefficient in 1+1 dimensions is the bulk viscosity. We evaluate the bulk viscosity by isolating the quasi-normal mode corresponding to the sound channel for the gravitational background of the D1-brane. We find that the ratio of the bulk viscosity to the entropy density to be 1/4 pi. This ratio continues to be 1/4 pi also in the regime when the D1-brane Yang-Mills theory is dual to the gravitational background of the fundamental string. Our analysis shows that this ratio is equal to 1/4 pi for a class of gravitational backgrounds dual to field theories in 1+1 dimensions obtained by considering D1-branes at cones over Sasaki-Einstein 7-manifolds.

Uniqueness of Walkup's 9-vertex 3-dimensional Klein bottle

Via a computer search, Altshuler and Steinberg found that there are 1296+1 combinatorial 3-manifolds on nine vertices, of which only one is non-sphere. This exceptional 3-manifold View the MathML source triangulates the twisted S2-bundle over S1. It was first constructed by Walkup. In this paper, we present a computer-free proof of the uniqueness of this non-sphere combinatorial 3-manifold. As opposed to the computer-generated proof, ours does not require wading through all the 9-vertex 3-spheres. As a preliminary result, we also show that any 9-vertex combinatorial 3-manifold is equivalent by proper bistellar moves to a 9-vertex neighbourly 3-manifold.

Constructing Reeb Graphs using Cylinder Maps

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. In this video, we describe a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Arcs in the Reeb graph are computed in the second step using a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The algorithm is also able to handle non-manifold domains.

Approximate VB-MO schemes for excitation gaps in Hubbard models

The excitation gaps in the singlet and triplet manifolds for finite Hubbard models in one, two and three dimensions have been obtained using different approximate configuration interaction (CI) schemes, as a function of the correlation strength, by using valence bond (VB) functions constructed over the molecular orbital (MO) basis. These are compared with numerically exact results and it is found that the scheme in which all particle hole excitations below a given threshold are included is the method of choice. The excitation energies are well reproduced, in trend as well as magnitude, particularly when the threshold equals the bandwidth of the corresponding noninteracting system.

Excitation and relaxation energies of trans-stilbene: Confined singlet, triplet, and charged bipolarons

The π-electronic excitations and excited-state geometries of trans-stilbene (tS) are found by combining exact solutions of the Pariser-Parr-Pople (PPP) model and semiempirical Parametric Method 3 (PM3) calculations. Comprehensive comparisons with tS spectra are obtained and related to the fluorescence and topological alternation of poly(paraphenylenevinylene) (PPV). The one-photon absorption and triplet of tS correspond, respectively, to singlet and triplet bipolarons confined to two phenyls, while the tS2- ground state is a confined charged bipolaron. Independent estimates of the relaxation energy between vertical and adiabatic excitation show the bipolaron binding energy to depend on both charge and spin, as expected for interacting π electrons in correlated or molecular states. Complete configuration interaction within the PPP model of tS accounts for the singlet-triplet gap, for the fine-structure constants and triplet-triplet spectra, for two-photon transitions and intensities, and for one-photon spectra and the radiative lifetime, although the relative position of nearly degenerate covalent and ionic singlets is not resolved. The planar PM3 geometry and low rotational barrier of tS agree with resolved rotational and vibrational spectra in molecular beams. PM3 excitation and relaxation energies for tS bipolarons are consistent with experiment and with PPP results. Instead of the exciton model, we interpret tS excitations in terms of states that are localized on each ring or extended over an alternating chain, as found exactly in Hückel theory, and find nearly degenerate transitions between extended and localized states in the singlet, triplet, and dianion manifolds. The large topological alternation of the extended system increases the ionicity and interchanges the order of the lowest one- and two-photon absorption of PPV relative to polyenes.

Nonlinear dynamics of a rigid block on a rigid base

The planar rocking of a prismatic rectangular rigid block about either of its corners is considered. The problem of homoclinic intersections of the stable and unstable manifolds of the perturbed separatrix is addressed to and the corresponding Melnikov functions are derived. Inclusion of the vertical forcing in the Hamiltonian permits the construction of a three-dimensional separatrix. The corresponding modified Melnikov function of Wiggins for homoclinic intersections is derived. Further, the 1-period symmetric orbits are predicted analytically using the method of averaging and compared with the simulation results. The stability boundary for such orbits is also established.

On Walkup's class K (d) and a minimal triangulation of (S-3 (sic) S-1)(#3)

For d >= 2, Walkup's class K (d) consists of the d-dimensional simplicial complexes all whose vertex-links are stacked (d - 1)-spheres. Kalai showed that for d >= 4, all connected members of K (d) are obtained from stacked d-spheres by finitely many elementary handle additions. According to a result of Walkup, the face vector of any triangulated 4-manifold X with Euler characteristic chi satisfies f(1) >= 5f(0) - 15/2 chi, with equality only for X is an element of K(4). Kuhnel observed that this implies f(0)(f(0) - 11) >= -15 chi, with equality only for 2-neighborly members of K(4). Kuhnel also asked if there is a triangulated 4-manifold with f(0) = 15, chi = -4 (attaining equality in his lower bound). In this paper, guided by Kalai's theorem, we show that indeed there is such a triangulation. It triangulates the connected sum of three copies of the twisted sphere product S-3 (sic) S-1. Because of Kuhnel's inequality, the given triangulation of this manifold is a vertex-minimal triangulation. By a recent result of Effenberger, the triangulation constructed here is tight. Apart from the neighborly 2-manifolds and the infinite family of (2d + 3)-vertex sphere products Sd-1 X S-1 (twisted for d odd), only fourteen tight triangulated manifolds were known so far. The present construction yields a new member of this sporadic family. We also present a self-contained proof of Kalai's result. (C) 2011 Elsevier B.V. All rights reserved.

Two dimensional weak pseudomanifolds on seven vertices

In this article we have explicitly determined all the 2-dimensional weak pseudomanifolds on 7 vertices. We have proved that there are (up to isomorphism) 13 such weak pseudomanifolds. The geometric carriers of them are 6 topological spaces, three of which are not manifolds.

Anomalous temperature dependence of phonons and photoluminescence bands in pyrochlore Er(2)Ti(2)O(7): signatures of structural deformation at 130 K

We report a Raman study of single crystal pyrochlore Er(2)Ti(2)O(7) as a function of temperature from 12 to 300 K. In addition to the phonons, various photoluminescence (PL) lines of Er(3+) in the visible range are also observed. Our Raman data show an anomalous red-shift of two phonons (one at similar to 200 cm(-1) and another at similar to 520 cm(-1)) upon cooling from room temperature which is attributed to phonon-phonon anharmonic interactions. However, the phonons at similar to 310, 330, and 690 cm(-1) initially show a blue-shift upon cooling from room temperature down to about 130 K, followed by a red-shift, indicating a structural deformation at similar to 130 K. The intensities of the PL bands associated with the transitions between the various levels of the ground state manifold ((4)I(15/2)) and the (2)H(11/2) as well as (4)S(3/2) excited state manifolds of Er(3+) show a change at similar to 130 K. Moreover, the temperature dependence of the peak position of the two PL bands shows a change in their slope (d(omega)/d(T)) at similar to 130 K, thus further strengthening the proposal of a structural deformation. The temperature dependence of the peak positions of the PL bands has been analyzed using the theory of optical dephasing in crystals.

Output-Sensitive Construction of Reeb Graphs

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. This paper describes a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds or non-manifolds in any dimension. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Critical points correspond to nodes in the Reeb graph. Arcs connecting the nodes are computed in the second step by a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The paper also describes a scheme for controlled simplification of the Reeb graph and two different graph layout schemes that help in the effective presentation of Reeb graphs for visual analysis of scalar fields. Finally, the Reeb graph is employed in four different applications-surface segmentation, spatially-aware transfer function design, visualization of interval volumes, and interactive exploration of time-varying data.

Minimal triangulation, complementarity and projective planes

Brehm and Kuhnel proved that if M-d is a combinatorial d-manifold with 3d/2 + 3 vertices and \ M-d \ is not homeomorphic to Sd then the combinatorial Morse number of M-d is three and hence d is an element of {0, 2, 4, 8, 16} and \ M-d \ is a manifold like a projective plane in the sense of Eells and Kuiper. We discuss the existence and uniqueness of such combinatorial manifolds. We also present the following result: ''Let M-n(d) be a combinatorial d-manifold with n vertices. M-n(d) satisfies complementarity if and only if d is an element of {0, 2, 4, 8, 16} with n = 3d/2 + 3 and \ M-n(d) \ is a manifold like a projective plane''.

Badly approximable numbers and vectors in Cantor-like sets

We show that a large class of Cantor-like sets of R-d, d >= 1, contains uncountably many badly approximable numbers, respectively badly approximable vectors, when d >= 2. An analogous result is also proved for subsets of R-d arising in the study of geodesic flows corresponding to (d+1)-dimensional manifolds of constant negative curvature and finite volume, generalizing the set of badly approximable numbers in R. Furthermore, we describe a condition on sets, which is fulfilled by a large class, ensuring a large intersection with these Cantor-like sets.

Computing Reeb Graphs as a Union of Contour Trees

The Reeb graph of a scalar function tracks the evolution of the topology of its level sets. This paper describes a fast algorithm to compute the Reeb graph of a piecewise-linear (PL) function defined over manifolds and non-manifolds. The key idea in the proposed approach is to maximally leverage the efficient contour tree algorithm to compute the Reeb graph. The algorithm proceeds by dividing the input into a set of subvolumes that have loop-free Reeb graphs using the join tree of the scalar function and computes the Reeb graph by combining the contour trees of all the subvolumes. Since the key ingredient of this method is a series of union-find operations, the algorithm is fast in practice. Experimental results demonstrate that it outperforms current generic algorithms by a factor of up to two orders of magnitude, and has a performance on par with algorithms that are catered to restricted classes of input. The algorithm also extends to handle large data that do not fit in memory.

On Wilking's criterion for the Ricci flow

Wilking has recently shown that one can associate a Ricci flow invariant cone of curvature operators , which are nonnegative in a suitable sense, to every invariant subset . In this article we show that if is an invariant subset of such that is closed and denotes the cone of curvature operators which are positive in the appropriate sense then one of the two possibilities holds: (a) The connected sum of any two Riemannian manifolds with curvature operators in also admits a metric with curvature operator in (b) The normalized Ricci flow on any compact Riemannian manifold with curvature operator in converges to a metric of constant positive sectional curvature. We also point out that if is an arbitrary subset, then is contained in the cone of curvature operators with nonnegative isotropic curvature.