A linear optimization technique for graph pebbling

Graph pebbling is a network model for studying whether or not a given supply of discrete pebbles can satisfy a given demand via pebbling moves. A pebbling move across an edge of a graph takes two pebbles from one endpoint and places one pebble at the other endpoint; the other pebble is lost in transit as a toll. It has been shown that deciding whether a supply can meet a demand on a graph is NP-complete. The pebbling number of a graph is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble. Deciding if the pebbling number is at most k is NP 2 -complete. In this paper we develop a tool, called theWeight Function Lemma, for computing upper bounds and sometimes exact values for pebbling numbers with the assistance of linear optimization. With this tool we are able to calculate the pebbling numbers of much larger graphs than in previous algorithms, and much more quickly as well. We also obtain results for many families of graphs, in many cases by hand, with much simpler and remarkably shorter proofs than given in previously existing arguments (certificates typically of size at most the number of vertices times the maximum degree), especially for highly symmetric graphs. Here we apply theWeight Function Lemma to several specific graphs, including the Petersen, Lemke, 4th weak Bruhat, Lemke squared, and two random graphs, as well as to a number of infinite families of graphs, such as trees, cycles, graph powers of cycles, cubes, and some generalized Petersen and Coxeter graphs. This partly answers a question of Pachter, et al., by computing the pebbling exponent of cycles to within an asymptotically small range. It is conceivable that this method yields an approximation algorithm for graph pebbling.

Cell size distribution in a random tessellation of space governed by the Kolmogorov-Johnson-Mehl-Avrami model: Grain size distribution in crystallization

The space subdivision in cells resulting from a process of random nucleation and growth is a subject of interest in many scientific fields. In this paper, we deduce the expected value and variance of these distributions while assuming that the space subdivision process is in accordance with the premises of the Kolmogorov-Johnson-Mehl-Avrami model. We have not imposed restrictions on the time dependency of nucleation and growth rates. We have also developed an approximate analytical cell size probability density function. Finally, we have applied our approach to the distributions resulting from solid phase crystallization under isochronal heating conditions

Comparing Random-based and k-Anonymity-Based Algorithms for Graph Anonymization

Recently, several anonymization algorithms have appeared for privacy preservation on graphs. Some of them are based on random-ization techniques and on k-anonymity concepts. We can use both of them to obtain an anonymized graph with a given k-anonymity value. In this paper we compare algorithms based on both techniques in orderto obtain an anonymized graph with a desired k-anonymity value. We want to analyze the complexity of these methods to generate anonymized graphs and the quality of the resulting graphs.

Avalanches in a fluctuationless first-order phase transition in a random-bond Ising model

We study the behavior of the random-bond Ising model at zero temperature by numerical simulations for a variable amount of disorder. The model is an example of systems exhibiting a fluctuationless first-order phase transition similar to some field-induced phase transitions in ferromagnetic systems and the martensitic phase transition appearing in a number of metallic alloys. We focus on the study of the hysteresis cycles appearing when the external field is swept from positive to negative values. By using a finite-size scaling hypothesis, we analyze the disorder-induced phase transition between the phase exhibiting a discontinuity in the hysteresis cycle and the phase with the continuous hysteresis cycle. Critical exponents characterizing the transition are obtained. We also analyze the size and duration distributions of the magnetization jumps (avalanches).

Hysteresis and avalanches in the random anisotropy Ising model

ches. The critical point is characterized by a set of critical exponents, which are consistent with the universal values proposed from the study of other simpler models.

Finite-size scaling analysis of the avalanches in the three-dimensional Gaussian random-field Ising model with metastable dynamics

A numerical study is presented of the third-dimensional Gaussian random-field Ising model at T=0 driven by an external field. Standard synchronous relaxation dynamics is employed to obtain the magnetization versus field hysteresis loops. The focus is on the analysis of the number and size distribution of the magnetization avalanches. They are classified as being nonspanning, one-dimensional-spanning, two-dimensional-spanning, or three-dimensional-spanning depending on whether or not they span the whole lattice in different space directions. Moreover, finite-size scaling analysis enables identification of two different types of nonspanning avalanches (critical and noncritical) and two different types of three-dimensional-spanning avalanches (critical and subcritical), whose numbers increase with L as a power law with different exponents. We conclude by giving a scenario for avalanche behavior in the thermodynamic limit.

