Cubicity, degeneracy, and crossing number

A $k$-box $B=(R_1,...,R_k)$, where each $R_i$ is a closed interval on the real line, is defined to be the Cartesian product $R_1\times R_2\times ...\times R_k$. If each $R_i$ is a unit length interval, we call $B$ a $k$-cube. Boxicity of a graph $G$, denoted as $\boxi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-boxes. Similarly, the cubicity of $G$, denoted as $\cubi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-cubes. It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan: Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/ 0607092, 2006.] that, for a graph $G$ with maximum degree $\Delta$, $\cubi(G)\leq \lceil 4(\Delta +1)\log n\rceil$. In this paper, we show that, for a $k$-degenerate graph $G$, $\cubi(G) \leq (k+2) \lceil 2e \log n \rceil$. Since $k$ is at most $\Delta$ and can be much lower, this clearly is a stronger result. This bound is tight. We also give an efficient deterministic algorithm that runs in $O(n^2k)$ time to output a $8k(\lceil 2.42 \log n\rceil + 1)$ dimensional cube representation for $G$. An important consequence of the above result is that if the crossing number of a graph $G$ is $t$, then $\boxi(G)$ is $O(t^{1/4}{\lceil\log t\rceil}^{3/4})$ . This bound is tight up to a factor of $O((\log t)^{1/4})$. We also show that, if $G$ has $n$ vertices, then $\cubi(G)$ is $O(\log n + t^{1/4}\log t)$. Using our bound for the cubicity of $k$-degenerate graphs we show that cubicity of almost all graphs in $\mathcal{G}(n,m)$ model is $O(d_{av}\log n)$, where $d_{av}$ denotes the average degree of the graph under consideration. model is O(davlogn).

Condition R and proper holomorphic maps between equidimensional product domains

We consider proper holomorphic mappings of equidimensional pseudoconvex domains in complex Euclidean space, where both source and target can be represented as Cartesian products of smoothly bounded domains. It is shown that such mappings extend smoothly up to the closures of the domains, provided each factor of the source satisfies Condition R. It also shown that the number of smoothly bounded factors in the source and target must be the same, and the proper holomorphic map splits as a product of proper mappings between the factor domains. (C) 2013 Elsevier Inc. All rights reserved.

Note on modelling directionality in piezoresistivity

When computing the change in electrical resistivity of a piezoresistive cubic material embedded in a deforming structure, the piezoresistive and the stress tensors should be in the same coordinate system. While the stress tensor is usually calculated in a coordinate system aligned with the principal axes of a regular structure, the specified piezoresistive coefficients may not be in that coordinate system. For instance, piezoresistive coefficients are usually given in an orthogonal cartesian coordinate system aligned with the <100> crystallographic directions and designers sometimes deliberately orient a crystallographic direction other than <100> along the principal directions of the structure to increase the gauge factor. In such structures, it is advantageous to calculate the piezoresistivity tensor in the coordinate system along which the stress tensors are known rather than the other way around. This is because the transformation of stress will have to be done at every point in the structure but piezoresistivity tensor needs to be transformed only once. Here, using tensor transformation relations, we show how to calculate the piezoresistive tensor along any arbitrary Cartesian coordinate system from the piezoresistive coefficients for the <100> coordinate system. Some of the software packages that simulate the piezoresistive effect do not have interfaces for calculation of the entire piezoresistive tensor for arbitrary directions. This warrants additional work for the user because not considering the complete piezoresisitive tensor can lead to large errors. This is illustrated with an example where the error is as high as 33%. Additionally, for elastic analysis, we used hybrid finite element formulation that estimates stresses more accurately than displacement-based formulation. Therefore, as shown in an example where the change in resistance can be calculated analytically, the percentage error of our piezoresistive program is an order of magnitude lower relative to displacement-based finite element method.

Signal tracking approach for phase estimation in digital holographic interferometry

