Badly approximable numbers and vectors in Cantor-like sets

We show that a large class of Cantor-like sets of R-d, d >= 1, contains uncountably many badly approximable numbers, respectively badly approximable vectors, when d >= 2. An analogous result is also proved for subsets of R-d arising in the study of geodesic flows corresponding to (d+1)-dimensional manifolds of constant negative curvature and finite volume, generalizing the set of badly approximable numbers in R. Furthermore, we describe a condition on sets, which is fulfilled by a large class, ensuring a large intersection with these Cantor-like sets.

Methods for Detecting Early Warnings of Critical Transitions in Time Series Illustrated Using Simulated Ecological Data

Many dynamical systems, including lakes, organisms, ocean circulation patterns, or financial markets, are now thought to have tipping points where critical transitions to a contrasting state can happen. Because critical transitions can occur unexpectedly and are difficult to manage, there is a need for methods that can be used to identify when a critical transition is approaching. Recent theory shows that we can identify the proximity of a system to a critical transition using a variety of so-called `early warning signals', and successful empirical examples suggest a potential for practical applicability. However, while the range of proposed methods for predicting critical transitions is rapidly expanding, opinions on their practical use differ widely, and there is no comparative study that tests the limitations of the different methods to identify approaching critical transitions using time-series data. Here, we summarize a range of currently available early warning methods and apply them to two simulated time series that are typical of systems undergoing a critical transition. In addition to a methodological guide, our work offers a practical toolbox that may be used in a wide range of fields to help detect early warning signals of critical transitions in time series data.

Rainbow connection number and connected dominating sets

The rainbow connection number of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on n vertices with minimum degree delta, the rainbow connection number is upper bounded by 3n/(delta + 1) + 3. This solves an open problem from Schiermeyer (Combinatorial Algorithms, Springer, Berlin/Hiedelberg, 2009, pp. 432437), improving the previously best known bound of 20n/delta (J Graph Theory 63 (2010), 185191). This bound is tight up to additive factors by a construction mentioned in Caro et al. (Electr J Combin 15(R57) (2008), 1). As an intermediate step we obtain an upper bound of 3n/(delta + 1) - 2 on the size of a connected two-step dominating set in a connected graph of order n and minimum degree d. This bound is tight up to an additive constant of 2. This result may be of independent interest. We also show that for every connected graph G with minimum degree at least 2, the rainbow connection number, rc(G), is upper bounded by Gc(G) + 2, where Gc(G) is the connected domination number of G. Bounds of the form diameter(G)?rc(G)?diameter(G) + c, 1?c?4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree delta at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G)?3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds.

Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n(3))-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n(4))-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs. (C) 2012 Elsevier B.V. All rights reserved.

A numerical approach to determine the sufficiency of given boundary data sets for uniquely estimating interior elastic properties

We consider an inverse elasticity problem in which forces and displacements are known on the boundary and the material property distribution inside the body is to be found. In other words, we need to estimate the distribution of constitutive properties using the finite boundary data sets. Uniqueness of the solution to this problem is proved in the literature only under certain assumptions for a given complete Dirichlet-to-Neumann map. Another complication in the numerical solution of this problem is that the number of boundary data sets needed to establish uniqueness is not known even under the restricted cases where uniqueness is proved theoretically. In this paper, we present a numerical technique that can assess the sufficiency of given boundary data sets by computing the rank of a sensitivity matrix that arises in the Gauss-Newton method used to solve the problem. Numerical experiments are presented to illustrate the method.

Antibodies against the extracellular domain of human Notch1 receptor reveal the critical role of epidermal-growth-factor-like repeats 25-26 in ligand binding and receptor activation

The Notch signalling pathway is implicated in a wide variety of cellular processes throughout metazoan development. Although the downstream mechanism of Notch signalling has been extensively studied, the details of its ligand-mediated receptor activation are not clearly understood. Although the role of Notch ELRs EGF (epidermal growth factor)-like-repeats] 11-12 in ligand binding is known, recent studies have suggested interactions within different ELRs of the Notch receptor whose significance remains to be understood. Here, we report critical inter-domain interactions between human Notch1 ELRs 21-30 and the ELRs 11-15 that are modulated by calcium. Surface plasmon resonance analysis revealed that the interaction between ELRs 21-30 and ELRs 11-15 is similar to 10-fold stronger than that between ELRs 11-15 and the ligands. Although there was no interaction between Notch 1 ELRs 21-30 and the ligands in vitro, addition of pre-clustered Jagged1Fc resulted in the dissociation of the preformed complex between ELRs 21-30 and 11-15, suggesting that inter-domain interactions compete for ligand binding. Furthermore, the antibodies against ELRs 21-30 inhibited ligand binding to the full-length Notch1 and subsequent receptor activation, with the antibodies against ELRs 25-26 being the most effective. These results suggest that the ELRs 25-26 represent a cryptic ligand-binding site which becomes exposed only upon the presence of the ligand. Thus, using specific antibodies against various domains of the Notch1 receptor, we demonstrate that, although ELRs 11-12 are the principal ligand-binding site, the ELRs 25-26 serve as a secondary binding site and play an important role in receptor activation.

InSt: an integrated steering framework for critical weather applications

Online remote visualization and steering of critical weather applications like cyclone tracking are essential for effective and timely analysis by geographically distributed climate science community. A steering framework for controlling the high-performance simulations of critical weather events needs to take into account both the steering inputs of the scientists and the criticality needs of the application including minimum progress rate of simulations and continuous visualization of significant events. In this work, we have developed an integrated user-driven and automated steering framework InSt for simulations, online remote visualization, and analysis for critical weather applications. InSt provides the user control over various application parameters including region of interest, resolution of simulation, and frequency of data for visualization. Unlike existing efforts, our framework considers both the steering inputs and the criticality of the application, namely, the minimum progress rate needed for the application, and various resource constraints including storage space and network bandwidth to decide the best possible parameter values for simulations and visualization.

The curvature of the liquid-vapor reduced pressure curve and its relation with the critical region

For most fluids, there exist a maximum and a minimum in the curvature of the reduced vapor pressure curve, p(r) = p(r)(T-r) (with p(r) = p/p(c) and T-r = T/T-c, p(c) and T-c being the pressure and temperature at the critical point). By analyzing National Institute of Standards and Technology (NIST) data on the liquid-vapor coexistence curve for 105 fluids, we find that the maximum occurs in the reduced temperature range 0.5 <= T-r <= 0.8 while the minimum occurs in the reduced temperature range 0.980 <= T-r <= 0.995. Vapor pressure equations for which d(2)p(r)/dT(r)(2) diverges at the critical point present a minimum in their curvature. Therefore, the point of minimum curvature can be used as a marker for the critical region. By using the well-known Ambrose-Walton (AW) vapor pressure equation we obtain the reduced temperatures of the maximum and minimum curvature in terms of the Pitzer acentric factor. The AW predictions are checked against those obtained from NIST data. (C) 2013 Elsevier Ltd. All rights reserved.

Benchmarking recognition results on camera captured word image data sets

We have benchmarked the maximum obtainable recognition accuracy on five publicly available standard word image data sets using semi-automated segmentation and a commercial OCR. These images have been cropped from camera captured scene images, born digital images (BDI) and street view images. Using the Matlab based tool developed by us, we have annotated at the pixel level more than 3600 word images from the five data sets. The word images binarized by the tool, as well as by our own midline analysis and propagation of segmentation (MAPS) algorithm are recognized using the trial version of Nuance Omnipage OCR and these two results are compared with the best reported in the literature. The benchmark word recognition rates obtained on ICDAR 2003, Sign evaluation, Street view, Born-digital and ICDAR 2011 data sets are 83.9%, 89.3%, 79.6%, 88.5% and 86.7%, respectively. The results obtained from MAPS binarized word images without the use of any lexicon are 64.5% and 71.7% for ICDAR 2003 and 2011 respectively, and these values are higher than the best reported values in the literature of 61.1% and 41.2%, respectively. MAPS results of 82.8% for BDI 2011 dataset matches the performance of the state of the art method based on power law transform.

Covariance profiles: a signature representation for object sets

We consider the problem of extracting a signature representation of similar entities employing covariance descriptors. Covariance descriptors can efficiently represent objects and are robust to scale and pose changes. We posit that covariance descriptors corresponding to similar objects share a common geometrical structure which can be extracted through joint diagonalization. We term this diagonalizing matrix as the Covariance Profile (CP). CP can be used to measure the distance of a novel object to an object set through the diagonality measure. We demonstrate how CP can be employed on images as well as for videos, for applications such as face recognition and object-track clustering.

Critical investigation on hydrogen bonding by Fourier transform infrared spectroscopy in hydrogenated amorphous silicon thin films

Fourier Transform Infrared (FTIR) spectroscopic analysis has been carried out on the hydrogenated amorphous silicon (a-Si:H) thin films deposited by DC, pulsed DC (PDC) and RF sputtering process to get insight regarding the total hydrogen concentration (C-H) in the films, configuration of hydrogen bonding, density of the films (decided by the vacancy and void incorporation) and the microstructure factor (R*) which varies with the type of sputtering carried out at the same processing conditions. The hydrogen incorporation is found to be more in RF sputter deposited films as compared to PDC and DC sputter deposited films. All the films were broadly divided into two regions namely vacancy dominated and void dominated regions. At low hydrogen dilutions the films are vacancy dominated and at high hydrogen dilutions they are void dominated. This demarcation is at C-H = 23 at.% H for RF, C-H = 18 at.% H for PDC and C-H = 14 at.% H for DC sputter deposited films. The microstructure structure factor R* is found to be as low as 0.029 for DC sputter deposited films at low C-H. For a given C-H, DC sputter deposited films have low R* as compared to PDC and RF sputter deposited films. Signature of dihydride incorporation is found to be more in DC sputter deposited films at low C-H.

Multiwalled-carbon-nanotube-induced miscibility in near-critical PS/PVME blends: assessment through concentration fluctuations and segmental relaxation

The effects of multiwalled carbon nanotubes (MWNTs) on the concentration fluctuations, interfacial driven elasticity, phase morphology, and local segmental dynamics of chains for near-critical compositions of polystyrene/poly(vinyl to methyl ether) (PS/PVME) blends were systematically investigated using dynamic shear rheology and dielectric spectroscopy. The contribution of the correlation length (xi) of the concentration fluctuations to the evolving stresses was monitored in situ to probe the different stages of demixing in the blends. The classical upturn in the dynamic moduli was taken as the rheological demixing temperature (T-rheo), which was also observed to be in close agreement with those obtained using concentration fluctuation variance, <(delta phi)(2)>, versus temperature curves. Further, Fredrickson and Larson's approach involving the mean-field approximation and the double-reptation self-concentration (DRSC) model was employed to evaluate the spinodal decomposition temperature (T-s). Interestingly, the values of both T-rheo and T-s shifted upward in the blends in the presence of MWNTs, manifesting in molecular-level miscibility. These phenomenal changes were further observed to be a function of the concentration of MWNTs. The evolution of morphology as a function of temperature was studied using polarized optical microscopy (POM). It was observed that PVME, which evolved as an interconnected network during the early stages of demixing, coarsened into a matrix-droplet morphology in the late stages. The preferential wetting of PVME onto MWNTs as a result of physicochemical interactions retained the interconnected network of PVME for longer time scales, as supported by POM and atomic force microscopy (AFM) images. Microscopic heterogeneity in macroscopically miscible systems was studied by dielectric relaxation spectroscopy. The slowing of segmental relaxations in PVME was observed in the presence of both ``frozen'' PS and MWNTs interestingly at temperatures much below the calorimetric glass transition temperature (T-g). This phenomenon was observed to be local rather than global and was addressed by monitoring the evolution of the relaxation spectra near and above the demixing temperature.

Mechanism design for time critical and cost critical task execution via crowdsourcing

An exciting application of crowdsourcing is to use social networks in complex task execution. In this paper, we address the problem of a planner who needs to incentivize agents within a network in order to seek their help in executing an atomic task as well as in recruiting other agents to execute the task. We study this mechanism design problem under two natural resource optimization settings: (1) cost critical tasks, where the planner's goal is to minimize the total cost, and (2) time critical tasks, where the goal is to minimize the total time elapsed before the task is executed. We identify a set of desirable properties that should ideally be satisfied by a crowdsourcing mechanism. In particular, sybil-proofness and collapse-proofness are two complementary properties in our desiderata. We prove that no mechanism can satisfy all the desirable properties simultaneously. This leads us naturally to explore approximate versions of the critical properties. We focus our attention on approximate sybil-proofness and our exploration leads to a parametrized family of payment mechanisms which satisfy collapse-proofness. We characterize the approximate versions of the desirable properties in cost critical and time critical domain.

Threats and trade-fffs in resource critical crowdsourcing tasks over networks

In recent times, crowdsourcing over social networks has emerged as an active tool for complex task execution. In this paper, we address the problem faced by a planner to incen-tivize agents in the network to execute a task and also help in recruiting other agents for this purpose. We study this mecha-nism design problem under two natural resource optimization settings: (1) cost critical tasks, where the planner’s goal is to minimize the total cost, and (2) time critical tasks, where the goal is to minimize the total time elapsed before the task is executed. We define a set of fairness properties that should beideally satisfied by a crowdsourcing mechanism. We prove that no mechanism can satisfy all these properties simultane-ously. We relax some of these properties and define their ap-proximate counterparts. Under appropriate approximate fair-ness criteria, we obtain a non-trivial family of payment mech-anisms. Moreover, we provide precise characterizations of cost critical and time critical mechanisms.