Spanning avalanches in the three-dimensional Gaussian random-field Ising model with metastable dynamics: Field dependence and geometrical properties

Spanning avalanches in the 3D Gaussian Random Field Ising Model (3D-GRFIM) with metastable dynamics at T=0 have been studied. Statistical analysis of the field values for which avalanches occur has enabled a Finite-Size Scaling (FSS) study of the avalanche density to be performed. Furthermore, a direct measurement of the geometrical properties of the avalanches has confirmed an earlier hypothesis that several types of spanning avalanches with two different fractal dimensions coexist at the critical point. We finally compare the phase diagram of the 3D-GRFIM with metastable dynamics with the same model in equilibrium at T=0.

Hysteresis and avalanches in the T=0 random field ising model with 2-spin flip dynamics

We study the nonequilibrium behavior of the three-dimensional Gaussian random-field Ising model at T=0 in the presence of a uniform external field using a two-spin-flip dynamics. The deterministic, history-dependent evolution of the system is compared with the one obtained with the standard one-spin-flip dynamics used in previous studies of the model. The change in the dynamics yields a significant suppression of coercivity, but the distribution of avalanches (in number and size) stays remarkably similar, except for the largest ones that are responsible for the jump in the saturation magnetization curve at low disorder in the thermodynamic limit. By performing a finite-size scaling study, we find strong evidence that the change in the dynamics does not modify the universality class of the disorder-induced phase transition.

Diluted three-dimensional random field Ising model at zero temperature with metastable dynamics.

The influence of vacancy concentration on the behavior of the three-dimensional random field Ising model with metastable dynamics is studied. We have focused our analysis on the number of spanning avalanches which allows us a clear determination of the critical line where the hysteresis loops change from continuous to discontinuous. By a detailed finite-size scaling analysis we determine the phase diagram and numerically estimate the critical exponents along the whole critical line. Finally, we discuss the origin of the curvature of the critical line at high vacancy concentration.

Influence of the driving mechanism on the response of systems with athermal dynamics: The example of the random-field Ising model

We investigate the influence of the driving mechanism on the hysteretic response of systems with athermal dynamics. In the framework of local mean-field theory at finite temperature (but neglecting thermally activated processes), we compare the rate-independent hysteresis loops obtained in the random field Ising model when controlling either the external magnetic field H or the extensive magnetization M. Two distinct behaviors are observed, depending on disorder strength. At large disorder, the H-driven and M-driven protocols yield identical hysteresis loops in the thermodynamic limit. At low disorder, when the H-driven magnetization curve is discontinuous (due to the presence of a macroscopic avalanche), the M-driven loop is reentrant while the induced field exhibits strong intermittent fluctuations and is only weakly self-averaging. The relevance of these results to the experimental observations in ferromagnetic materials, shape memory alloys, and other disordered systems is discussed.

Random-field Potts model with dipolarlike interactions: Hysteresis avalanches and microstructure

A model for the study of hysteresis and avalanches in a first-order phase transition from a single variant phase to a multivariant phase is presented. The model is based on a modification of the random-field Potts model with metastable dynamics by adding a dipolar interaction term truncated at nearest neighbors. We focus our study on hysteresis loop properties, on the three-dimensional microstructure formation, and on avalanche statistics.

Numerical signs fos a transition in the 2d Random Field Ising Model at T=0

Intensive numerical studies of exact ground states of the two-dimensional ferromagnetic random field Ising model at T=0, with a Gaussian distribution of fields, are presented. Standard finite size scaling analysis of the data suggests the existence of a transition at ¿c=0.64±0.08. Results are compared with existing theories and with the study of metastable avalanches in the same model.