Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

Shape effect on optimal geometric conditions in surface aeration systems

The performance of surface aeration systems, among other key design variables, depends upon the geometric parameters of the aeration tank. Efficient performance and scale up or scale down of the experimental results of an aeration ystem requires optimal geometric conditions. Optimal conditions refer to the conditions of maximum oxygen transfer rate, which assists in scaling up or down the system for ommercial utilization. The present work investigates the effect of an aeration tank's shape (unbaffled circular, baffled circular and unbaffled square) on oxygen transfer. Present results demonstrate that there is no effect of shape on the optimal geometric conditions for rotor position and rotor dimensions. This experimentation shows that circular tanks (baffled or unbaffled) do not have optimal geometric conditions for liquid transfer, whereas the square cross-section tank shows a unique geometric shape to optimize oxygen transfer.

A geometric approach for determining inner and exterior boundaries of workspaces of planar manipulators

In this paper a method to determine the internal and external boundaries of planar workspaces, represented with an ordered set of points, is presented. The sequence of points are grouped and can be interpreted to form a sequence of curves. Three successive curves are used for determining the instantaneous center of rotation for the second one of them. The two extremal points on the curve with respect to the instantaneous center are recognized as singular points. The chronological ordering of these singular points is used to generate the two envelope curves, which are potentially intersecting. Methods have been presented in the paper for the determination of the workspace boundary from the envelope curves. Strategies to deal with the manipulators with joint limits and various degenerate situations have also been discussed. The computational steps being completely geometric, the method does not require the knowledge about the manipulator's kinematics. Hence, it can be used for the workspace of arbitrary planar manipulators. A number of illustrative examples demonstrate the efficacy of the proposed method.

A geometric approach to stationary defect solutions in one space dimension

In this manuscript, we consider the impact of a small jump-type spatial heterogeneity on the existence of stationary localized patterns in a system of partial dierential equations in one spatial dimension...

Capturability analysis of a geometric guidance law in relative velocity space

In this paper, a relative velocity approach is used to analyze the capturability of a geometric guidance law. Point mass models are assumed for both the missile and the target. The speeds of the missile and target are assumed to remain constant throughout the engagement. Lateral acceleration, obtained from the guidance law, is applied to change the path of the missile. The kinematic equations for engagements in the horizontal plane are derived in the relative velocity space. Some analytical results for the capture region are obtained for non-maneuvering and maneuvering targets. For non-maneuvering targets it is enough for the navigation gain to be a constant to intercept the target, while for maneuvering targets a time varying navigation gain is needed for interception. These results are then verified through numerical simulations.

Manifestation of geometric frustration on magnetic and thermodynamic properties of the pyrochlores Sm2X2O7 (X=Ti,Zr)

We present here magnetization, specific heat, and Raman studies on single-crystalline specimens of the first pyrochlore member Sm2Ti2O7 of the rare-earth titanate series. Its analogous compound Sm2Zr2O7 in the rare-earth zirconate series is also investigated in the polycrystalline form. The Sm spins in Sm2Ti2O7 remain unordered down to at least T=0.5 K. The absence of magnetic ordering is attributed to very small values of exchange (θcw∼−0.26 K) and dipolar interaction (μeff∼0.15 μB) between the Sm3+ spins in this pyrochlore. In contrast, the pyrochlore Sm2Zr2O7 is characterized by a relatively large value of Sm-Sm spin exchange (θcw∼−10 K); however, long-range ordering of the Sm3+ spins is not established at least down to T=0.67 K due to frustration of the Sm3+ spins on the pyrochlore lattice. The ground state of Sm3+ ions in both pyrochlores is a well-isolated Kramers doublet. The higher-lying crystal field excitations are observed in the low-frequency region of the Raman spectra of the two compounds recorded at T=10 K. At higher temperatures, the magnetic susceptibility of Sm2Ti2O7 shows a broad maximum at T=140 K, while that of Sm2Zr2O7 changes monotonically. Whereas Sm2Ti2O7 is a promising candidate for investigating spin fluctuations on a frustrated lattice, as indicated by our data, the properties of Sm2Zr2O7 seem to conform to a conventional scenario where geometrical frustration of the spin excludes their long-range ordering.

Topological properties of the one dimensional exponential random geometric graph

In this article we study the one-dimensional random geometric (random interval) graph when the location of the nodes are independent and exponentially distributed. We derive exact results and limit theorems for the connectivity and other properties associated with this random graph. We show that the asymptotic properties of a graph with a truncated exponential distribution can be obtained using the exponential random geometric graph. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008.

Asymmetric cross-coupled differential pair configuration to realize neuron activation function and its derivative

