Minimal Triangulations of Manifolds

Finding vertex-minimal triangulations of closed manifolds is a very difficult problem. Except for spheres and two series of manifolds, vertex-minimal triangulations are known for only few manifolds of dimension more than 2 (see the table given at the end of Section 5). In this article, we present a brief survey on the works done in last 30 years on the following:(i) Finding the minimal number of vertices required to triangulate a given pl manifold. (ii) Given positive integers n and d, construction of n-vertex triangulations of different d-dimensional pl manifolds. (iii) Classifications of all the triangulations of a given pl manifold with same number of vertices.In Section 1, we have given all the definitions which are required for the remaining part of this article. A reader can start from Section 2 and come back to Section 1 as and when required. In Section 2, we have presented a very brief history of triangulations of manifolds. In Section 3,we have presented examples of several vertex-minimal triangulations. In Section 4, we have presented some interesting results on triangulations of manifolds. In particular, we have stated the Lower Bound Theorem and the Upper Bound Theorem. In Section 5, we have stated several results on minimal triangulations without proofs. Proofs are available in the references mentioned there. We have also presented some open problems/conjectures in Sections 3 and 5.

Minimal unsatisfiable sets: Classification and bounds

Proving the unsatisfiability of propositional Boolean formulas has applications in a wide range of fields. Minimal Unsatisfiable Sets (MUS) are signatures of the property of unsatisfiability in formulas and our understanding of these signatures can be very helpful in answering various algorithmic and structural questions relating to unsatisfiability. In this paper, we explore some combinatorial properties of MUS and use them to devise a classification scheme for MUS. We also derive bounds on the sizes of MUS in Horn, 2-SAT and 3-SAT formulas.

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''.

Geometric Decision Tree

In this paper, we present a new algorithm for learning oblique decision trees. Most of the current decision tree algorithms rely on impurity measures to assess the goodness of hyperplanes at each node while learning a decision tree in top-down fashion. These impurity measures do not properly capture the geometric structures in the data. Motivated by this, our algorithm uses a strategy for assessing the hyperplanes in such a way that the geometric structure in the data is taken into account. At each node of the decision tree, we find the clustering hyperplanes for both the classes and use their angle bisectors as the split rule at that node. We show through empirical studies that this idea leads to small decision trees and better performance. We also present some analysis to show that the angle bisectors of clustering hyperplanes that we use as the split rules at each node are solutions of an interesting optimization problem and hence argue that this is a principled method of learning a decision tree.

Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V (G) and edge set E(G). A k-dimensional box is a Cartesian product of closed intervals [a(1), b(1)] x [a(2), b(2)] x ... x [a(k), b(k)]. The boxicity of G, box(G), is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes; i.e., each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset, where S is the ground set and P is a reflexive, antisymmetric and transitive binary relation on S. The dimension of P, dim(P), is the minimum integer t such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P; i.e., S is the vertex set and two vertices are adjacent if and only if they are comparable in P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. It immediately follows that if P is a height-2 poset, then box(G(P)) <= dim(P) <= 2box(G(P)) since the underlying comparability graph of a height-2 poset is a bipartite graph. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with the extended double cover of G, denoted as G(c): Note that G(c) is a bipartite graph with partite sets A and B which are copies of V (G) such that, corresponding to every u is an element of V (G), there are two vertices u(A) is an element of A and u(B) is an element of B and {u(A), v(B)} is an edge in G(c) if and only if either u = v or u is adjacent to v in G. Let P(c) be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P(c)) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension such as dim(P) = 2 tree width (G(P)) + 4, since boxicity of any graph is known to be at most its tree width + 2. In the other direction, using the already known bounds for partial order dimension we get the following: (1) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta), which is an improvement over the best-known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-is an element of)) for any is an element of > 0 unless NP = ZPP.

Real-time monitoring of critical nodes with minimal number of Phasor Measurement Units

This paper presents a method for placement of Phasor Measurement Units, ensuring the monitoring of vulnerable buses which are obtained based on transient stability analysis of the overall system. Real-time monitoring of phase angles across different nodes, which indicates the proximity to instability, the very purpose will be well defined if the PMUs are placed at buses which are more vulnerable. The issue is to identify the key buses where the PMUs should be placed when the transient stability prediction is taken into account considering various disturbances. Integer Linear Programming technique with equality and inequality constraints is used to find out the optimal placement set with key buses identified from transient stability analysis. Results on IEEE-14 bus system are presented to illustrate the proposed approach.

3-MANIFOLD GROUPS, KÄHLER GROUPS AND COMPLEX SURFACES

