Statistics of opinion domains of the majority-vote model on a square lattice

The existence of juxtaposed regions of distinct cultures in spite of the fact that people's beliefs have a tendency to become more similar to each other's as the individuals interact repeatedly is a puzzling phenomenon in the social sciences. Here we study an extreme version of the frequency-dependent bias model of social influence in which an individual adopts the opinion shared by the majority of the members of its extended neighborhood, which includes the individual itself. This is a variant of the majority-vote model in which the individual retains its opinion in case there is a tie among the neighbors' opinions. We assume that the individuals are fixed in the sites of a square lattice of linear size L and that they interact with their nearest neighbors only. Within a mean-field framework, we derive the equations of motion for the density of individuals adopting a particular opinion in the single-site and pair approximations. Although the single-site approximation predicts a single opinion domain that takes over the entire lattice, the pair approximation yields a qualitatively correct picture with the coexistence of different opinion domains and a strong dependence on the initial conditions. Extensive Monte Carlo simulations indicate the existence of a rich distribution of opinion domains or clusters, the number of which grows with L(2) whereas the size of the largest cluster grows with ln L(2). The analysis of the sizes of the opinion domains shows that they obey a power-law distribution for not too large sizes but that they are exponentially distributed in the limit of very large clusters. In addition, similarly to other well-known social influence model-Axelrod's model-we found that these opinion domains are unstable to the effect of a thermal-like noise.

Ground-state functional for quantum spin chains with bond defects

We have developed a nonlocal functional of the exchange interaction for the ground-state energy of quantum spin chains described by the Heisenberg Hamiltonian. An alternating chain is used to obtain the correlation energy and a local unit-cell approximation is defined in the context of the density-functional theory. The agreement with our exact numerical data, for small chains, is significantly better than a previous formulation, even for chains with several ferromagnetic or antiferromagnetic bond defects. The results can be particularly relevant in the study of finite spin-1/2 Heisenberg chains, with exchange couplings changing, magnitude, or even sign, from bond-to-bond.

Spin gaps and spin-flip energies in density-functional theory

Energy gaps are crucial aspects of the electronic structure of finite and extended systems. Whereas much is known about how to define and calculate charge gaps in density-functional theory (DFT), and about the relation between these gaps and derivative discontinuities of the exchange-correlation functional, much less is known about spin gaps. In this paper we give density-functional definitions of spin-conserving gaps, spin-flip gaps and the spin stiffness in terms of many-body energies and in terms of single-particle (Kohn-Sham) energies. Our definitions are as analogous as possible to those commonly made in the charge case, but important differences between spin and charge gaps emerge already on the single-particle level because unlike the fundamental charge gap spin gaps involve excited-state energies. Kohn-Sham and many-body spin gaps are predicted to differ, and the difference is related to derivative discontinuities that are similar to, but distinct from, those usually considered in the case of charge gaps. Both ensemble DFT and time-dependent DFT (TDDFT) can be used to calculate these spin discontinuities from a suitable functional. We illustrate our findings by evaluating our definitions for the Lithium atom, for which we calculate spin gaps and spin discontinuities by making use of near-exact Kohn-Sham eigenvalues and, independently, from the single-pole approximation to TDDFT. The many-body corrections to the Kohn-Sham spin gaps are found to be negative, i.e., single-particle calculations tend to overestimate spin gaps while they underestimate charge gaps.

Nonempirical hyper-generalized-gradient functionals constructed from the Lieb-Oxford bound

A simple and completely general representation of the exact exchange-correlation functional of density-functional theory is derived from the universal Lieb-Oxford bound, which holds for any Coulomb-interacting system. This representation leads to an alternative point of view on popular hybrid functionals, providing a rationale for why they work and how they can be constructed. A similar representation of the exact correlation functional allows to construct fully nonempirical hyper-generalized-gradient approximations (HGGAs), radically departing from established paradigms of functional construction. Numerical tests of these HGGAs for atomic and molecular correlation energies and molecular atomization energies show that even simple HGGAs match or outperform state-of-the-art correlation functionals currently used in solid-state physics and quantum chemistry.

Lower Bounds on the Exchange-Correlation Energy in Reduced Dimensions

Bounds on the exchange-correlation energy of many-electron systems are derived and tested. By using universal scaling properties of the electron-electron interaction, we obtain the exponent of the bounds in three, two, one, and quasione dimensions. From the properties of the electron gas in the dilute regime, the tightest estimate to date is given for the numerical prefactor of the bound, which is crucial in practical applications. Numerical tests on various low-dimensional systems are in line with the bounds obtained and give evidence of an interesting dimensional crossover between two and one dimensions.

