Subdivisions,parity and well-covered graphs

A graph is well-covered if every maximal independent set is maximum. This concept, introduced by Plummer in 1970 (J. Combin. Theory 8 (1970)), is the focal point of much interest and current research. We consider well-covered 2-degenerate graphs and supply a structural (and polynomial time algorithm) characterization of the class called 3-separable graphs. Also we consider parity graphs studied by Finbow and Hartnell and answer the question posed by them (Ars. Combin. 40 (1995)) by proving, among other results, that the decision problem: “given a graph G which is a parity graph, is G also well-covered graph?” is in the class CO-NPC. In addition we supply some complexity results that answer some problems due to Plummer (Quaestiones Math. 16 (1993)) and Finbow, Hartnell, and Whitehead (Discrete Math. 125 (1994)). © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 85–94, 1997     

Asymptotics of Weil–Petersson Geodesics I: Ending Laminations, Recurrence, and Flows

We define an ending lamination for a Weil–Petersson geodesic ray. Despite the lack of a natural visual boundary for the Weil–Petersson metric [Bro2], these ending laminations provide an effective boundary theory that encodes much of its asymptotic CAT(0) geometry. In particular, we prove an ending lamination theorem (Theorem 1.1) for the full-measure set of rays that recur to the thick part, and we show that the association of an ending lamination embeds asymptote classes of recurrent rays into the Gromov-boundary of the curve complex C(S){\mathcal{C}(S)}. As an application, we establish fundamentals of the topological dynamics of the Weil–Petersson geodesic flow, showing density of closed orbits and topological transitivity.     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .     

Analysis of multi-configuration density functional theory methods: theory and model application to bond-breaking

We consider the extension of the standard single-determinant Kohn–Sham method to the case of a multi-configuration auxiliary wave function. By applying the rigorous Kohn–Sham method to this case, we construct the proper interacting and auxiliary energy functionals. Following the Hohenberg–Kohn theorem for both energy functionals, we derive the corresponding multi-configuration Kohn–Sham equations, based on a local effective potential. At the end of the analysis we show that, at the ground state, the auxiliary wavefunction must collapse into a single-determinant wave function, equal to the regular KS wavefunction. We also discuss the stability of the wavefunction in multi-configuration density functional theory methods where the auxiliary system is partially interacting, and the remaining (residual) correlation is evaluated as a functional of the density. As an example showing both the challenges and the possibilities, we implement such a procedure for the perfect pairing wavefunction, using a residual correlation functional that is based on the Lee–Yang–Parr functional, and present results for an elementary bond-breaking process.     

Finding the projection of a point onto the intersection of convex sets via projections onto half-spaces

We present a modification of Dykstra's algorithm which allows us to avoid projections onto general convex sets. Instead, we calculate projections onto either a half-space or onto the intersection of two half-spaces. Convergence of the algorithm is established and special choices of the half-spaces are proposed.The option to project onto half-spaces instead of general convex sets makes the algorithm more practical. The fact that the half-spaces are quite general enables us to apply the algorithm in a variety of cases and to generalize a number of known projection algorithms.The problem of projecting a point onto the intersection of closed convex sets receives considerable attention in many areas of mathematics and physics as well as in other fields of science and engineering such as image reconstruction from projections.In this work we propose a new class of algorithms which allow projection onto certain super half-spaces, i.e., half-spaces which contain the convex sets. Each one of the algorithms that we present gives the user freedom to choose the specific super half-space from a family of such half-spaces. Since projecting a point onto a half-space is an easy task to perform, the new algorithms may be more useful in practical situations in which the construction of the super half-spaces themselves is not too difficult.     

Understanding the Role of Alumina (Al2O3), Pentalithium Aluminate (Li5AlO4), and Pentasodium Aluminate (Na5AlO4) Coatings on the Li and Mn-Rich NCM Cathode Material 0.33Li2MnO3·0.67Li(Ni0.4Co0.2Mn0.4)O2 for Enhanced Electrochemical Performance

The active role of alumina, pentalithium aluminate (Li₅AlO₄, Li-aluminate), and pentasodium aluminate (Na₅AlO₄, Na-aluminate) as the surface protection coatings produced via atomic layer deposition on Li and Mn-rich NCM cathode materials 0.33Li₂MnO₃·0.67LiNi_0.4Co_0.2Mn_0.4O₂ is discussed. A notable improvement in the electrochemical behavior of the coated cathodes has been found while tested in Li-coin cells at 30 °C. Though all the coated cathodes demonstrate enhanced electrochemical cycling and rate performances, Na-aluminate coated cathodes exhibit exemplary behavior. Prolonged cycling and rate capability testing demonstrate that after more than 400 cycles at 1 C rate, the uncoated cathode delivers only 63 mAh g⁻¹, while those with alumina, Li-aluminate, and Na-aluminate coatings exhibit approximately two times higher specific capacities. The coated cathodes display steady average discharge potential and lower evolution of the voltage hysteresis during prolonged cycling compared to the uncoated cathode. Importantly, Na-aluminate coated cathode shows a lowering in gases (O₂, CO₂, H₂, etc.) evolution. Post-cycling analysis of the electrodes demonstrates higher morphological integrity of the coated cathode materials and lower transition metals dissolution from them. The coatings mitigate undesirable side reactions between the electrodes and the electrolyte solution in the cells.     

A multiprojection algorithm using Bregman projections in a product space

