Subexponential Algorithm for d-Cluster Edge Deletion: Exception or Rule?

The correlation clustering problem is a fundamental problem in both theory and practice, and it involves identifying clusters of objects in a data set based on their similarity. A traditional modeling of this question as a graph theoretic problem involves associating vertices with data points and indicating similarity by adjacency. Clusters then correspond to cliques in the graph. The resulting optimization problem, Cluster Editing (and several variants) are very well-studied algorithmically. In many situations, however, translating clusters to cliques can be somewhat restrictive. A more flexible notion would be that of a structure where the vertices are mutually ``not too far apart'', without necessarily being adjacent. One such generalization is realized by structures called s-clubs, which are graphs of diameter at most s. In this work, we study the question of finding a set of at most k edges whose removal leaves us with a graph whose components are s-clubs. Recently, it has been shown that unless Exponential Time Hypothesis fail (ETH) fails Cluster Editing (whose components are 1-clubs) does not admit sub-exponential time algorithm STACS, 2013]. That is, there is no algorithm solving the problem in time 2 degrees((k))n(O(1)). However, surprisingly they show that when the number of cliques in the output graph is restricted to d, then the problem can be solved in time O(2(O(root dk)) + m + n). We show that this sub-exponential time algorithm for the fixed number of cliques is rather an exception than a rule. Our first result shows that assuming the ETH, there is no algorithm solving the s-Club Cluster Edge Deletion problem in time 2 degrees((k))n(O(1)). We show, further, that even the problem of deleting edges to obtain a graph with d s-clubs cannot be solved in time 2 degrees((k))n(O)(1) for any fixed s, d >= 2. This is a radical contrast from the situation established for cliques, where sub-exponential algorithms are known.

BELIEF PROPAGATION FOR OPTIMAL EDGE COVER IN THE RANDOM COMPLETE GRAPH

We apply the objective method of Aldous to the problem of finding the minimum-cost edge cover of the complete graph with random independent and identically distributed edge costs. The limit, as the number of vertices goes to infinity, of the expected minimum cost for this problem is known via a combinatorial approach of Hessler and Wastlund. We provide a proof of this result using the machinery of the objective method and local weak convergence, which was used to prove the (2) limit of the random assignment problem. A proof via the objective method is useful because it provides us with more information on the nature of the edge's incident on a typical root in the minimum-cost edge cover. We further show that a belief propagation algorithm converges asymptotically to the optimal solution. This can be applied in a computational linguistics problem of semantic projection. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worst-case settings.

Local disorder investigation in NiS2-xSex using Raman and Ni K-edge x-ray absorption spectroscopies

We report on Raman and Ni K-edge x-ray absorption investigations of a NiS2-xSex (with x = 0.00, 0.50/0.55, 0.60, and 1.20) pyrite family. The Ni K-edge absorption edge shows a systematic shift going from an insulating phase (x = 0.00 and 0.50) to a metallic phase (x = 0.60 and 1.20). The near-edge absorption features show a clear evolution with Se doping. The extended x-ray absorption fine structure data reveal the evolution of the local structure with Se doping which mainly governs the local disorder. We also describe the decomposition of the NiS2-xSex Raman spectra and investigate the weights of various phonon modes using Gaussian and Lorentzian profiles. The effectiveness of the fitting models in describing the data is evaluated by means of Bayes factor estimation. The Raman analysis clearly demonstrates the disorder effects due to Se alloying in describing the phonon spectra of NiS2-xSex pyrites.

Flexibility in flapping foil suppresses meandering of induced jet in absence of free stream

