Bounds on isoperimetric values of trees

Let G = (V, E) be a finite, simple and undirected graph. For S subset of V, let delta(S, G) = {(u, v) is an element of E : u is an element of S and v is an element of V - S} be the edge boundary of S. Given an integer i, 1 <= i <= vertical bar V vertical bar, let the edge isoperimetric value of G at i be defined as b(e)(i, G) = min(S subset of V:vertical bar S vertical bar=i)vertical bar delta(S, G)vertical bar. The edge isoperimetric peak of G is defined as b(e)(G) = max(1 <= j <=vertical bar V vertical bar)b(e)(j, G). Let b(v)(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi: 10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees. The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as T-d(2)), c(1)d <= b(e) (T-d(2)) <= d and c(2)d <= b(v)(T-d(2)) <= d where c(1), c(2) are constants. For a complete t-ary tree of depth d (denoted as T-d(t)) and d >= c log t where c is a constant, we show that c(1)root td <= b(e)(T-d(t)) <= td and c(2)d/root t <= b(v) (T-d(t)) <= d where c(1), c(2) are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T = (V, E, r) be a finite, connected and rooted tree - the root being the vertex r. Define a weight function w : V -> N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index eta(T) be defined as the number of distinct weights in the tree, i.e eta(T) vertical bar{w(u) : u is an element of V}vertical bar. For a positive integer k, let l(k) = vertical bar{i is an element of N : 1 <= i <= vertical bar V vertical bar, b(e)(i, G) <= k}vertical bar. We show that l(k) <= 2(2 eta+k k)

On the Cubicity of Interval Graphs

A k-cube (or ``a unit cube in k dimensions'') is defined as the Cartesian product R-1 x . . . x R-k where R-i (for 1 <= i <= k) is an interval of the form [a(i), a(i) + 1] on the real line. The k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that the k-cubes corresponding to two vertices in G have a non-empty intersection if and only if the vertices are adjacent. The cubicity of a graph G, denoted as cub(G), is defined as the minimum dimension k such that G has a k-cube representation. An interval graph is a graph that can be represented as the intersection of intervals on the real line - i. e., the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. We show that for any interval graph G with maximum degree Delta, cub(G) <= inverted right perpendicular log(2) Delta inverted left perpendicular + 4. This upper bound is shown to be tight up to an additive constant of 4 by demonstrating interval graphs for which cubicity is equal to inverted right perpendicular log(2) Delta inverted left perpendicular.

Influence of spatial variability of permeability property on steady state seepage flow and slope stability analysis