Let G be a Kahler group admitting a short exact sequence 1 -> N -> G -> Q -> 1 where N is finitely generated. (i) Then Q cannot be non-nilpotent solvable. (ii) Suppose in addition that Q satisfies one of the following: (a) Q admits a discrete faithful non-elementary action on H-n for some n >= 2. (b) Q admits a discrete faithful non-elementary minimal action on a simplicial tree with more than two ends. (c) Q admits a (strong-stable) cut R such that the intersection of all conjugates of R is trivial. Then G is virtually a surface group. It follows that if Q is infinite, not virtually cyclic, and is the fundamental group of some closed 3-manifold, then Q contains as a finite index subgroup either a finite index subgroup of the three-dimensional Heisenberg group or the fundamental group of the Cartesian product of a closed oriented surface of positive genus and the circle. As a corollary, we obtain a new proof of a theorem of Dimca and Suciu in Which 3-manifold groups are Kahler groups? J. Eur. Math. Soc. 11 (2009) 521-528] by taking N to be the trivial group. If instead, G is the fundamental group of a compact complex surface, and N is finitely presented, then we show that Q must contain the fundamental group of a Seifert-fibered 3-manifold as a finite index subgroup, and G contains as a finite index subgroup the fundamental group of an elliptic fibration. We also give an example showing that the relation of quasi-isometry does not preserve Kahler groups. This gives a negative answer to a question of Gromov which asks whether Kahler groups can be characterized by their asymptotic geometry.

Minimal residual method provides optimal regularization parameter for diffuse optical tomography

The inverse problem in the diffuse optical tomography is known to be nonlinear, ill-posed, and sometimes under-determined, requiring regularization to obtain meaningful results, with Tikhonov-type regularization being the most popular one. The choice of this regularization parameter dictates the reconstructed optical image quality and is typically chosen empirically or based on prior experience. An automated method for optimal selection of regularization parameter that is based on regularized minimal residual method (MRM) is proposed and is compared with the traditional generalized cross-validation method. The results obtained using numerical and gelatin phantom data indicate that the MRM-based method is capable of providing the optimal regularization parameter. (C) 2012 Society of Photo-Optical Instrumentation Engineers (SPIE). DOI: 10.1117/1.JBO.17.10.106015]

Leptonic minimal flavour violation in warped extra dimensions

Lepton mass hierarchies and lepton flavour violation are revisited in the framework of Randall-Sundrum models. Models with Dirac-type as well as Majorana-type neutrinos are considered. The five-dimensional c-parameters are fit to the charged lepton and neutrino masses and mixings using chi(2) minimization. Leptonic flavour violation is shown to be large in these cases. Schemes of minimal flavour violation are considered for the cases of an effective LLHH operator and Dirac neutrinos and are shown to significantly reduce the limits from lepton flavour violation.

Scalable multi-dimensional user intent identification using tree structured distributions

The problem of identifying user intent has received considerable attention in recent years, particularly in the context of improving the search experience via query contextualization. Intent can be characterized by multiple dimensions, which are often not observed from query words alone. Accurate identification of Intent from query words remains a challenging problem primarily because it is extremely difficult to discover these dimensions. The problem is often significantly compounded due to lack of representative training sample. We present a generic, extensible framework for learning the multi-dimensional representation of user intent from the query words. The approach models the latent relationships between facets using tree structured distribution which leads to an efficient and convergent algorithm, FastQ, for identifying the multi-faceted intent of users based on just the query words. We also incorporated WordNet to extend the system capabilities to queries which contain words that do not appear in the training data. Empirical results show that FastQ yields accurate identification of intent when compared to a gold standard.

Delineation of seismic source zones based on seismicity parameters and probabilistic evaluation of seismic hazard using logic tree approach

The delineation of seismic source zones plays an important role in the evaluation of seismic hazard. In most of the studies the seismic source delineation is done based on geological features. In the present study, an attempt has been made to delineate seismic source zones in the study area (south India) based on the seismicity parameters. Seismicity parameters and the maximum probable earthquake for these source zones were evaluated and were used in the hazard evaluation. The probabilistic evaluation of seismic hazard for south India was carried out using a logic tree approach. Two different types of seismic sources, linear and areal, were considered in the present study to model the seismic sources in the region more precisely. In order to properly account for the attenuation characteristics of the region, three different attenuation relations were used with different weightage factors. Seismic hazard evaluation was done for the probability of exceedance (PE) of 10% and 2% in 50 years. The spatial variation of rock level peak horizontal acceleration (PHA) and spectral acceleration (Sa) values corresponding to return periods of 475 and 2500 years for the entire study area are presented in this work. The peak ground acceleration (PGA) values at ground surface level were estimated based on different NEHRP site classes by considering local site effects.