Generalized distances give rise to generalized projections into convex sets. An important question is whether or not one can use within the same projection algorithm different types of such generalized projections. This question has practical consequences in the area of signal detection and image recovery in situations that can be formulated mathematically as a convex feasibility problem. Using an extension of Pierra's product space formalism, we show here that a multiprojection algorithm converges. Our algorithm is fully simultaneous, i.e., it uses in each iterative stepall sets of the convex feasibility problem. Different multiprojection algorithms can be derived from our algorithmic scheme by a judicious choice of the Bregman functions which govern the process. As a by-product of our investigation we also obtain blockiterative schemes for certain kinds of linearly constraned optimization problems.     

Sensing of Alkylating Agents Using Organic Field‐Effect Transistors

Alkylating agents are simple and reactive molecules that are commonly used in many and diverse fields, such as organic synthesis, medicine, and agriculture. Some highly reactive alkylating species are also being used as blister chemical warfare agents. The detection and identification of alkylating agent is not a trivial issue because of their high reactivity and simple structure. Here, a novel polythiophene derivative that is capable of reacting with alkylating agents is reported, along with its application in direct electrical sensing of alkylators using an organic field‐effect transistor, OFET, device. Upon reacting with alkylators, the OFET containing the new polythiophene analogue as its channel becomes conductive, and the gate effect is lost; this is in marked contrast to the response of the OFET to “innocent” vapors, such as alcohols and acetone. By following the drain–source current under gate bias, one can easily follow the processes of absorption of the analyte to the polythiophene channel and their subsequent reaction.     

Reversible Thermal Tuning of All‐Dielectric Metasurfaces

All‐dielectric metasurfaces provide a powerful platform for a new generation of flat optical devices, in particular, for applications in telecommunication systems, due to their low losses and high transparency in the infrared. However, active and reversible tuning of such metasurfaces remains a challenge. This study experimentally demonstrates and theoretically justifies a novel scenario of the dynamical reversible tuning of all‐dielectric metasurfaces based on the temperature‐dependent change of the refractive index of silicon. How to design an all‐dielectric metasurface with sharp resonances by achieving interference between magnetic dipole and electric quadrupole modes of constituted nanoparticles arranged in a 2D lattice is shown. Thermal tuning of these resonances can cause drastic but reciprocal changes in the directional scattering of the metasurface in a spectral window of 75 nm. This change can result in a 50‐fold enhancement of the radiation directionality. This type of reversible tuning can play a significant role in novel flat optical devices including the metalenses and metaholograms.     

Authenticated Adversarial Routing

The aim of this paper is to demonstrate the feasibility of authenticated throughput-efficient routing in an unreliable and dynamically changing synchronous network in which the majority of malicious insiders try to destroy and alter messages or disrupt communication in any way. More specifically, in this paper we seek to answer the following question: Given a network in which the majority of nodes are controlled by a node-controlling adversary and whose topology is changing every round, is it possible to develop a protocol with polynomially bounded memory per processor (with respect to network size) that guarantees throughput-efficient and correct end-to-end communication? We answer the question affirmatively for extremely general corruption patterns: we only request that the topology of the network and the corruption pattern of the adversary leaves at least one path each round connecting the sender and receiver through honest nodes (though this path may change at every round). Out construction works in the public-key setting and enjoys optimal transfer rate and bounded memory per processor (that is polynomial in the network size and does not depend on the amount of traffic). We stress that our protocol assumes no knowledge of which nodes are corrupted nor which path is reliable at any round, and is also fully distributed with nodes making decisions locally, so that they need not know the topology of the network at any time. The optimality that we prove for our protocol is very strong. Given any routing protocol, we evaluate its efficiency (rate of message delivery) in the “worst case,” that is with respect to the worst possible graph and against the worst possible (polynomially bounded) adversarial strategy (subject to the above mentioned connectivity constraints). Using this metric, we show that there does not exist any protocol that can be asymptotically superior (in terms of throughput) to ours in this setting. We remark that the aim of our paper is to demonstrate via explicit example the feasibility of throughput-efficient authenticated adversarial routing. However, we stress that out protocol is not intended to provide a practical solution, as due to its complexity, no attempt thus far has been made to reduce constants and memory requirements. Our result is related to recent work of Barak et al. (Proc. of Advances in Cryptology—27th EUROCRYPT 2008, LNCS, vol. 4965, pp. 341–360, 2008) who studied fault localization in networks assuming a private-key trusted-setup setting. Our work, in contrast, assumes a public-key PKI setup and aims at not only fault localization, but also transmission optimality. Among other things, our work answers one of the open questions posed in the Barak et al. paper regarding fault localization on multiple paths. The use of a public-key setting to achieve strong error-correction results in networks was inspired by the work of Micali et al. (Proc. of 2nd Theory of Cryptography Conf., LNCS, vol. 3378, pp. 1–16, 2005) who showed that classical error correction against a polynomially bounded adversary can be achieved with surprisingly high precision. Our work is also related to an interactive coding theorem of Rajagopalan and Schulman (Proc. 26th ACM Symp. on Theory of Computing, pp. 790–799, 1994) who showed that in noisy-edge static-topology networks a constant overhead in communication can also be achieved (provided none of the processors are malicious), thus establishing an optimal-rate routing theorem for static-topology networks. Finally, our work is closely related and builds upon to the problem of End-To-End Communication in distributed networks, studied by Afek and Gafni (Proc. of the 7th ACM Symp. on Principles of Distributed Computing, pp. 131–148, 1988); Awebuch et al. (Proc. of the 30th IEEE Symp. on Foundations of Computer Science, FOCS, 1989); Afek et al. (Proc. of the 11th ACM Symp. on Principles of Distributed Computing, pp. 35–46, 1992); and Afek et al. (J. Algorithms 22:158–186, 1997), though none of these papers consider or ensure correctness in the setting of a node-controlling adversary that may corrupt the majority of the network.