Reverse engineering in many-body quantum physics: Correspondence between many-body systems and effective single-particle equations

The mapping, exact or approximate, of a many-body problem onto an effective single-body problem is one of the most widely used conceptual and computational tools of physics. Here, we propose and investigate the inverse map of effective approximate single-particle equations onto the corresponding many-particle system. This approach allows us to understand which interacting system a given single-particle approximation is actually describing, and how far this is from the original physical many-body system. We illustrate the resulting reverse engineering process by means of the Kohn-Sham equations of density-functional theory. In this application, our procedure sheds light on the nonlocality of the density-potential mapping of density-functional theory, and on the self-interaction error inherent in approximate density functionals.

Physical signatures of discontinuities of the time-dependent exchange-correlation potential

The exact exchange-correlation (XC) potential in time-dependent density-functional theory (TDDFT) is known to develop steps and discontinuities upon change of the particle number in spatially confined regions or isolated subsystems. We demonstrate that the self-interaction corrected adiabatic local-density approximation for the XC potential has this property, using the example of electron loss of a model quantum well system. We then study the influence of the XC potential discontinuity in a real-time simulation of a dissociation process of an asymmetric double quantum well system, and show that it dramatically affects the population of the resulting isolated single quantum wells. This indicates the importance of a proper account of the discontinuities in TDDFT descriptions of ionization, dissociation or charge transfer processes.

Density-functional description of superconducting and magnetic proximity effects across a tunneling barrier

A density-functional formalism for superconductivity and magnetism is presented. The resulting relations unify previously derived Kohn-Sham equations for superconductors and for noncollinear magnetism. The formalism, which discriminates Cooper-pair singlets from triplets, is applied to two quantum liquids coupled by tunneling through a barrier. An exact expression is derived, relating the eigenstates and eigenvalues of the Kohn-Sham equations, unperturbed by tunneling, on one side of the barrier to the proximity-induced ordering potential on the other.

Density functional theory investigation of 3d, 4d, and 5d 13-atom metal clusters

The knowledge of the atomic structure of clusters composed by few atoms is a basic prerequisite to obtain insights into the mechanisms that determine their chemical and physical properties as a function of diameter, shape, surface termination, as well as to understand the mechanism of bulk formation. Due to the wide use of metal systems in our modern life, the accurate determination of the properties of 3d, 4d, and 5d metal clusters poses a huge problem for nanoscience. In this work, we report a density functional theory study of the atomic structure, binding energies, effective coordination numbers, average bond lengths, and magnetic properties of the 3d, 4d, and 5d metal (30 elements) clusters containing 13 atoms, M(13). First, a set of lowest-energy local minimum structures (as supported by vibrational analysis) were obtained by combining high-temperature first- principles molecular-dynamics simulation, structure crossover, and the selection of five well-known M(13) structures. Several new lower energy configurations were identified, e. g., Pd(13), W(13), Pt(13), etc., and previous known structures were confirmed by our calculations. Furthermore, the following trends were identified: (i) compact icosahedral-like forms at the beginning of each metal series, more opened structures such as hexagonal bilayerlike and double simple-cubic layers at the middle of each metal series, and structures with an increasing effective coordination number occur for large d states occupation. (ii) For Au(13), we found that spin-orbit coupling favors the three-dimensional (3D) structures, i.e., a 3D structure is about 0.10 eV lower in energy than the lowest energy known two-dimensional configuration. (iii) The magnetic exchange interactions play an important role for particular systems such as Fe, Cr, and Mn. (iv) The analysis of the binding energy and average bond lengths show a paraboliclike shape as a function of the occupation of the d states and hence, most of the properties can be explained by the chemistry picture of occupation of the bonding and antibonding states.

Transition-metal 13-atom clusters assessed with solid and surface-biased functionals

First-principles density-functional theory studies have reported open structures based on the formation of double simple-cubic (DSC) arrangements for Ru(13), Rh(13), Os(13), and Ir(13), which can be considered an unexpected result as those elements crystallize in compact bulk structures such as the face-centered cubic and hexagonal close-packed lattices. In this work, we investigated with the projected augmented wave method the dependence of the lowest-energy structure on the local and semilocal exchange-correlation (xc) energy functionals employed in density-functional theory. We found that the local-density approximation (LDA) and generalized-gradient formulations with different treatment of the electronic inhomogeneities (PBE, PBEsol, and AM05) confirm the DSC configuration as the lowest-energy structure for the studied TM(13) clusters. A good agreement in the relative total energies are obtained even for structures with small energy differences, e. g., 0.10 eV. The employed xc functionals yield the same total magnetic moment for a given structure, i.e., the differences in the bond lengths do not affect the moments, which can be attributed to the atomic character of those clusters. Thus, at least for those systems, the differences among the LDA, PBE, PBEsol, and AM05 functionals are not large enough to yield qualitatively different results. (C) 2011 American Institute of Physics. [doi: 10.1063/1.3577999]

