The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

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 can be represented as 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 R-i is a closed interval oil the real line of the form a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-cubes. The threshold dimension of a graph G(V, E) is the smallest integer k such that E can be covered by k threshold spanning subgraphs of G. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n vertices with factor O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is NP-complete to determine whether a given split graph has boxicity at most 3. (C) 2010 Elsevier B.V. All rights reserved.

Spin-1 Kitaev model in one dimension

We study a one-dimensional version of the Kitaev model on a ring of size N, in which there is a spin S > 1/2 on each site and the Hamiltonian is J Sigma(nSnSn+1y)-S-x. The cases where S is integer and half-odd integer are qualitatively different. We show that there is a Z(2)-valued conserved quantity W-n for each bond (n, n + 1) of the system. For integer S, the Hilbert space can be decomposed into 2N sectors, of unequal sizes. The number of states in most of the sectors grows as d(N), where d depends on the sector. The largest sector contains the ground state, and for this sector, for S=1, d=(root 5+1)/2. We carry out exact diagonalization for small systems. The extrapolation of our results to large N indicates that the energy gap remains finite in this limit. In the ground-state sector, the system can be mapped to a spin-1/2 model. We develop variational wave functions to study the lowest energy states in the ground state and other sectors. The first excited state of the system is the lowest energy state of a different sector and we estimate its excitation energy. We consider a more general Hamiltonian, adding a term lambda Sigma W-n(n), and show that this has gapless excitations in the range lambda(c)(1)<=lambda <=lambda(c)(2). We use the variational wave functions to study how the ground-state energy and the defect density vary near the two critical points lambda(c)(1) and lambda(c)(2).

Fractal boundaries of basin of attraction of Newton-Raphson method in helicopter trim

A key problem in helicopter aeroelastic analysis is the enormous computational time required for a numerical solution of the nonlinear system of algebraic equations required for trim, particularly when free wake models are used. Trim requires calculation of the main rotor and tail rotor controls and the vehicle attitude which leads to the six steady forces and moments about the helicopter center of gravity to be zero. An appropriate initial estimate of the trim state is needed for successful helicopter trim. This study aims to determine the control inputs that can have considerable effect on the convergence of trim solution in the aeroelastic analysis of helicopter rotors by investigating the basin of attraction of the nonlinear equations (set of initial guess points from which the nonlinear equations converge). It is illustrated that the three main rotor pitch controls of collective pitch, longitudinal cyclic pitch and lateral cyclic pitch have a significant contribution to the convergence of the trim solution. Trajectories of the Newton iterates are shown and some ideas for accelerating the convergence of a trim solution in the aeroelastic analysis of helicopters are proposed. It is found that the basins of attraction can have fractal boundaries. (C) 2010 Elsevier Ltd. All rights reserved.

Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V(G) and edge set E(C). 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, anti-symmetric and transitive binary relation on S. The dimension of P, dim(P) is the minimum integer l such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of 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. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with its extended double cover, denoted as G(c). 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. In the other direction, using the already known bounds for partial order dimension we get the following: (I) 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-epsilon)) for any epsilon > 0, unless NP=ZPP.

Phonons and fractons in sol-gel alumina: Raman study

We report Raman scattering from the boehmite, gamma-, delta- and alpha-phases of the alumina gel. Samples are characterized by transmission and scanning electron microscopy, X-ray diffraction and density measurements. The main Raman line in the boehmite phase is red-shifted as well as asymmetrically broadened with respect to that in the crystalline boehmite, signifying the nanocrystalline nature of the gel. Raman signatures are absent in the gamma- and delta-phases due to the disorder in cation vacancies. We also show that low frequency Raman scattering from the boehmite phase resembles that from a fractal network, characterized in terms of fraction dimension ($) over tilde d. Taking Hausdorff dimension D of the boehmite gel to be 2.5 (or 3.0), the value of ($) over tilde d is 1.33 +/- 0.02 (or 1.44 +/- 0.02), which is close to the theoretically predicted value of 4/3.

A New Class of Exactly Solvable Interacting Fermion Models in One Dimension

We investigate a model containing two species of one-dimensional fermions interacting via a gauge field determined by the positions of all particles of the opposite species. The model can be salved exactly via a simple unitary transformation. Nevertheless, correlation functions exhibit nontrivial interaction-dependent exponents. A similar model defined on a lattice is introduced and solved. Various generalizations, e.g., to the case of internal symmetries of the fermions, are discussed. The present treatment also clarifies certain aspects of Luttinger's original solution of the "Luttinger model."

Exact spectral functions of a non-Fermi liquid in one dimension

We study the exact one-electron propagator and spectral function of a solvable model of interacting electrons due to Schulz and Shastry. The solution previously found for the energies and wave functions is extended to give spectral functions that turn out to be computable, interesting, and nontrivial. They provide one of the few examples of cases where the spectral functions are known asymptotically as well as exactly.

13C-1H HSQC Experiment of Probe Molecules Aligned in Thermotropic Liquid Crystals: Sensitivity and Resolution Enhancement in the Indirect Dimension

