On the cubicity of bipartite graphs

A unit cube in k-dimension (or a k-cube) is defined as the Cartesian product R-1 x R-2 x ... x R-k, where each R-i is a closed interval on the real line of the form [a(j), a(i), + 1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph. It is known that for graph G, cub(G) <= left perpendicular2n/3right perpendicular. Recently it has been shown that for a graph G, cub(G) >= 4(Delta + 1) In n, where n and Delta are the number of vertices and maximum degree of G, respectively. In this paper, we show that for a bipartite graph G = (A boolean OR B, E) with |A| = n(1), |B| = n2, n(1) <= n(2), and Delta' = min {Delta(A),Delta(B)}, where Delta(A) = max(a is an element of A)d(a) and Delta(B) = max(b is an element of B) d(b), d(a) and d(b) being the degree of a and b in G, respectively , cub(G) <= 2(Delta' + 2) bar left rightln n(2)bar left arrow. We also give an efficient randomized algorithm to construct the cube representation of G in 3 (Delta' + 2) bar right arrowIn n(2)bar left arrow dimension. The reader may note that in general Delta' can be much smaller than Delta.

An eigenproblem approach to classical screw theory

This paper presents a novel algebraic formulation of the central problem of screw theory, namely the determination of the principal screws of a given system. Using the algebra of dual numbers, it shows that the principal screws can be determined via the solution of a generalised eigenproblem of two real, symmetric matrices. This approach allows the study of the principal screws of the general two-, three-systems associated with a manipulator of arbitrary geometry in terms of closed-form expressions of its architecture and configuration parameters. We also present novel methods for the determination of the principal screws for four-, five-systems which do not require the explicit computation of the reciprocal systems. Principal screws of the systems of different orders are identified from one uniform criterion, namely that the pitches of the principal screws are the extreme values of the pitch.The classical results of screw theory, namely the equations for the cylindroid and the pitch-hyperboloid associated with the two-and three-systems, respectively have been derived within the proposed framework. Algebraic conditions have been derived for some of the special screw systems. The formulation is also illustrated with several examples including two spatial manipulators of serial and parallel architecture, respectively.

An upper bound for Cubicity in terms of Boxicity

An axis-parallel b-dimensional box is a Cartesian product R-1 x R-2 x ... x R-b where each R-i (for 1 <= i <= b) is a closed interval of the form [a(i), b(i)] on the real line. The boxicity of any graph G, box(G) is the minimum positive integer b such that G can be represented as the intersection graph of axis-parallel b-dimensional boxes. A b-dimensional cube is a Cartesian product R-1 x R-2 x ... x R-b, where each R-i (for 1 <= i <= b) is a closed interval of the form [a(i), a(i) + 1] on the real line. When the boxes are restricted to be axis-parallel cubes in b-dimension, the minimum dimension b required to represent the graph is called the cubicity of the graph (denoted by cub(G)). In this paper we prove that cub(G) <= inverted right perpendicularlog(2) ninverted left perpendicular box(G), where n is the number of vertices in the graph. We also show that this upper bound is tight.Some immediate consequences of the above result are listed below: 1. Planar graphs have cubicity at most 3inverted right perpendicularlog(2) ninvereted left perpendicular.2. Outer planar graphs have cubicity at most 2inverted right perpendicularlog(2) ninverted left perpendicular.3. Any graph of treewidth tw has cubicity at most (tw + 2) inverted right perpendicularlog(2) ninverted left perpendicular. Thus, chordal graphs have cubicity at most (omega + 1) inverted right erpendicularlog(2) ninverted left perpendicular and circular arc graphs have cubicity at most (2 omega + 1)inverted right perpendicularlog(2) ninverted left perpendicular, where omega is the clique number.

Cultural-Evolution of Ecological Prudence

Animals often behave in a profligate fashion and decimate the populations of plants and animals they depend upon. They may, however, evolve prudent behaviour under special conditions, namely when such prudence greatly enhances the success of populations that are not too prone to invasions by profligate individuals. Cultural evolution in human societies can also lead to the adoption of prudent practices under similar conditions. These are more likely to be realized in stable environments in which the human populations tend to grow close to the carrying capacity, when the human groups are closed, and when the technology is stagnant. These conditions probably prevailed in the hunter—gatherer societies of the tropics and subtropics, and led to the adoption of a number of socially imposed restraints on the use of plant and animal resources. Such practices were rationalized in the form of Nature-worship. The Indian caste society became so organized as to fulfill these conditions, and gave rise to two religions, Buddhism and Jainism, which emphasize compassion towards all forms of life. The pastoral nomads of the middle east, on the other hand, lived in an environment which militated against prudence, and these societies gave rise to religions like Christianity, which declared war on nature. As the ruling elite and state have grown in power, they have tried to wrest control of natural resources from the local communities. This has sometimes resulted in conservation and prudent use under guidance from the state, but has often led to conflicts with local populations to the detriment of prudent behaviour. Modern technological progress has also often removed the need for conservation, as when availability of coal permitted the deforestation of England. While modern scientific understanding has led to a better appreciation of the need for prudence, the prevailing social and economic conditions often militate against any implementation of the understanding, as is seen from the history of whaling. However, the imperative for survival of the poor from the Third-World countries may finally bring about conditions in which ecological prudence may once again come to dominate human cultures as it might once have done with stable societies of hunter—gatherers.

Cubicity, boxicity, and vertex cover

A k-dimensional box is the cartesian product R-1 x R-2 x ... x R-k where each R-i is a closed interval on the real line. The boxicity of a graph G,denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the cartesian product R-1 x R-2 x ... x R-k where each Ri is a closed interval on the real line of the form [a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. In this paper we show that cub(G) <= t + inverted right perpendicularlog(n - t)inverted left perpendicular - 1 and box(G) <= left perpendiculart/2right perpendicular + 1, where t is the cardinality of a minimum vertex cover of G and n is the number of vertices of G. We also show the tightness of these upper bounds. F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph G, box(G) <= left perpendicularn/2right perpendicular and cub(G) <= inverted right perpendicular2n/3inverted left perpendicular, where n is the number of vertices of G, and these bounds are tight. We show that if G is a bipartite graph then box(G) <= inverted right perpendicularn/4inverted left perpendicular and this bound is tight. We also show that if G is a bipartite graph then cub(G) <= n/2 + inverted right perpendicularlog n inverted left perpendicular - 1. We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to n/4. Interestingly, if boxicity is very close to n/2, then chromatic number also has to be very high. In particular, we show that if box(G) = n/2 - s, s >= 0, then chi (G) >= n/2s+2, where chi (G) is the chromatic number of G.

Effect of a magnetic field on the flow and blood oxygenation in channels of variable cross-section

The effect of a magnetic field on the flow and oxygenation of an incompressible Newtonian conducting fluid in channels with irregular boundaries has been investigated. The geometric parameter δ, which is a ratio of the mean half width of the channel d to the characteristic length λ along the channel over which the significant changes in the flow quantities occur, has been used for perturbing the governing equations. Closed form solutions of the various order equations are presented for the stream function. The equations for oxygen partial pressure remain nonlinear even after perturbation, therefore a numerical solution is presented. The expressions for shear stress at a wall and pressure distributions are derived. Here the separation in the flow occurs at a higher Reynolds number than the corresponding non-magnetic case. It is found that the magnetic field has an effect on local oxygen concentration but has a little effect on the saturation length.

On The Topology Of Manifolds With Positive Isotropic Curvature

We show that a closed orientable Riemannian n-manifold, n >= 5, with positive isotropic curvature and free fundamental group is homeomorphic to the connected sum of copies of Sn-1 x S-1.

SIR Analysis and Interference Cancellation in Uplink OFDMA with Large Carrier Frequency/Timing Offsets

In uplink orthogonal frequency division multiple access (OFDMA), large timing offsets (TO) and/or carrier frequency offsets (CFO) of other users with respect to a desired user can cause significant multiuser interference (MUI). In this letter, we analytically characterize the degradation in the average output signal-to-interference ratio (SIR) due to the combined effect of both TOs as well as CFOs in uplink OFDMA. Specifically, we derive closed-form expressions for the average SIR at the DFT output in the presence of large CFOs and TOs. The analyticalexpressions derived for the signal and various interference terms at the DFT output are used to devise an interference cancelling receiver to mitigate the effect of CFO/TO-induced interferences.

A Current Source Inverter Fed Induction Motor Drive with Power Factor Angle Control Using Microprocessor

This paper describes a method of adjusting the stator power factor angle for the control of an induction motor fed from a current source inverter (CSI) based on the concept of space vectors (or park vectors). It is shown that under steady state, if the torque angle is kept constant over the entire operating range, it has the advantage of keeping the slip frequency constant. This can be utilized to dispose of the speed feedback and simplify the control scheme for the drive, such that the stator voltage integral zero crossings alone can be used as a feedback for deciding the triggering instants of the CSI thyristors under stable operation of the system. A closed-loop control strategy is developed for the drive based on this principle, using a microprocessor-based control system and is implemented on a laboratory prototype CSI fed induction motor drive.

Theoretical description of time-resolved pump/probe photoemission in TaS2: a single-band DFT+DMFT(NRG) study within the quasiequilibrium approximation

In this work, we theoretically examine recent pump/probe photoemission experiments on the strongly correlated charge-density-wave insulator TaS2.We describe the general nonequilibrium many-body formulation of time-resolved photoemission in the sudden approximation, and then solve the problem using dynamical mean-field theory with the numerical renormalization group and a bare density of states calculated from density functional theory including the charge-density-wave distortion of the ion cores and spin-orbit coupling. We find a number of interesting results: (i) the bare band structure actually has more dispersion in the perpendicular direction than in the two-dimensional planes; (ii) the DMFT approach can produce upper and lower Hubbard bands that resemble those in the experiment, but the upper bands will overlap in energy with other higher energy bands; (iii) the effect of the finite width of the probe pulse is minimal on the shape of the photoemission spectra; and (iv) the quasiequilibrium approximation does not fully describe the behavior in this system.

Structural Basis of Drug Resistance by Genetic Variants of HIV Type 1 Clade C Protease from India

Using computer modeling of three-dimensional structures and structural information available on the crystal structures of HIV-1 protease, we investigated the structural effects of mutations, in treatment-naive and treatment-exposed individuals from India and postulated mechanisms of resistance in clade C variants. A large number of models (14) have been generated by computational mutation of the available crystal structures of drug bound proteases. Localized energy minimization was carried out in and around the sites of mutation in order to optimize the geometry of interactions present. Most of the mutations result in structural differences at the flap that favors the semiopen state of the enzyme. Some of the mutations were also found to confer resistance by affecting the geometry of the active site. The E35D mutation affects the flap structure in clade B strains and E35N and E35K mutation, seen in our modeled strains, have a more profound effect. Common polymorphisms at positions 36 and 63 in clade C also affected flap structure. Apart from a few other residues Gln-58, Asn-83, Asn-88, and Gln-92 and their interactions are important for the transition from the closed to the open state. Development of protease inhibitors by structure-based design requires investigation of mechanisms operative for clade C to improve the efficacy of therapy.