In recent years, spatial variability modeling of soil parameters using random field theory has gained distinct importance in geotechnical analysis. In the present Study, commercially available finite difference numerical code FLAC 5.0 is used for modeling the permeability parameter as spatially correlated log-normally distributed random variable and its influence on the steady state seepage flow and on the slope stability analysis are studied. Considering the case of a 5.0 m high cohesive-frictional soil slope of 30 degrees, a range of coefficients of variation (CoV%) from 60 to 90% in the permeability Values, and taking different values of correlation distance in the range of 0.5-15 m, parametric studies, using Monte Carlo simulations, are performed to study the following three aspects, i.e., (i) effect ostochastic soil permeability on the statistics of seepage flow in comparison to the analytic (Dupuit's) solution available for the uniformly constant permeability property; (ii) strain and deformation pattern, and (iii) stability of the given slope assessed in terms of factor of safety (FS). The results obtained in this study are useful to understand the role of permeability variations in slope stability analysis under different slope conditions and material properties. (C) 2009 Elsevier B.V. All rights reserved.

Intent Based Clustering of Search Engine Query Log

The keyword based search technique suffers from the problem of synonymic and polysemic queries. Current approaches address only theproblem of synonymic queries in which different queries might have the same information requirement. But the problem of polysemic queries,i.e., same query having different intentions, still remains unaddressed. In this paper, we propose the notion of intent clusters, the members of which will have the same intention. We develop a clustering algorithm that uses the user session information in query logs in addition to query URL entries to identify cluster of queries having the same intention. The proposed approach has been studied through case examples from the actual log data from AOL, and the clustering algorithm is shown to be successful in discerning the user intentions.

Approximate linear time ML decoding on tail-biting trellises in two rounds

A linear time approximate maximum likelihood decoding algorithm on tail-biting trellises is presented, that requires exactly two rounds on the trellis. This is an adaptation of an algorithm proposed earlier with the advantage that it reduces the time complexity from O(m log m) to O(m) where m is the number of nodes in the tail-biting trellis. A necessary condition for the output of the algorithm to differ from the output of the ideal ML decoder is deduced and simulation results on an AWGN channel using tail-biting trellises for two rate 1/2 convolutional codes with memory 4 and 6 respectively, are reported.

Remark on factorials that are products of factorials

In a paper published in 1993, Erdos proved that if n! = a! b!, where 1 < a a parts per thousand currency sign b, then the difference between n and b does not exceed 5 log log n for large enough n. In the present paper, we improve this upper bound to ((1 + epsilon)/ log 2) log log n and generalize it to the equation a (1)!a (2)! ... a (k) ! = n!. In a recent paper, F. Luca proved that n - b = 1 for large enough n provided that the ABC-hypothesis holds.

The log delta log t method for the determination of the coefficient of consolidation

The behaviour of saturated soils undergoing consolidation is very complex, It may not follow Terzaghi's theory over the entire consolidation process, Different soils may behave in such a way as to fit into Terzaghi's theory over some specific stages of the consolidation process (percentage of consolidation), This may be one of the reasons for the difficulties faced by the existing curve-fitting procedures in obtaining the coefficient of consolidation, c(v). It has been shown that the slope of the initial linear portion of the theoretical log U-log T curve is constant over a wider range of degree of consolidation, U, when compared with the other methods in use, This initial well-defined straight line in the log U-log T plot intersects the U = 100% line at T = pi/4, which corresponds to U = 88.3%, The proposed log delta-log t method is based on this observation, which gives the value of c(v) through simple graphical construction, In the proposed method, which is more versatile, identification of the characteristic straight lines is very clear; the intersection of these lines is more precise and the method does not depend upon the initial compression for the determination of c(v).

Propensity of formation of zipper architecture vs. Lincoln log arrangement in solvated molecular complexes of melamine with hydroxybenzoic acids

Molecular complexes of melamine with hydroxy and dihydroxybenzoic acids have been analyzed to assess the collective role of the hydroxyl (OH) and carboxyl (COOH) functionalities in the recognition process. In most cases, solvents of crystallization do play a major role in self-assembly and structure stabilization. Hydrated compounds generate linear chains of melamine molecules with acid molecules pendant resulting in a zipper architecture. However, anhydrous and solvated compounds generate tetrameric units consisting of melamine dimers together with acid molecules. These tetramers in turn interweave to form a Lincoln log arrangement in the crystal. The salt/co-crystal formation in these complexes cannot be predicted apriori on the basis of Delta pK(a) values as there exists a salt-to-co-crystal continuum.

On the Limits of Spatial Reuse and Cooperative Communication for Dense Wireless Networks

We consider a dense ad hoc wireless network comprising n nodes confined to a given two dimensional region of fixed area. For the Gupta-Kumar random traffic model and a realistic interference and path loss model (i.e., the channel power gains are bounded above, and are bounded below by a strictly positive number), we study the scaling of the aggregate end-to-end throughput with respect to the network average power constraint, P macr, and the number of nodes, n. The network power constraint P macr is related to the per node power constraint, P macr, as P macr = np. For large P, we show that the throughput saturates as Theta(log(P macr)), irrespective of the number of nodes in the network. For moderate P, which can accommodate spatial reuse to improve end-to-end throughput, we observe that the amount of spatial reuse feasible in the network is limited by the diameter of the network. In fact, we observe that the end-to-end path loss in the network and the amount of spatial reuse feasible in the network are inversely proportional. This puts a restriction on the gains achievable using the cooperative communication techniques studied in and, as these rely on direct long distance communication over the network.

On guessing the realization of an arbitrarily varying source

We present a method to guess the realization of an arbitrarily varying source. Let TU be the type of the unknown state sequence. Our method results in a guessing moment that is within Kn (TU) + O(log n=n) of the minimum attainable guessing moment with full knowledge of source statistics, i.e., with knowledge of the sequence of states sn. The quantity Kn (TU) + O(log n=n) can be interpreted as the penalty one pays for not knowing the sequence of states sn of the source. Kn (TU) by itself is the penalty one pays for guessing with the additional knowledge that the state sequence belongs to type TU. Conversely, given any guessing strategy, for every type TU, there is a state sequence belonging to this type whose corresponding source forces a guessing moment penalty of at least Kn (TU) ¡ O(log n=n).

Inhibition of Mycobacterium tuberculosis RNA Polymerase by Binding of a Gre Factor Homo log to the Secondary Channel

Because of its essential nature, each step of transcription, viz., initiation, elongation, and termination, is subjected to elaborate regulation. A number of transcription factors modulate the rates of transcription at these different steps, and several inhibitors shut down the process. Many modulators, including small molecules and proteinaceous inhibitors, bind the RNA polymerase (RNAP) secondary channel to control transcription. We describe here the first small protein inhibitor of transcription in Mycobacterium tuberculosis. Rv3788 is a homolog of the Gre factors that binds near the secondary channel of RNAP to inhibit transcription. The factor also affected the action of guanosine pentaphosphate (pppGpp) on transcription and abrogated Gre action, indicating its function in the modulation of the catalytic center of RNAP. Although it has a Gre factor-like domain organization with the conserved acidic residues in the N terminus and retains interaction with RNAP, the factor did not show any transcript cleavage stimulatory activity. Unlike Rv3788, another Gre homolog from Mycobacterium smegmatis, MSMEG_6292 did not exhibit transcription-inhibitory activities, hinting at the importance of the former in influencing the lifestyle of M. tuberculosis.

Moderate intensity static magnetic field has bactericidal effect on E. coli and S. epidermidis on sintered hydroxyapatite

The application of electromagnetic field in the context of bacteria associated infections on biomaterial surfaces has not been extensively explored. In this work, we applied a moderate intensity static magnetic field (100 mT) to understand the adhesion and growth behavior of both gram positive (S. epidermidis) and gram negative bacteria (E. coli) and also to investigate bactericidal/bacteriostatic property of the applied electromagnetic field. An in-house built magnetometer was used to apply static homogeneous magnetic field during a planned set of in vitro experiments. Both the sintered hydroxyapatite (HA) and the control samples seeded with bacteria were exposed to the magnetic field (100 mT) for different timescale during their log phase growth. Quantitative analysis of the SEM images confirms the effect of electromagnetic field on suppressing bacterial growth. Furthermore, cell integrity and inner membrane permeabilization assays were performed to understand the origin of such effect. The results of these assays were statistically analyzed to reveal the bactericidal effect of magnetic field, indicating cell membrane damage. Under the investigated culture conditions, the bactericidal effect was found to be less effective for S. Epidermidis than E. coli. (c) 2012 Wiley Periodicals, Inc. J Biomed Mater Res Part B: Appl Biomater 2012:100B:12061217, 2012.

An experimental study on cracking evolution in concrete and cement mortar by the b-value analysis of acoustic emission technique

Notched three point bend (TPB) specimens made with plain concrete and cement mortar were tested under crack mouth opening displacement (CMOD) control at a rate of 0.0004 mm/s and simultaneously acoustic emissions (AE) released were recorded during the experiments. Amplitude distribution analysis of AE released during concrete was carried out to study the development of fracture process in concrete and mortar specimens. The slope of the log-linear frequency-amplitude distribution of AE is known as the AE based b-value. The AE based b-value was computed in terms of physical process of time varying applied load using cumulative frequency distribution (Gutenberg-Richter relationship) and discrete frequency distribution (Aki's method) of AE released during concrete fracture. AE characteristics of plain concrete and cement mortar were studied and discussed and it was observed that the AE based b-value analysis serves as a tool to identify the damage in concrete structural members. (C) 2012 Elsevier Ltd. All rights reserved.

Impact of pit-toilet leachate on groundwater chemistry and role of vadose zone in removal of nitrate and E-coli pollutants in Kolar District, Karnataka, India

Assessment of chemistry of groundwater infiltrated by pit-toilet leachate and contaminant removal by vadose zone form the focus of this study. The study area is Mulbagal Town in Karnataka State, India. Groundwater level measurements and estimation of unsaturated permeability indicated that the leachate recharged the groundwater inside the town at the rate of 1 m/day. The average nitrate concentration of groundwater inside the town (148 mg/L) was three times larger than the permissible limit (45 mg/L), while the average nitrate concentration of groundwater outside the town (30 mg/L) was below the permissible limit. The groundwater inside the town exhibited E. coli contamination, while groundwater outside the town was free of pathogen contamination. Infiltration of alkalis (Na+, K+) and strong acids (Cl-, SO4 (2-)) caused the mixed Ca-Mg-Cl type (60 %) and Na-Cl type (28 %) facies to predominate groundwater inside the town, while, Ca-HCO3 (35 %), mixed Ca-Mg-Cl type (35 %) and mixed Ca-Na-HCO3 type (28 %) facies predominated groundwater outside/periphery of town. Reductions in E. coli and nitrate concentrations with vadose zone thickness indicated its participation in contaminant removal. A 4-m thickness of unsaturated sand + soft, disintegrated weathered rock deposit facilitates the removal of 1 log of E. coli pathogen. The anoxic conditions prevailing in the deeper layers of the vadose zone (> 19 m thickness) favor denitrification resulting in lower nitrate concentrations (28-96 mg/L) in deeper water tables (located at depths of -29 to -39 m).

On finding a set of healthy individuals from a large population

In this paper, we explore fundamental limits on the number of tests required to identify a given number of ``healthy'' items from a large population containing a small number of ``defective'' items, in a nonadaptive group testing framework. Specifically, we derive mutual information-based upper bounds on the number of tests required to identify the required number of healthy items. Our results show that an impressive reduction in the number of tests is achievable compared to the conventional approach of using classical group testing to first identify the defective items and then pick the required number of healthy items from the complement set. For example, to identify L healthy items out of a population of N items containing K defective items, when the tests are reliable, our results show that O(K(L - 1)/(N - K)) measurements are sufficient. In contrast, the conventional approach requires O(K log(N/K)) measurements. We derive our results in a general sparse signal setup, and hence, they are applicable to other sparse signal-based applications such as compressive sensing also.