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.

First-Principles Study of the Effect of Organic Ligands on the Crystal Structure of CdS Nanoparticles

We show with the aid of first-principles electronic structure calculations that suitable choice of the capping ligands may be an important control parameter for crystal structure engineering of nanoparticles. Our calculations on CdS nanocrystals reveal that the binding energy of model trioctylphosphine molecules on the (001) facets of zincblende nanocrystals is larger compared to that on wurtzite facets. Similarly, the binding energy of model cis-oleic acid is found to be dominant for the (10 (1) over bar0) facets of wurtzite structure. As a consequence, trioctylphosphine as a capping agent stabilizes the zincblende structure while cis-oleic acid stabilizes the wurtzite phase by influencing the surface energy, which has a sizable contribution to the energetics of a nanocrystal. Our detailed analysis suggests that the binding of molecules on the nanocrystalline facets depends on the surface topology of the facets, the coordination of the surface atoms where the capping molecule is likely to attach, and the conformation of the capping molecule.

Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any arbitrary of nodes. However regenerating codes possess in addition, the ability to repair a failed node by connecting to any arbitrary nodes and downloading an amount of data that is typically far less than the size of the data file. This amount of download is termed the repair bandwidth. Minimum storage regenerating (MSR) codes are a subclass of regenerating codes that require the least amount of network storage; every such code is a maximum distance separable (MDS) code. Further, when a replacement node stores data identical to that in the failed node, the repair is termed as exact. The four principal results of the paper are (a) the explicit construction of a class of MDS codes for d = n - 1 >= 2k - 1 termed the MISER code, that achieves the cut-set bound on the repair bandwidth for the exact repair of systematic nodes, (b) proof of the necessity of interference alignment in exact-repair MSR codes, (c) a proof showing the impossibility of constructing linear, exact-repair MSR codes for d < 2k - 3 in the absence of symbol extension, and (d) the construction, also explicit, of high-rate MSR codes for d = k+1. Interference alignment (IA) is a theme that runs throughout the paper: the MISER code is built on the principles of IA and IA is also a crucial component to the nonexistence proof for d < 2k - 3. To the best of our knowledge, the constructions presented in this paper are the first explicit constructions of regenerating codes that achieve the cut-set bound.

Basic principles of ultrafast Raman loss spectroscopy

When a light beam passes through any medium, the effects of interaction of light with the material depend on the field intensity. At low light intensities the response of materials remain linear to the amplitude of the applied electromagnetic field. But for sufficiently high intensities, the optical properties of materials are no longer linear to the amplitude of applied electromagnetic field. In such cases, the interaction of light waves with matter can result in the generation of new frequencies due to nonlinear processes such as higher harmonic generation and mixing of incident fields. One such nonlinear process, namely, the third order nonlinear spectroscopy has become a popular tool to study molecular structure. Thus, the spectroscopy based on the third order optical nonlinearity called stimulated Raman spectroscopy (SRS) is a tool to extract the structural and dynamical information about a molecular system. Ultrafast Raman loss spectroscopy (URLS) is analogous to SRS but is more sensitive than SRS. In this paper, we present the theoretical basis of SRS (URLS) techniques which have been developed in our laboratory.

Coupled phonons, magnetic excitations, and ferroelectricity in AlFeO3: Raman and first-principles studies

We determine the nature of coupled phonons and magnetic excitations in AlFeO3 using inelastic light scattering from 5 to 315 K covering a spectral range from 100 to 2200 cm(-1) and complementary first-principles density functional theory-based calculations. A strong spin-phonon coupling and magnetic ordering-induced phonon renormalization are evident in (1) anomalous temperature dependence of many modes with frequencies below 850 cm(-1), particularly near the magnetic transition temperature T-c approximate to 250 K, and (2) distinct changes in band positions of high-frequency Raman bands between 1100 and 1800 cm(-1); in particular, a broad mode near 1250 cm(-1) appears only below T-c, attributed to the two-magnon Raman scattering. We also observe weak anomalies in the mode frequencies similar to 100 K due to a magnetically driven ferroelectric phase transition. Understanding of these experimental observations has been possible on the basis of first-principles calculations of the phonons' spectrum and their coupling with spins.

Signal-Powered Low-Drop-Diode Equivalent Circuit for Full-Wave Bridge Rectifier