In this brief, we present a new circuit technique to generate the sigmoid neuron activation function (NAF) and its derivative (DNAF). The circuit makes use of transistor asymmetry in cross-coupled differential pair to obtain the derivative. The asymmetry is introduced through external control signal, as and when required. This results in the efficient utilization of the hard-ware by realizing NAF and DNAF using the same building blocks. The operation of the circuit is presented in the subthreshold region for ultra low-power applications. The proposed circuit has been experimentally prototyped and characterized as a proof of concept on the 1.5-mum AMI technology.

A Geometric Algorithm for Learning Oblique Decision Trees

In this paper we present a novel algorithm for learning oblique decision trees. Most of the current decision tree algorithms rely on impurity measures to assess goodness of hyperplanes at each node. These impurity measures do not properly capture the geometric structures in the data. Motivated by this, our algorithm uses a strategy, based on some recent variants of SVM, to assess the hyperplanes in such a way that the geometric structure in the data is taken into account. We show through empirical studies that our method is effective.

Geometric quantum computation using fictitious spin-1/2 subspaces of strongly dipolar coupled nuclear spins

Geometric phases have been used in NMR to implement controlled phase shift gates for quantum-information processing, only in weakly coupled systems in which the individual spins can be identified as qubits. In this work, we implement controlled phase shift gates in strongly coupled systems by using nonadiabatic geometric phases, obtained by evolving the magnetization of fictitious spin-1/2 subspaces, over a closed loop on the Bloch sphere. The dynamical phase accumulated during the evolution of the subspaces is refocused by a spin echo pulse sequence and by setting the delay of transition selective pulses such that the evolution under the homonuclear coupling makes a complete 2 pi rotation. A detailed theoretical explanation of nonadiabatic geometric phases in NMR is given by using single transition operators. Controlled phase shift gates, two qubit Deutsch-Jozsa algorithm, and parity algorithm in a qubit-qutrit system have been implemented in various strongly dipolar coupled systems obtained by orienting the molecules in liquid crystal media.

Influence of phosphate ligands in abolishing the conformational difference between ribonuclease A and its acid-denatured derivative

The initial structural alteration of RNAase A due to acid denaturation (0.5 N HCl, 30 degrees C) that accompanies deamidation (without altering enzymic activity) has been dectected by spectrophotometric titration, fluorescence and ORD/CD measurements. It is shown that acid treated RNAase A has an altered conformation at neutral pH, 25 degrees C. This is characterized by the increased accessibility of buried tyrosine residue(s) towards the solvent. The most altered conformation of RNAase A is found in the 10 h acid-treated derivative. This has about 1.5 additional exposed tyrosine residues and a lesser amount of secondary structure than RNAase A. All three methods (titration, fluorescence and CD) established that the structural transition of RNAase A is biphasic. The first phase occurs within 1 h and the resulting subtle conformational change is constant up to 7 h. Following this, after the release of 0.55 mol of ammonia, the major conformational change begins. The altered conformation of the acid-denatured RNAase A could be reversed completely to the native state through a conformational change induced by substrate analogs like 2'- or 3'-CMP. Thus the monodeamidated derivative isolated from the acid-denatured RNAase A by phosphate is very similar to RNAase A in over-all conformation. The results suggest the possibility of flexibility in the RNAase A molecule that does not affect its catalytic activity, as probed through the tyrosine residues.

Chemistry in Confined Spaces: High-Energy Conformer of a Piperidine Derivative is Favored Within a Water-Soluble Capsuleplex

Propyloxy-substituted piperidine in solution adopts a conformation in which its alkoxy group is equatorially positioned Surprisingly, two conformers of it that do not interconvert in the NMR time scale at room temperature have been found within an octa-acid capsule The serendipitous finding of the axial conformer of propyloxy-substituted piperidine within a supramolecular capsule highlights the value of confined spaces in physical organic chemistry.

Criticality of the exponential rate of decay for the largest nearest-neighbor link in random geometric graphs

Let n points be placed independently in d-dimensional space according to the density f(x) = A(d)e(-lambda parallel to x parallel to alpha), lambda, alpha > 0, x is an element of R-d, d >= 2. Let d(n) be the longest edge length of the nearest-neighbor graph on these points. We show that (lambda(-1) log n)(1-1/alpha) d(n) - b(n) converges weakly to the Gumbel distribution, where b(n) similar to ((d - 1)/lambda alpha) log log n. We also prove the following strong law for the normalized nearest-neighbor distance (d) over tilde (n) = (lambda(-1) log n)(1-1/alpha) d(n)/log log n: (d - 1)/alpha lambda <= lim inf(n ->infinity) (d) over tilde (n) <= lim sup(n ->infinity) (d) over tilde (n) <= d/alpha lambda almost surely. Thus, the exponential rate of decay alpha = 1 is critical, in the sense that, for alpha > 1, d(n) -> 0, whereas, for alpha <= 1, d(n) -> infinity almost surely as n -> infinity.