In this research work, we introduce a novel approach for phase estimation from noisy reconstructed interference fields in digital holographic interferometry using an unscented Kalman filter. Unlike conventionally used unwrapping algorithms and piecewise polynomial approximation approaches, this paper proposes, for the first time to the best of our knowledge, a signal tracking approach for phase estimation. The state space model derived in this approach is inspired from the Taylor series expansion of the phase function as the process model, and polar to Cartesian conversion as the measurement model. We have characterized our approach by simulations and validated the performance on experimental data (holograms) recorded under various practical conditions. Our study reveals that the proposed approach, when compared with various phase estimation methods available in the literature, outperforms at lower SNR values (i.e., especially in the range 0-20 dB). It is demonstrated with experimental data as well that the proposed approach is a better choice for estimating rapidly varying phase with high dynamic range and noise. (C) 2014 Optical Society of America

Isotropic finite volume discretization

Finite volume methods traditionally employ dimension by dimension extension of the one-dimensional reconstruction and averaging procedures to achieve spatial discretization of the governing partial differential equations on a structured Cartesian mesh in multiple dimensions. This simple approach based on tensor product stencils introduces an undesirable grid orientation dependence in the computed solution. The resulting anisotropic errors lead to a disparity in the calculations that is most prominent between directions parallel and diagonal to the grid lines. In this work we develop isotropic finite volume discretization schemes which minimize such grid orientation effects in multidimensional calculations by eliminating the directional bias in the lowest order term in the truncation error. Explicit isotropic expressions that relate the cell face averaged line and surface integrals of a function and its derivatives to the given cell area and volume averages are derived in two and three dimensions, respectively. It is found that a family of isotropic approximations with a free parameter can be derived by combining isotropic schemes based on next-nearest and next-next-nearest neighbors in three dimensions. Use of these isotropic expressions alone in a standard finite volume framework, however, is found to be insufficient in enforcing rotational invariance when the flux vector is nonlinear and/or spatially non-uniform. The rotationally invariant terms which lead to a loss of isotropy in such cases are explicitly identified and recast in a differential form. Various forms of flux correction terms which allow for a full recovery of rotational invariance in the lowest order truncation error terms, while preserving the formal order of accuracy and discrete conservation of the original finite volume method, are developed. Numerical tests in two and three dimensions attest the superior directional attributes of the proposed isotropic finite volume method. Prominent anisotropic errors, such as spurious asymmetric distortions on a circular reaction-diffusion wave that feature in the conventional finite volume implementation are effectively suppressed through isotropic finite volume discretization. Furthermore, for a given spatial resolution, a striking improvement in the prediction of kinetic energy decay rate corresponding to a general two-dimensional incompressible flow field is observed with the use of an isotropic finite volume method instead of the conventional discretization. (C) 2014 Elsevier Inc. All rights reserved.

Rainbow Connection Number of Graph Power and Graph Products

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely the Cartesian product, the lexicographic product and the strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) a parts per thousand currency sign 2r(G) + c, where r(G) denotes the radius of G and . In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius 1]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight up to additive constants. The proofs are constructive and hence yield polynomial time -factor approximation algorithms.

LOWER BOUNDS FOR BOXICITY

An axis-parallel b-dimensional box is a Cartesian product R-1 x R-2 x ... x R-b where R-i 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 b, such that G is representable as the intersection graph of boxes in b-dimensional space. Although boxicity was introduced in 1969 and studied extensively, there are no significant results on lower bounds for boxicity. In this paper, we develop two general methods for deriving lower bounds. Applying these methods we give several results, some of which are listed below: 1. The boxicity of a graph on n vertices with no universal vertices and minimum degree delta is at least n/2(n-delta-1). 2. Consider the g(n,p) model of random graphs. Let p <= 1 - 40logn/n(2.) Then with high `` probability, box(G) = Omega(np(1 - p)). On setting p = 1/2 we immediately infer that almost all graphs have boxicity Omega(n). Another consequence of this result is as follows: For any positive constant c < 1, almost all graphs on n vertices and m <= c((n)(2)) edges have boxicity Omega(m/n). 3. Let G be a connected k-regular graph on n vertices. Let lambda be the second largest eigenvalue in absolute value of the adjacency matrix of G. Then, the boxicity of G is a least (kappa(2)/lambda(2)/log(1+kappa(2)/lambda(2))) (n-kappa-1/2n). 4. For any positive constant c 1, almost all balanced bipartite graphs on 2n vertices and m <= cn(2) edges have boxicity Omega(m/n).

The cold mode: a phenomenological model for the evolution of density perturbations in the intracluster medium