Piezoelectric-device-based vibration energy harvesting requires a rectifier for conversion of input ac to usable dc form. Power loss due to diode drop in rectifier is a significant fraction of the already low levels of harvested power. The proposed circuit is a low-drop-diode equivalent, which mimics a diode using linear region-operated MOSFET. The proposed diode equivalent is powered directly from input signal and requires no additional power supply for its control. Power used by the control circuit is kept at a bare minimum to have an overall output power improvement. Diode equivalent was used to replace the four diodes in a full-wave bridge rectifier, which is the basic full- wave rectifier and is a part of the more advanced rectifiers like switch-only and bias-flip rectifiers. Simulation in 130-nm technology and experiment with discrete components show that a bridge rectifier with the proposed diode provides a 30-169% increase in output power extracted from piezoelectric device, as compared to a bridge rectifier with diode-connected MOSFETs. The bridge rectifier with the proposed diode can extract 90% of the maximum available power from an ideal piezoelectric device-bridge rectifier circuit. Setting aside the constraint of power loss, simulations indicate that diode drop as low as 10 mV at 38 mu A can be achieved.

Elasto-plastic analysis of jointed rocks using discrete continuum and equivalent continuum approaches

Results from elasto-plastic numerical simulations of jointed rocks using both the equivalent continuum and discrete continuum approaches are presented, and are compared with experimental measurements. Initially triaxial compression tests on different types of rocks with wide variation in the uniaxial compressive strength are simulated using both the approaches and the results are compared. The applicability and relative merits and limitations of both the approaches for the simulation of jointed rocks are discussed. It is observed that both the approaches are reasonably good in predicting the real response. However, the equivalent continuum approach has predicted somewhat higher stiffness values at low strains. Considering the modelling effort involved in case of discrete continuum approach, for problems with complex geometry, it is suggested that a proper equivalent continuum model can be used, without compromising much on the accuracy of the results. Then the numerical analysis of a tunnel in Japan is taken up using the continuum approach. The deformations predicted are compared well against the field measurements and the predictions from discontinuum analysis. (C) 2012 Elsevier Ltd. All rights reserved.

On maximum entropy and minimum KL-divergence optimization by Grobner basis methods

In this paper we study constrained maximum entropy and minimum divergence optimization problems, in the cases where integer valued sufficient statistics exists, using tools from computational commutative algebra. We show that the estimation of parametric statistical models in this case can be transformed to solving a system of polynomial equations. We give an implicit description of maximum entropy models by embedding them in algebraic varieties for which we give a Grobner basis method to compute it. In the cases of minimum KL-divergence models we show that implicitization preserves specialization of prior distribution. This result leads us to a Grobner basis method to embed minimum KL-divergence models in algebraic varieties. (C) 2012 Elsevier Inc. All rights reserved.

Natural Convection in a Vertical Channel with Arrays of Flush-Mounted Heaters on Opposite Conductive Walls

Three-dimensional numerical study of natural convection in a vertical channel with flush-mounted discrete heaters on opposite conductive substrate walls is carried out in the present work. Detailed flow and heat transfer characteristics are presented for various Grashof numbers. The heat transfer effects on one wall by the presence of heaters on its opposite wall is examined. It is found that heat transfer rates on one wall are increased by the presence of heaters on its opposite wall. The thermal boundary layers on the opposite walls complement each other for enhanced heat transfer. The effects of spacing between the heated walls, spacings between heaters and substrate conductivity on flow and heat transfer are examined. Existence of optimum spacings between the heated walls for maximum heat transfer and mass flow are observed. It is found that the heat transfer and fluid flow do not follow the same optimum spacings. Mass flow rate reaches maximum value at a wall spacing greater than the spacing for maximum heat transfer. This is because the interaction of thermal boundary layers on individual walls ceases at a lower spacing before the velocity boundary layers separate each other. It is found that increased spacings between heaters reduce individual heater temperatures provided the heaters close to exit on both substrates avail sufficient substrate potions on the exit side. Insufficient substrate portions between the exit heaters and the exit cause abnormal local temperature rise in the exit heaters which are the hottest ones among all the heaters. Optimal heater spacings exist for minimum hottest heater temperature rise. Correlations are presented for dimensionless mass flow rate, temperature maximum, and average Nusselt number.

First principles calculations of H-storage in sorption materials

A review of various contributions of first principles calculations in the area of hydrogen storage, particularly for the carbon-based sorption materials, is presented. Carbon-based sorption materials are considered as promising hydrogen storage media due to their light weight and large surface area. Depending upon the hybridization state of carbon, these materials can bind the hydrogen via various mechanisms, including physisorption, Kubas and chemical bonding. While attractive binding energy range of Kubas bonding has led to design of several promising storage systems, in reality the experiments remain very few due to materials design challenges that are yet to be overcome. Finally, we will discuss the spillover process, which deals with the catalytic chemisorption of hydrogen, and arguably is the most promising approach for reversibly storing hydrogen under ambient conditions.