Thrust-generating flapping foils are known to produce jets inclined to the free stream at high Strouhal numbers St = fA/U-infinity, where f is the frequency and A is the amplitude of flapping and U-infinity is the free-stream velocity. Our experiments, in the limiting case of St —> infinity (zero free-stream speed), show that a purely oscillatory pitching motion of a chordwise flexible foil produces a coherent jet composed of a reverse Benard-Karman vortex street along the centreline, albeit over a specific range of effective flap stiffnesses. We obtain flexibility by attaching a thin flap to the trailing edge of a rigid NACA0015 foil; length of flap is 0.79 c where c is rigid foil chord length. It is the time-varying deflections of the flexible flap that suppress the meandering found in the jets produced by a pitching rigid foil for zero free-stream condition. Recent experiments (Marais et al., J. Fluid Mech., vol. 710, 2012, p. 659) have also shown that the flexibility increases the St at which non-deflected jets are obtained. Analysing the near-wake vortex dynamics from flow visualization and particle image velocimetry (PIV) measurements, we identify the mechanisms by which flexibility suppresses jet deflection and meandering. A convenient characterization of flap deformation, caused by fluid-flap interaction, is through a non-dimensional effective stiffness', EI* = 8 EI/(rho V-TEmax(2) s(f) c(f)(3)/2), representing the inverse of the flap deflection due to the fluid-dynamic loading; here, EI is the bending stiffness of flap, rho is fluid density, V-TEmax is the maximum velocity of rigid foil trailing edge, s(f) is span and c(f) is chord length of the flexible flap. By varying the amplitude and frequency of pitching, we obtain a variation in EI* over nearly two orders of magnitude and show that only moderate EI*. (0.1 less than or similar to EI * less than or similar to 1 generates a sustained, coherent, orderly jet. Relatively `stiff' flaps (EI* greater than or similar to 1), including the extreme case of no flap, produce meandering jets, whereas highly `flexible' flaps (EI* less than or similar to 0.1) produce spread-out jets. Obtained from the measured mean velocity fields, we present values of thrust coefficients for the cases for which orderly jets are observed.

Long range emission enhancement and anisotropy in coupled quantum dots induced by aligned gold nanoantenna

Quantum dot arrays have been projected as the material of choice for next generation displays and photodetectors. Extensive ongoing research aims at improving optical and electrical efficiencies of such devices. We report experimental results on non-local long range emission intensity enhancement and anisotropy in quantum dot assemblies induced by isolated and partially aligned gold nanoantennas. Spatially resolved photoluminescence clearly demonstrate that the effect is maximum, when the longitudinal surface plasmon resonance of the nanoantenna is resonant with the emission maxima of the quantum dots. We estimated the decay length of this enhancement to be similar to 2.6 mu m, which is considerably larger than the range of near field interaction of metal nanoantenna. Numerical simulations qualitatively capture the near field behavior of the nanorods but fail to match the experimentally observed non-local effects. We have suggested how strong interactions of quantum dots in the close packed assemblies, mediated by the nanoantennas, could lead to such observed behavior. (C) 2014 AIP Publishing LLC.

Effect of functional groups on separating carbon dioxide from CO2/N-2 gas mixtures using edge functionalized graphene nanoribbons

Development of microporous adsorbents for separation and sequestration of carbon dioxide from flue gas streams is an area of active research. In this study, we assess the influence of specific functional groups on the adsorption selectivity of CO2/N-2 mixtures through Grand Canonical Monte Carlo (GCMC) simulations. Our model system consists of a bilayer graphene nanoribbon that has been edge functionalized with OH, NH2, NO2, CH3 and COOH. Ab initio Moller-Plesset (MP2) calculations with functionalized benzenes are used to obtain binding energies and optimized geometries for CO2 and N-2. This information is used to validate the choice classical forcefields in GCMC simulations. In addition to simulations of adsorption from binary mixtures of CO2 and N-2, the ideal adsorbed solution theory (IAST) is used to predict mixture isotherms. Our study reveals that functionalization always leads to an increase in the adsorption of both CO2 and N-2 with the highest for COOH. However, significant enhancement in the selectivity for CO2 is only seen with COOH functionalized nanoribbons. The COOH functionalization gives a 28% increase in selectivity compared to H terminated nanoribbons, whereas the improvement in the selectivity for other functional groups are much Enure modest. Our study suggests that specific functionalization with COOH groups can provide a material's design strategy to improve CO2 selectivity in microporous adsorbents. Synthesis of graphene nanoplatelets with edge functionalized COOH, which has the potential for large scale production, has recently been reported (Jeon el, al., 2012). (C) 2014 Elsevier Ltd. All rights reserved,

On flame-turbulence interaction in constant-pressure expanding flames

In this paper we present one of the first high-speed particle image velocimetry measurements to quantify flame-turbulence interaction in centrally-ignited constant-pressure premixed flames expanding in nearisotropic turbulence. Measurements of mean flow velocity and rms of fluctuating flow velocity are provided over a range of conditions both in the presence and absence of the flame. The distributions of stretch rate contributions from different terms such as tangential straining, normal straining and curvature are also provided. It is found that the normal straining displays non-Gaussian pdf tails whereas the tangential straining shows near Gaussian behavior. We have further tracked the motion of the edge points that reside and co-move with the edge of the flame kernel during its evolution in time, and found that within the measurement conditions, on average the persistence time scales of stretch due to pure curvature exceed that due to tangential straining by at least a factor of two. (C) 2014 The Combustion Institute. Published by Elsevier Inc. All rights reserved.

Rainbow matchings in strongly edge-colored graphs

A rainbow matching of an edge-colored graph G is a matching in which no two edges have the same color. There have been several studies regarding the maximum size of a rainbow matching in a properly edge-colored graph G in terms of its minimum degree 3(G). Wang (2011) asked whether there exists a function f such that a properly edge-colored graph G with at least f (delta(G)) vertices is guaranteed to contain a rainbow matching of size delta(G). This was answered in the affirmative later: the best currently known function Lo and Tan (2014) is f(k) = 4k - 4, for k >= 4 and f (k) = 4k - 3, for k <= 3. Afterwards, the research was focused on finding lower bounds for the size of maximum rainbow matchings in properly edge-colored graphs with fewer than 4 delta(G) - 4 vertices. Strong edge-coloring of a graph G is a restriction of proper edge-coloring where every color class is required to be an induced matching, instead of just being a matching. In this paper, we give lower bounds for the size of a maximum rainbow matching in a strongly edge-colored graph Gin terms of delta(G). We show that for a strongly edge-colored graph G, if |V(G)| >= 2 |3 delta(G)/4|, then G has a rainbow matching of size |3 delta(G)/4|, and if |V(G)| < 2 |3 delta(G)/4|, then G has a rainbow matching of size |V(G)|/2] In addition, we prove that if G is a strongly edge-colored graph that is triangle-free, then it contains a rainbow matching of size at least delta(G). (C) 2015 Elsevier B.V. All rights reserved.

Mixed Mode Analysis of Obliquely Oriented Edge Cracked Semicircular Disk Under Compression

A new mixed-mode compression fracture specimen, obliquely oriented edge cracked semicircular disk (OECSD) is analyzed by extending pure opening mode configuration of edge cracked semicircular disk (ECSD) under Hertzian compression. Photoelastic experiments are conducted on two different specimens of OECSD of same size and different crack lengths and inclinations. Finite element method (FEM) is used to solve a number of cases of the problem varying crack length and crack inclination. FE results show a good match with experiments. Inclination of edge crack in OECSD can be so made as to obtain any mode-mixity ratio between zero and one and beyond for any crack length. The new specimen can be used for fracture testing under compression more conveniently than the existing ones in several ways.

Orientational order as the origin of the long-range hydrophobic effect

The long range attractive force between two hydrophobic surfaces immersed in water is observed to decrease exponentially with their separation-this distance-dependence of effective force is known as the hydrophobic force law (HFL). We explore the microscopic origin of HFL by studying distance-dependent attraction between two parallel rods immersed in 2D Mercedes Benz model of water. This model is found to exhibit a well-defined HFL. Although the phenomenon is conventionally explained by density-dependent theories, we identify orientation, rather than density, as the relevant order parameter. The range of density variation is noticeably shorter than that of orientational heterogeneity. The latter is comparable to the observed distances of hydrophobic force. At large separation, attraction between the rods arises primarily from a destructive interference among the inwardly propagating oppositely oriented heterogeneity generated in water by the two rods. As the rods are brought closer, the interference increases leading to a decrease in heterogeneity and concomitant decrease in free energy of the system, giving rise to the effective attraction. We notice formation of hexagonal ice-like structures at the onset of attractive region which suggests that metastable free energy minimum may play a role in the origin of HFL. (C) 2015 AIP Publishing LLC.

HCN channels enhance spike phase coherence and regulate the phase of spikes and LFPs in the theta-frequency range

What are the implications for the existence of subthreshold ion channels, their localization profiles, and plasticity on local field potentials (LFPs)? Here, we assessed the role of hyperpolarization-activated cyclic-nucleotide-gated (HCN) channels in altering hippocampal theta-frequency LFPs and the associated spike phase. We presented spatiotemporally randomized, balanced theta-modulated excitatory and inhibitory inputs to somatically aligned, morphologically realistic pyramidal neuron models spread across a cylindrical neuropil. We computed LFPs from seven electrode sites and found that the insertion of an experimentally constrained HCN-conductance gradient into these neurons introduced a location- dependent lead in the LFP phase without significantly altering its amplitude. Further, neurons fired action potentials at a specific theta phase of the LFP, and the insertion of HCN channels introduced large lags in this spike phase and a striking enhancement in neuronal spike-phase coherence. Importantly, graded changes in either HCN conductance or its half-maximal activation voltage resulted in graded changes in LFP and spike phases. Our conclusions on the impact of HCN channels on LFPs and spike phase were invariant to changes in neuropil size, to morphological heterogeneity, to excitatory or inhibitory synaptic scaling, and to shifts in the onset phase of inhibitory inputs. Finally, we selectively abolished the inductive lead in the impedance phase introduced by HCN channels without altering neuronal excitability and found that this inductive phase lead contributed significantly to changes in LFP and spike phase. Our results uncover specific roles for HCN channels and their plasticity in phase-coding schemas and in the formation and dynamic reconfiguration of neuronal cell assemblies.

Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs

Conditions for the existence of heterochromatic Hamiltonian paths and cycles in edge colored graphs are well investigated in literature. A related problem in this domain is to obtain good lower bounds for the length of a maximum heterochromatic path in an edge colored graph G. This problem is also well explored by now and the lower bounds are often specified as functions of the minimum color degree of G - the minimum number of distinct colors occurring at edges incident to any vertex of G - denoted by v(G). Initially, it was conjectured that the lower bound for the length of a maximum heterochromatic path for an edge colored graph G would be 2v(G)/3]. Chen and Li (2005) showed that the length of a maximum heterochromatic path in an edge colored graph G is at least v(G) - 1, if 1 <= v(G) <= 7, and at least 3v(G)/5] + 1 if v(G) >= 8. They conjectured that the tight lower bound would be v(G) - 1 and demonstrated some examples which achieve this bound. An unpublished manuscript from the same authors (Chen, Li) reported to show that if v(G) >= 8, then G contains a heterochromatic path of length at least 120 + 1. In this paper, we give lower bounds for the length of a maximum heterochromatic path in edge colored graphs without small cycles. We show that if G has no four cycles, then it contains a heterochromatic path of length at least v(G) - o(v(G)) and if the girth of G is at least 4 log(2)(v(G)) + 2, then it contains a heterochromatic path of length at least v(G) - 2, which is only one less than the bound conjectured by Chen and Li (2005). Other special cases considered include lower bounds for the length of a maximum heterochromatic path in edge colored bipartite graphs and triangle-free graphs: for triangle-free graphs we obtain a lower bound of 5v(G)/6] and for bipartite graphs we obtain a lower bound of 6v(G)-3/7]. In this paper, it is also shown that if the coloring is such that G has no heterochromatic triangles, then G contains a heterochromatic path of length at least 13v(G)/17)]. This improves the previously known 3v(G)/4] bound obtained by Chen and Li (2011). We also give a relatively shorter and simpler proof showing that any edge colored graph G contains a heterochromatic path of length at least (C) 2015 Elsevier Ltd. All rights reserved.

Robust design of multiple trailing edge flaps for helicopter vibration reduction: A multi-objective bat algorithm approach

The objective of this study is to determine an optimal trailing edge flap configuration and flap location to achieve minimum hub vibration levels and flap actuation power simultaneously. An aeroelastic analysis of a soft in-plane four-bladed rotor is performed in conjunction with optimal control. A second-order polynomial response surface based on an orthogonal array (OA) with 3-level design describes both the objectives adequately. Two new orthogonal arrays called MGB2P-OA and MGB4P-OA are proposed to generate nonlinear response surfaces with all interaction terms for two and four parameters, respectively. A multi-objective bat algorithm (MOBA) approach is used to obtain the optimal design point for the mutually conflicting objectives. MOBA is a recently developed nature-inspired metaheuristic optimization algorithm that is based on the echolocation behaviour of bats. It is found that MOBA inspired Pareto optimal trailing edge flap design reduces vibration levels by 73% and flap actuation power by 27% in comparison with the baseline design.

Electric field induced short range to long range structural ordering and its influence on the Eu+3 photoluminescence in the lead-free ferroelectric Na1/2Bi1/2TiO3

Eu+3 was incorporated into the lattice of a lead-free ferroelectric Na1/2Bi1/2TiO3 (NBT) as per the nominal formula Na0.5Bi0.5-xEuxTiO3. This system was investigated with regard to the Eu+3 photoluminescence (PL) and structural behaviour as a function of composition and electric field. Electric field was found to irreversibly change the features in the PL spectra and also in the x-ray diffraction patterns below the critical composition x = 0.025. Detailed analysis revealed that below the critical composition, electric field irreversibly suppresses the structural heterogeneity inherent of the host matrix NBT and brings about a long range ferroelectric state with rhombohedral (R3c) distortion. It is shown that the structural disorder on the nano-scale opens a new channel for radiative transition which manifests as a new emission line branching off from the main D-5(0)-> F-7(0) line along with a concomitant change in the relative intensity of the other crystal field induced Stark lines with different J values. The study suggests that Eu+3 luminescence can be used to probe the relative degree of field induced structural ordering in relaxor ferroelectrics and also in high performance piezoelectric alloys where electric field couples very strongly with the lattice and structural degrees of freedom. (C) 2015 AIP Publishing LLC.

Active dendrites mediate stratified gamma-range coincidence detection in hippocampal model neurons

Hippocampal pyramidal neurons exhibit gamma-phase preference in their spikes, selectively route inputs through gamma frequency multiplexing and are considered part of gamma-bound cell assemblies. How do these neurons exhibit gamma-frequency coincidence detection capabilities, a feature that is essential for the expression of these physiological observations, despite their slow membrane time constant? In this conductance-based modelling study, we developed quantitative metrics for the temporal window of integration/coincidence detection based on the spike-triggered average (STA) of the neuronal compartment. We employed these metrics in conjunction with quantitative measures for spike initiation dynamics to assess the emergence and dependence of coincidence detection and STA spectral selectivity on various ion channel combinations. We found that the presence of resonating conductances (hyperpolarization-activated cyclic nucleotide-gated or T-type calcium), either independently or synergistically when expressed together, led to the emergence of spectral selectivity in the spike initiation dynamics and a significant reduction in the coincidence detection window (CDW). The presence of A-type potassium channels, along with resonating conductances, reduced the STA characteristic frequency and broadened the CDW, but persistent sodium channels sharpened the CDW by strengthening the spectral selectivity in the STA. Finally, in a morphologically precise model endowed with experimentally constrained channel gradients, we found that somatodendritic compartments expressed functional maps of strong theta-frequency selectivity in spike initiation dynamics and gamma-range CDW. Our results reveal the heavy expression of resonating and spike-generating conductances as the mechanism underlying the robust emergence of stratified gamma-range coincidence detection in the dendrites of hippocampal and cortical pyramidal neurons.