Cool cluster cores are in global thermal equilibrium but are locally thermally unstable. We study a non-linear phenomenological model for the evolution of density perturbations in the intracluster medium (ICM) due to local thermal instability and gravity. We have analysed and extended a model for the evolution of an overdense blob in the ICM. We find two regimes in which the overdense blobs can cool to thermally stable low temperatures. One for large t(cool)/t(ff) (t(cool) is the cooling time and t(ff) is the free-fall time), where a large initial overdensity is required for thermal runaway to occur; this is the regime which was previously analysed in detail. We discover a second regime for t(cool)/t(ff) less than or similar to 1 (in agreement with Cartesian simulations of local thermal instability in an external gravitational field), where runaway cooling happens for arbitrarily small amplitudes. Numerical simulations have shown that cold gas condenses out more easily in a spherical geometry. We extend the analysis to include geometrical compression in weakly stratified atmospheres such as the ICM. With a single parameter, analogous to the mixing length, we are able to reproduce the results from numerical simulations; namely, small density perturbations lead to the condensation of extended cold filaments only if t(cool)/t(ff) less than or similar to 10.

Hierarchical sampling for metastable conformers determines biomolecular recognition: the case of malectin and diglucosylated N-glycan interactions

Structural information over the entire course of binding interactions based on the analyses of energy landscapes is described, which provides a framework to understand the events involved during biomolecular recognition. Conformational dynamics of malectin's exquisite selectivity for diglucosylated N-glycan (Dig-N-glycan), a highly flexible oligosaccharide comprising of numerous dihedral torsion angles, are described as an example. For this purpose, a novel approach based on hierarchical sampling for acquiring metastable molecular conformations constituting low-energy minima for understanding the structural features involved in a biologic recognition is proposed. For this purpose, four variants of principal component analysis were employed recursively in both Cartesian space and dihedral angles space that are characterized by free energy landscapes to select the most stable conformational substates. Subsequently, k-means clustering algorithm was implemented for geometric separation of the major native state to acquire a final ensemble of metastable conformers. A comparison of malectin complexes was then performed to characterize their conformational properties. Analyses of stereochemical metrics and other concerted binding events revealed surface complementarity, cooperative and bidentate hydrogen bonds, water-mediated hydrogen bonds, carbohydrate-aromatic interactions including CH-pi and stacking interactions involved in this recognition. Additionally, a striking structural transition from loop to beta-strands in malectin CRD upon specific binding to Dig-N-glycan is observed. The interplay of the above-mentioned binding events in malectin and Dig-N-glycan supports an extended conformational selection model as the underlying binding mechanism.

Boxicity and cubicity of product graphs

The boxicity (cubicity) of a graph G is the minimum natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in R-k. In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of d, of the boxicity and the cubicity of the dth power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the dth Cartesian power of any given finite graph is, respectively, in O(log d/ log log d) and circle dot(d/ log d). On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products. (C) 2015 Elsevier Ltd. All rights reserved.

Cold gas in cluster cores: global stability analysis and non-linear simulations of thermal instability

We perform global linear stability analysis and idealized numerical simulations in global thermal balance to understand the condensation of cold gas from hot/virial atmospheres (coronae), in particular the intracluster medium (ICM). We pay particular attention to geometry (e.g. spherical versus plane-parallel) and the nature of the gravitational potential. Global linear analysis gives a similar value for the fastest growing thermal instability modes in spherical and Cartesian geometries. Simulations and observations suggest that cooling in haloes critically depends on the ratio of the cooling time to the free-fall time (t(cool)/t(ff)). Extended cold gas condenses out of the ICM only if this ratio is smaller than a threshold value close to 10. Previous works highlighted the difference between the nature of cold gas condensation in spherical and plane-parallel atmospheres; namely, cold gas condensation appeared easier in spherical atmospheres. This apparent difference due to geometry arises because the previous plane-parallel simulations focused on in situ condensation of multiphase gas but spherical simulations studied condensation anywhere in the box. Unlike previous claims, our non-linear simulations show that there are only minor differences in cold gas condensation, either in situ or anywhere, for different geometries. The amount of cold gas depends on the shape of tcool/tff; gas has more time to condense if gravitational acceleration decreases towards the centre. In our idealized plane-parallel simulations with heating balancing cooling in each layer, there can be significant mass/energy/momentum transfer across layers that can trigger condensation and drive tcool/tff far beyond the critical value close to 10.