Receive Antenna Selection for Time-Varying Channels Using Discrete Prolate Spheroidal Sequences

Receive antenna selection (AS) has been shown to maintain the diversity benefits of multiple antennas while potentially reducing hardware costs. However, the promised diversity gains of receive AS depend on the assumptions of perfect channel knowledge at the receiver and slowly time-varying fading. By explicitly accounting for practical constraints imposed by the next-generation wireless standards such as training, packetization and antenna switching time, we propose a single receive AS method for time-varying fading channels. The method exploits the low training overhead and accuracy possible from the use of discrete prolate spheroidal (DPS) sequences based reduced rank subspace projection techniques. It only requires knowledge of the Doppler bandwidth, and does not require detailed correlation knowledge. Closed-form expressions for the channel prediction and estimation error as well as symbol error probability (SEP) of M-ary phase-shift keying (MPSK) for symbol-by-symbol receive AS are also derived. It is shown that the proposed AS scheme, after accounting for the practical limitations mentioned above, outperforms the ideal conventional single-input single-output (SISO) system with perfect CSI and no AS at the receiver and AS with conventional estimation based on complex exponential basis functions.

Selective excitation and detection of maximum quantum coherence of a group of scalar coupled protons in chiral molecules: an NMR experiment for enantiodiscrimination

The H-1 NMR spectroscopic discrimination of enantiomers in the solution state and the measurement of enantiomeric composition is most often hindered due to either very small chemical shift differences between the discriminated peaks or severe overlap of transitions from other chemically non-equivalent protons. In addition the use of chiral auxiliaries such as, crown ether and chiral lanthanide shift reagent may often cause enormous line broadening or give little degree of discrimination beyond the crown ether substrate ratio, hampering the discrimination. In circumventing such problems we are proposing the utilization of the difference in the additive values of all the chemical shifts of a scalar coupled spin system. The excitation and detection of appropriate highest quantum coherence yields the measurable difference in the frequencies between two transitions, one pertaining to each enantiomer in the maximum quantum dimension permitting their discrimination and the F-2 cross section at each of these frequencies yields an enantiopure spectrum. The advantage of the utility of the proposed method is demonstrated on several chiral compounds where the conventional one dimensional H-1 NMR spectra fail to differentiate the enantiomers.

Capacity region of K-user discrete memoryless interference channels with a mixed strong-very strong interference

The capacity region of the 3-user Gaussian Interference Channel (GIC) with mixed strong-very strong interference was established in [1]. The mixed strong-very strong interference conditions considered in [1] correspond to the case where, at each receiver, one of the interfering signals is strong and the other is very strong. In this paper, we derive the capacity region of K-user (K ≥ 3) Discrete Memoryless Interference Channels (DMICs) with a mixed strong-very strong interference. This corresponds to the case where, at each receiver one of the interfering signals is strong and the other (K - 2) interfering signals are very strong. This includes, as a special case, the 3-user DMIC with mixed strong-very strong interference. The proof is specialized to the 3-user GIC case and hence an alternative derivation for the capacity region of the 3-user GIC with mixed strong-very strong interference is provided.

Multi-objective optimization of satellite image registration using discrete Pparticle swarm optimisation

A new multi-sensor image registration technique is proposed based on detecting the feature corner points using modified Harris Corner Detector (HDC). These feature points are matched using multi-objective optimization (distance condition and angle criterion) based on Discrete Particle Swarm Optimization (DPSO). This optimization process is more efficient as it considers both the distance and angle criteria to incorporate multi-objective switching in the fitness function. This optimization process helps in picking up three corresponding corner points detected in the sensed and base image and thereby using the affine transformation, the sensed image is aligned with the base image. Further, the results show that the new approach can provide a new dimension in solving multi-sensor image registration problems. From the obtained results, the performance of image registration is evaluated and is concluded that the proposed approach is efficient.

A fully discrete C-0 interior penalty Galerkin approximation of the extended Fisher-Kolmogorov equation

A fully discrete C-0 interior penalty finite element method is proposed and analyzed for the Extended Fisher-Kolmogorov (EFK) equation u(t) + gamma Delta(2)u - Delta u + u(3) - u = 0 with appropriate initial and boundary conditions, where gamma is a positive constant. We derive a regularity estimate for the solution u of the EFK equation that is explicit in gamma and as a consequence we derive a priori error estimates that are robust in gamma. (C) 2013 Elsevier B.V. All rights reserved.