Effective coordination concept applied for phase change (GeTe)(m)(Sb(2)Te(3))(n) compounds

In this work, we employed the effective coordination concept to study the local environments of the Ge, Sb, and Te atoms in the Ge(m)Sb(2n)Te(m+3n) compounds. From our calculations and analysis, we found an average effective coordination number (ECN) reduction of 1.59, 1.42, and 1.37, for the Ge, Sb, Te atoms in the phase transition from crystalline, ECN=5.55 (Ge), 5.73 (Sb), 4.37 (Te), to the amorphous phase, ECN=3.96 (Ge), 4.31 (Sb), 3.09 (Te), for the Ge(2)Sb(2)Te(5) composition. Similar changes are observed for other compositions. Thus, our results indicate that the coordination changes from the crystalline to amorphous phase are not large as previously assumed in the literature, i.e., from sixfold to fourfold for Ge, which can contribute to obtain a better understanding of the crystalline to amorphous phase transition. (C) 2011 American Institute of Physics. [doi:10.1063/1.3533422]

The role of electron localization in the atomic structure of transition-metal 13-atom clusters: the example of Co(13), Rh(13), and Hf(13)

The crystalline structure of transition-metals (TM) has been widely known for several decades, however, our knowledge on the atomic structure of TM clusters is still far from satisfactory, which compromises an atomistic understanding of the reactivity of TM clusters. For example, almost all density functional theory (DFT) calculations for TM clusters have been based on local (local density approximation-LDA) and semilocal (generalized gradient approximation-GGA) exchange-correlation functionals, however, it is well known that plain DFT fails to correct the self-interaction error, which affects the properties of several systems. To improve our basic understanding of the atomic and electronic properties of TM clusters, we report a DFT study within two nonlocal functionals, namely, the hybrid HSE (Heyd, Scuseria, and Ernzerhof) and GGA + U functionals, of the structural and electronic properties of the Co(13), Rh(13), and Hf(13) clusters. For Co(13) and Rh(13), we found that improved exchange-correlation functionals decrease the stability of open structures such as the hexagonal bilayer (HBL) and double simple-cubic (DSC) compared with the compact icosahedron (ICO) structure, however, DFT-GGA, DFT-GGA + U, and DFT-HSE yield very similar results for Hf(13). Thus, our results suggest that the DSC structure obtained by several plain DFT calculations for Rh(13) can be improved by the use of improved functionals. Using the sd hybridization analysis, we found that a strong hybridization favors compact structures, and hence, a correct description of the sd hybridization is crucial for the relative energy stability. For example, the sd hybridization decreases for HBL and DSC and increases for ICO in the case of Co(13) and Rh(13), while for Hf(13), the sd hybridization decreases for all configurations, and hence, it does not affect the relative stability among open and compact configurations.

On the k-restricted structure ratio in planar and outerplanar graphs

A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1/2. The same result holds for the weighted version. Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.

An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

TESTING STATISTICAL HYPOTHESIS ON RANDOM TREES AND APPLICATIONS TO THE PROTEIN CLASSIFICATION PROBLEM

Efficient automatic protein classification is of central importance in genomic annotation. As an independent way to check the reliability of the classification, we propose a statistical approach to test if two sets of protein domain sequences coming from two families of the Pfam database are significantly different. We model protein sequences as realizations of Variable Length Markov Chains (VLMC) and we use the context trees as a signature of each protein family. Our approach is based on a Kolmogorov-Smirnov-type goodness-of-fit test proposed by Balding et at. [Limit theorems for sequences of random trees (2008), DOI: 10.1007/s11749-008-0092-z]. The test statistic is a supremum over the space of trees of a function of the two samples; its computation grows, in principle, exponentially fast with the maximal number of nodes of the potential trees. We show how to transform this problem into a max-flow over a related graph which can be solved using a Ford-Fulkerson algorithm in polynomial time on that number. We apply the test to 10 randomly chosen protein domain families from the seed of Pfam-A database (high quality, manually curated families). The test shows that the distributions of context trees coming from different families are significantly different. We emphasize that this is a novel mathematical approach to validate the automatic clustering of sequences in any context. We also study the performance of the test via simulations on Galton-Watson related processes.