The spectra of molecules oriented in liquid crystalline media are dominated by partially averaged dipolar couplings. In the 13C–1H HSQC, due to the inefficient hetero-nuclear dipolar decoupling in the indirect dimension, normally carried out by using a π pulse, there is a considerable loss of resolution. Furthermore, in such strongly orienting media the 1H–1H and 13C–1H dipolar couplings leads to fast dephasing of transverse magnetization causing inefficient polarization transfer and hence the loss of sensitivity in the indirect dimension. In this study we have carried out 13C–1H HSQC experiment with efficient polarization transfer from 1H to 13C for molecules aligned in liquid crystalline media. The homonuclear dipolar decoupling using FFLG during the INEPT transfer delays and also during evolution period combined with the π pulse heteronuclear decoupling in the t1 period has been applied. The studies showed a significant reduction in partially averaged dipolar couplings and thereby enhancement in the resolution and sensitivity in the indirect dimension. This has been demonstrated on pyridazine and pyrimidine oriented in the liquid crystal. The two closely resonating carbons in pyrimidine are better resolved in the present study compared to the earlier work [H.S. Vinay Deepak, Anu Joy, N. Suryaprakash, Determination of natural abundance 15N–1H and 13C–1H dipolar couplings of molecules in a strongly orienting media using two-dimensional inverse experiments, Magn. Reson. Chem. 44 (2006) 553–565].

Geometric representations of graphs in low dimension

We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5 (\Delta + 2) \ln n$ dimensions, where $\Delta$ is the maximum degree of G. We also show that $\boxi(G) \le (\Delta + 2) \ln n$ 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, its boxicity is upper bound by $c\cdot(d_{av} + 1) \ln n$ where d_{av} is the average degree and c is a small constant. Also, we show that for any graph G, $\boxi(G) \le \sqrt{8 n d_{av} \ln n}$, which is tight up to a factor of $b \sqrt{\ln n}$ for a constant b.

Fracture analysis of concrete using singular fractal functions with lattice beam network and confirmation with acoustic emission study

In the present study singular fractal functions (SFF) were used to generate stress-strain plots for quasibrittle material like concrete and cement mortar and subsequently stress-strain plot of cement mortar obtained using SFF was used for modeling fracture process in concrete. The fracture surface of concrete is rough and irregular. The fracture surface of concrete is affected by the concrete's microstructure that is influenced by water cement ratio, grade of cement and type of aggregate 11-41. Also the macrostructural properties such as the size and shape of the specimen, the initial notch length and the rate of loading contribute to the shape of the fracture surface of concrete. It is known that concrete is a heterogeneous and quasi-brittle material containing micro-defects and its mechanical properties strongly relate to the presence of micro-pores and micro-cracks in concrete 11-41. The damage in concrete is believed to be mainly due to initiation and development of micro-defects with irregularity and fractal characteristics. However, repeated observations at various magnifications also reveal a variety of additional structures that fall between the `micro' and the `macro' and have not yet been described satisfactorily in a systematic manner [1-11,15-17]. The concept of singular fractal functions by Mosolov was used to generate stress-strain plot of cement concrete, cement mortar and subsequently the stress-strain plot of cement mortar was used in two-dimensional lattice model [28]. A two-dimensional lattice model was used to study concrete fracture by considering softening of matrix (cement mortar). The results obtained from simulations with lattice model show softening behavior of concrete and fairly agrees with the experimental results. The number of fractured elements are compared with the acoustic emission (AE) hits. The trend in the cumulative fractured beam elements in the lattice fracture simulation reasonably reflected the trend in the recorded AE measurements. In other words, the pattern in which AE hits were distributed around the notch has the same trend as that of the fractured elements around the notch which is in support of lattice model. (C) 2011 Elsevier Ltd. All rights reserved.

Low-Complexity Detection in Large-Dimension MIMO-ISI Channels Using Graphical Models

In this paper, we deal with low-complexity near-optimal detection/equalization in large-dimension multiple-input multiple-output inter-symbol interference (MIMO-ISI) channels using message passing on graphical models. A key contribution in the paper is the demonstration that near-optimal performance in MIMO-ISI channels with large dimensions can be achieved at low complexities through simple yet effective simplifications/approximations, although the graphical models that represent MIMO-ISI channels are fully/densely connected (loopy graphs). These include 1) use of Markov random field (MRF)-based graphical model with pairwise interaction, in conjunction with message damping, and 2) use of factor graph (FG)-based graphical model with Gaussian approximation of interference (GAI). The per-symbol complexities are O(K(2)n(t)(2)) and O(Kn(t)) for the MRF and the FG with GAI approaches, respectively, where K and n(t) denote the number of channel uses per frame, and number of transmit antennas, respectively. These low-complexities are quite attractive for large dimensions, i.e., for large Kn(t). From a performance perspective, these algorithms are even more interesting in large-dimensions since they achieve increasingly closer to optimum detection performance for increasing Kn(t). Also, we show that these message passing algorithms can be used in an iterative manner with local neighborhood search algorithms to improve the reliability/performance of M-QAM symbol detection.

Online Handwriting Recognition of Tamil Script Using Fractal Geometry

We present a fractal coding method to recognize online handwritten Tamil characters and propose a novel technique to increase the efficiency in terms of time while coding and decoding. This technique exploits the redundancy in data, thereby achieving better compression and usage of lesser memory. It also reduces the encoding time and causes little distortion during reconstruction. Experiments have been conducted to use these fractal codes to classify the online handwritten Tamil characters from the IWFHR 2006 competition dataset. In one approach, we use fractal coding and decoding process. A recognition accuracy of 90% has been achieved by using DTW for distortion evaluation during classification and encoding processes as compared to 78% using nearest neighbor classifier. In other experiments, we use the fractal code, fractal dimensions and features derived from fractal codes as features in separate classifiers. While the fractal code is successful as a feature, the other two features are not able to capture the wide within-class variations.