Negative-weight percolation

Abstract

We describe a percolation problem on lattices (graphs, networks), with edge weights drawn from disorder distributions that allow for weights (or distances) of either sign, i.e. including negative weights. We are interested whether there are spanning paths or loops of total negative weight. This kind of percolation problem is fundamentally different from conventional percolation problems, e.g. it does not exhibit transitivity, hence no simple definition of clusters, and several spanning paths/loops might coexist in the percolation regime at the same time. Furthermore, to study this percolation problem numerically, one has to perform a non-trivial transformation of the original graph and apply sophisticated matching algorithms. Using this approach, we study the corresponding percolation transitions on large square, hexagonal and cubic lattices for two types of disorder distributions and determine the critical exponents. The results show that negative-weight percolation is in a different universality class compared to conventional bond/site percolation. On the other hand, negative-weight percolation seems to be related to the ferromagnet/spin-glass transition of random-bond Ising systems, at least in two dimensions.

v1: 4 pages, 4 figures; v2: 10 pages, 7 figures, added results, text and references

References in corpus (12)

• Low-temperature behavior of two-dimensional Gaussian Ising spin glasses
• Critical behaviour of SU(2) lattice gauge theory. A complete analysis with the ${\chi }^2$-method
• Domain-Wall Energies and Magnetization of the Two-Dimensional Random-Bond Ising Model
• Matching Kasteleyn Cities for Spin Glass Ground States
• Kertesz Line in the Three-Dimensional Compact U(1) Lattice Higgs Model
• Fractal dimension of domain walls in two-dimensional Ising spin glasses
• Critical slowing down in polynomial time algorithms
• Percolation, Bose-Einstein Condensation, and String Proliferation
• The length distribution of vortex strings in U(1) equilibrium scalar field theory
• Disorder-Induced Topological Defects in a d=2 Elastic Medium at Zero Temperature
• Critical properties of loop percolation models with optimization constraints
• Vortex-line percolation in the three-dimensional complex |psi|^4 model

Cited by in corpus (13)

• Percolation thresholds on planar Euclidean relative neighborhood graphs
• A dedicated algorithm for calculating ground states for the triangular random bond Ising model
• Scaling behavior of domain walls at the T=0 ferromagnet to spin-glass transition
• The upper critical dimension of the negative-weight percolation problem
• Phase transitions in diluted negative-weight percolation models
• Typical and large-deviation properties of minimum-energy paths on disordered hierarchical lattices
• Is negative-weight percolation compatible with SLE?
• Mean-field behavior of the negative-weight percolation model on random regular graphs
• Configurational statistics of densely and fully packed loops in the negative-weight percolation model
• Analysis of the loop length distribution for the negative weight percolation problem in dimensions d=2 through 6
• Biased and greedy random walks on two-dimensional lattices with quenched randomness: the "greedy" ant within a disordered environment
• Directed negative-weight percolation
• Exact Ground States of the Kaya-Berker Model