Scale-dependent relationships between tree species richness and ecosystem function in forests

1. The relationship between species richness and ecosystem function, as measured by productivity or biomass, is of long-standing theoretical and practical interest in ecology. This is especially true for forests, which represent a majority of global biomass, productivity and biodiversity. 2. Here, we conduct an analysis of relationships between tree species richness, biomass and productivity in 25 forest plots of area 8-50ha from across the world. The data were collected using standardized protocols, obviating the need to correct for methodological differences that plague many studies on this topic. 3. We found that at very small spatial grains (0.04ha) species richness was generally positively related to productivity and biomass within plots, with a doubling of species richness corresponding to an average 48% increase in productivity and 53% increase in biomass. At larger spatial grains (0.25ha, 1ha), results were mixed, with negative relationships becoming more common. The results were qualitatively similar but much weaker when we controlled for stem density: at the 0.04ha spatial grain, a doubling of species richness corresponded to a 5% increase in productivity and 7% increase in biomass. Productivity and biomass were themselves almost always positively related at all spatial grains. 4. Synthesis. This is the first cross-site study of the effect of tree species richness on forest biomass and productivity that systematically varies spatial grain within a controlled methodology. The scale-dependent results are consistent with theoretical models in which sampling effects and niche complementarity dominate at small scales, while environmental gradients drive patterns at large scales. Our study shows that the relationship of tree species richness with biomass and productivity changes qualitatively when moving from scales typical of forest surveys (0.04ha) to slightly larger scales (0.25 and 1ha). This needs to be recognized in forest conservation policy and management.

Minimal crystallizations of 3-manifolds

We have introduced the weight of a group which has a presentation with number of relations is at most the number of generators. We have shown that the number of facets of any contracted pseudotriangulation of a connected closed 3-manifold M is at least the weight of the fundamental group of M. This lower bound is sharp for the 3-manifolds RP3, L(3, 1), L(5, 2), S-1 x S-1 x S-1, S-2 x S-1, S-2 (x) under bar S-1 and S-3/Q(8), where Q(8) is the quaternion group. Moreover, there is a unique such facet minimal pseudotriangulation in each of these seven cases. We have also constructed contracted pseudotriangulations of L(kq - 1, q) with 4(q + k - 1) facets for q >= 3, k >= 2 and L(kq + 1, q) with 4(q + k) facets for q >= 4, k >= 1. By a recent result of Swartz, our pseudotriangulations of L(kg + 1, q) are facet minimal when kg + 1 are even. In 1979, Gagliardi found presentations of the fundamental group of a manifold M in terms of a contracted pseudotriangulation of M. Our construction is the converse of this, namely, given a presentation of the fundamental group of a 3-manifold M, we construct a contracted pseudotriangulation of M. So, our construction of a contracted pseudotriangulation of a 3-manifold M is based on a presentation of the fundamental group of M and it is computer-free.

Error analysis of discontinuous Galerkin methods for the Stokes problem under minimal regularity

In this article, we analyse several discontinuous Galerkin (DG) methods for the Stokes problem under minimal regularity on the solution. We assume that the velocity u belongs to H-0(1)(Omega)](d) and the pressure p is an element of L-0(2)(Omega). First, we analyse standard DG methods assuming that the right-hand side f belongs to H-1(Omega) boolean AND L-1(Omega)](d). A DG method that is well defined for f belonging to H-1(Omega)](d) is then investigated. The methods under study include stabilized DG methods using equal-order spaces and inf-sup stable ones where the pressure space is one polynomial degree less than the velocity space.

Temporal variability of forest communities: empirical estimates of population change in 4000 tree species

Long-term surveys of entire communities of species are needed to measure fluctuations in natural populations and elucidate the mechanisms driving population dynamics and community assembly. We analysed changes in abundance of over 4000 tree species in 12 forests across the world over periods of 6-28years. Abundance fluctuations in all forests are large and consistent with population dynamics models in which temporal environmental variance plays a central role. At some sites we identify clear environmental drivers, such as fire and drought, that could underlie these patterns, but at other sites there is a need for further research to identify drivers. In addition, cross-site comparisons showed that abundance fluctuations were smaller at species-rich sites, consistent with the idea that stable environmental conditions promote higher diversity. Much community ecology theory emphasises demographic variance and niche stabilisation; we encourage the development of theory in which temporal environmental variance plays a central role.