Del sueño cartesiano a la muerte encefálica

Resumen: Entre el sueño y la muerte hay “sólo una distancia”. El dormir encierra un misterio que se aviva con los sueños y, al parecer, habrían prefigurado al mismo método científico moderno. Descartes pensó que en sus sueños se transmitía el espíritu de la verdad. El alma soñadora e inmortal adquirió notoriedad en su dualismo, al tiempo que dejó de asociársela con la muerte. Tres siglos después, la medicina permitió identificar individuos que estaban muertos, aunque pareciesen dormidos (coma dépassé). Así reapareció la asociación sueño-muerte, pero ahora con médicos provistos del “diagnóstico anátomo-clínico” que, por su herencia cartesiana, demandará evidencias. La duda metódica integrada al pensamiento científico, aportaría incertidumbre a las formulaciones cerebrales de la muerte. Este trabajo repasa el valor de los sueños para el pensamiento occidental, busca al “hombre-máquina” dentro de los criterios neurológicos del fallecido y, con la ayuda de la Filosofía, intenta comprender algunas objeciones en torno a la licitud del diagnóstico de “muerte encefálica”. Se propone una revisión sucinta de la obra del filósofo francés y su reflejo en aspectos del debate ofrecido por la literatura médica.

Aportes teóricos de la psicología cognitiva para la construcción de una nueva economía científica

Resumen: El presente ensayo teórico se orienta a revisar las concepciones de sujeto de uno de los sistemas teóricos de economía-política que han tenido mayor influencia hasta el presente. El padre del liberalismo (Adam Smith) sustentó una teoría de sujeto cartesiano (moderno), es decir, un verdadero sapiens sapiens racional y autoconsciente. A través de la psicología cognitiva, los Premios Nobel en economía Kanheman y Tversky presentan una nueva variante de homoeconomicus, enriquecida con aportes de la ciencia experimental, modificando sustancialmente aquella vieja concepción de hombre como ser racional que signó casi todo el pensamiento moderno. Dadas estas “recientes revisiones” teórico-metodológicas, gestadas a la luz de la denominada ciencia de la mente, es que se hace indispensable re-pensar las viejas nociones de sujeto que sirvieron de cimiento al sistema económico y político, antes citadas. Para tal fin, se propone efectuar una sinergia teórico-metodológica entre dos disciplinas científicas: la economía y la psicología. Dicho sincretismo podría proporcionar las bases para una nueva disciplina científica integradora, que muchos teóricos ya han denominado neuro-economía. Es por esto que en el presente trabajo se propone realizar una crítica fundamentada de una de las teorías económicas vigentes, haciendo principal hincapié en los supuestos psicológicos y antropológicos. Finalmente, se intenta re-pensar un nuevo modelo de homoeconomicus, articulando los principales supuestos de la economía actual con algunos de los aportes de la psicología cognitiva, la biología y las neurociencias cognitivas, que redunde en un nuevo paradigma integrador denominado psiconeuro- economía.

Anima, mente, corpo e inmortalità : la sfida del naturalismo

Resumen: Il saggio esamina il rapporto anima, mente, corpo alla luce delle sfide del nuovo naturalismo che molto spesso incorpora un secco riduzionismo ed un’opzione materialistica. Questa risulta un apriori, non l’esito di un argomento: J. Searle la chiama “la religione del nostro tempo”. Vengono poi esaminati l’attuale oblio dell’anima, la riduzione del suo tema al mind-body problem, la qualità della tesi ilemorfica, illustrata in specie attraverso le soluzioni dell’Aquinate, l’equivoco del dualismo cartesiano. Chiude il saggio uno sguardo sulla questione dell’immortalità dell’anima.

Dynamic equations for curved submerged floating tunnel

In virtue of reference Cartesian coordinates, geometrical relations of spatial curved structure are presented in orthogonal curvilinear coordinates. Dynamic equations for helical girder are derived by Hamilton principle. These equations indicate that four generalized displacements are coupled with each other. When spatial structure degenerates into planar curvilinear structure, two generalized displacements in two perpendicular planes are coupled with each other. Dynamic equations for arbitrary curvilinear structure may be obtained by the method used in this paper.