Search

Quadratic Unconstrained Binary Optimization (QUBO or UBQP) is concerned with maximizing/minimizing the quadratic form $H(J, \eta) = W \sum_{i,j} J_{i,j} \eta_{i} \eta_{j}$ with $J$ a matrix of coefficients, $\eta \in \{0, 1\}^N$ and $W$ a normalizing constant. In the statistical mechanics literature, QUBO is a lattice gas counterpart to the (generalized) Sherrington--Kirkpatrick spin glass model. Finding the optima of $H$ is an NP-hard problem. Several problems in combinatorial optimization and data analysis can be mapped to QUBO in a straightforward manner. In the combinatorial optimization literature, random instances of QUBO are often used to test the effectiveness of heuristic algorithms. Here we consider QUBO with random independent coefficients and show that if the $J_{i,j}$'s have zero mean and finite variance then, after proper normalization, the minimum and maximum \emph{per particle} of $H$ do not depend on the details of the distribution of the couplings and are concentrated around their expected values. Further, with the help of numerical simulations, we study the minimum and maximum of the objective function and provide some insight into the structure of the minimizer and the maximizer of $H$. We argue that also this structure is rather robust. Our findings hold also in the diluted case where each of the $J_{i,j}$'s is allowed to be zero with probability going to $1$ as $N \to \infty$ in a suitable way., Comment: 20 pages, 8 figures

We prove the equivalence between integral and local central limit theorem for spin system interacting via an absolutely summable pair potential without any conditions on the temperature of the system.

In this paper we propose a simplified model to describe the dissipative effects of tides. We assume a spherical Earth with a dissipative coupling with a mechanical dumbbell. The latter has a mass much smaller than the Earth's, and it models the presence of the tidal bulges. Using properly the scale analysis, we will show that some of the consequences of tidal dissipation are the circularization and the enlargement of orbit of the Moon and the slowing down of the Earth's rotation. We will also see that tidal dissipation plays a fundamental role for the establishment of a regime of spin-orbit resonance in the celestial systems. The mathematical tools used make our treatment appropriate for senior high school students or college students., Comment: 10 pages, 3 figures

We analyse the Blume-Emery-Griffiths (BEG) model on the lattice $\Zd$ at the ferromagnetic-antiquadrupolar-disordered (FAD) and antiquadrupolar-disordered (AD) interfaces of parameters. In our analysis of the FAD interface we introduce a Gibbs sampler of the ground states at zero temperature, and we exploit it in two different ways: first, we perform via perfect sampling an empirical evaluation of the spontaneous magnetization at zero temperature, finding a non-zero value in $d=3$ and a vanishing value in $d=2$. Second, using a careful coupling with the Bernoulli site percolation model in $d=2$, we prove rigorously that imposing $+$ boundary conditions, the magnetization in the center of a square box tends to zero in the thermodynamical limit and the two-point correlations decay exponentially. Also, using again a coupling argument, we show that the infinite volume Gibbs measure of the zero-temperature BEG exists and it is unique. In our analysis of the AD interface we restrict ourselves to $d=2$ and, by comparing the BEG model with a Bernoulli site percolation in a matching graph of $\mathbb{Z}^2$, we get a condition for the vanishing of the infinite volume limit magnetization improving, for low temperatures, earlier results obtained via expansion techniques.

On the space of $\pm 1$ spin configurations on the 3$d$-square lattice, we consider the \emph{shaken dynamics}, a parallel Markovian dynamics that can be interpreted in terms of Probabilistic Cellular Automata. The transition probabilities are defined in terms of pair ferromagnetic Ising-type Hamiltonians with nearest neighbor interaction $J$, depending on an additional parameter $q$, measuring the tendency of the system to remain locally in the same state. Odd times and even times have different transition probabilities. We compute the stationary measure of the shaken dynamics and we investigate its relation with the Gibbs measure for the 3$d$ Ising model. It turns out that the two parameters $J$ and $q$ tune the geometry of the underlying lattice. We conjecture the existence of unique line of critical points in $J-q$ plane. By a judicious use of perturbative methods we delimit the region where such curve must lie and we perform numerical simulation to determine it. Our method allows us to find in a unified way the critical values of $J$ for Ising model with first neighbors interaction, defined on a whole class of lattices, intermediate between the two-dimensional hexagonal and the three-dimensional cubic one, such as, for example, the tetrahedral lattice. Finally we estimate the critical exponents of the magnetic susceptibility and show that our model captures a dimensional transition in the geometry of the system at $q = 0$.

We discuss a model describing the effects of tidal dissipation on satellite's orbits. Tidal bulges are described in terms of a dumbbell, coupled to the rotation by a dissipative interaction. The assumptions on this dissipative coupling turns out to be crucial in the evolution of the system., Comment: 2 figures

In this paper we propose a notion of stability, that we call $\epsilon -N$-stability, for systems of particles interacting via Newton's gravitational potential, and orbiting a much bigger object. For these systems the usual thermodynamical stability condition, ensuring the possibility to perform the thermodynamical limit, fails, but one can use as relevant parameter the maximum number of particles $N$ that guarantees the $\epsilon -N$-stability. With some judicious but not particularly optimized estimates, borrowed from the classical theory of equilibrium statistical mechanics, we show that our model has a good fit with the data observed in the Solar System, and it gives a reasonable interpretation of some of its global properties.

On the space of Ising configurations on the 2-d square lattice, we consider a family of non Gibbsian measures introduced by using a pair Hamiltonian, depending on an additional inertial parameter $q$. These measures are related to the usual Gibbs measure on $\Z^2$ and turn out to be the marginal of the Gibbs measure of a suitable Ising model on the hexagonal lattice. The inertial parameter $q$ tunes the geometry of the system. The critical behaviour and the decay of correlation functions of these measures are studied thanks to relation with the Random Cluster model.

We define a class of Markovian parallel dynamics for spin systems on arbitrary graphs with nearest neighbor interaction described by a Hamiltonian function $H(\sigma)$. These dynamics turn out to be reversible and their stationary measure is explicitly determined. Convergence to equilibrium and relation of the stationary measure to the usual Gibbs measure are discussed when the dynamics is defined on $\mathbb{Z}^2$. Further it is shown how these dynamics can be used to define natively parallel algorithms to face problems in the context of combinatorial optimization., Comment: 8 figures

We study rigorously a lattice gas version of the Sherrington-Kirckpatrick spin glass model. In discrete optimization literature this problem is known as Unconstrained Binary Quadratic Programming (UBQP) and it belongs to the class NP-hard. We prove that the fluctuations of the ground state energy tend to vanish in the thermodynamic limit, and we give a lower bound of such ground state energy. Then we present an heuristic algorithm, based on a probabilistic cellular automaton, which seems to be able to find configurations with energy very close to the minimum, even for quite large instances., Comment: 3 figures, 2 tables

We present a simple one-dimensional Ising-type spin system on which we define a completely asymmetric Markovian single spin-flip dynamics. We study the system at a very low, yet non-zero, temperature and we show that for empty boundary conditions the Gibbs measure is stationary for such dynamics, while introducing in a single site a $+$ condition the stationary measure changes drastically, with macroscopical effects. We achieve this result defining an absolutely convergent series expansion of the stationary measure around the zero temperature system. Interesting combinatorial identities are involved in the proofs.

We construct a parallel stochastic dynamics with invariant measure converging to the Gibbs measure of the low temperature Ising model. The proof of such convergence requires a polymer expansion based on suitably defined Peierls-type contours.

The Totally Asymmetric Simple Exclusion Process (TASEP) is an important example of a particle system driven by an irreversible Markov chain. In this paper we give a simple yet rigorous derivation of the chain stationary measure in the case of parallel updating rule. In this parallel framework we then consider the blockage problem (aka slow bond problem). We find the exact expression of the current for an arbitrary blockage intensity $\varepsilon$ in the case of the so-called rule-184 cellular automaton, i.e. a parallel TASEP where at each step all particles free-to-move are actually moved. Finally, we investigate through numerical experiments the conjecture that for parallel updates other than rule-184 the current may be non-analytic in the blockage intensity around the value $\varepsilon = 0$.

We study metastability and mixing time for a non-reversible probabilistic cellular automaton. With a suitable choice of the parameters, we first show that the stationary distribution is close in total variation to a low temperature Ising model. Then we prove that both the mixing time and the time to exit a metastable state grow polynomially in the size of the system, while this growth is exponential in reversible dynamics. In this model, non-reversibility, parallel updatings and a suitable choice of boundary conditions combine to produce an efficient dynamical stability.

In this paper we present a new bound obtained with the probabilistic method for the solution of the Set Covering problem with unit costs. The bound is valid for problems of fixed dimension, thus extending previous similar asymptotic results, and it depends only on the number of rows of the coefficient matrix and the row densities. We also consider the particular case of matrices that are \textit{almost} block decomposable, and show how the bound may improve according to the particular decomposition adopted. Such final result may provide interesting indications for comparing different matrix decomposition strategies.

We revisit an old tree graph formula, namely the Brydges-Federbush tree identity, and use it to get new bounds for the convergence radius of the Mayer series for gases of continuous particles interacting via non absolutely summable pair potentials with an attractive tail including Lennard-Jones type pair potentials.

We propose a unified approach to reversible and irreversible PCA dynamics, and we show that in the case of 1D and 2D nearest neighbour Ising systems with periodic boundary conditions we are able to compute the stationary measure of the dynamics also when the latter is irreversible. We also show how, according to [DPSS12], the stationary measure is very close to the Gibbs for a suitable choice of the parameters of the PCA dynamics, both in the reversible and in the irreversible cases. We discuss some numerical aspects regarding this topic, including a possible parallel implementation.

We present a model to describe the inbound air traffic over a congested hub. We show that this model gives a very accurate description of the traffic by the comparison of our theoretical distribution of the queue with the actual distribution observed over Heathrow airport. We discuss also the robustness of our model.

We study a discrete time queueing system where deterministic arrivals have i.i.d. exponential delays $\xi_{i}$. The standard deviation $\sigma$ of the delay is finite, but its value is much larger than the deterministic unit service time. We describe the model as a bivariate Markov chain, we prove that it is ergodic and then we focus on the unique joint equilibrium distribution. We write a functional equation for the bivariate generating function, finding the solution of such equation on a subset of its set of definition. This solution allows us to prove that the equilibrium distribution of the Markov chain decays super-exponentially fast in the quarter plane. Finally, exploiting the latter result, we discuss the numerical computation of the stationary distribution, showing the effectiveness of a simple approximation scheme in a wide region of the parameters. The model, motivated by air and railway traffic, was proposed many decades ago by Kendall with the name of "late arrivals problem", but no solution has been found so far.

We consider the problem of approximate sampling from the finite volume Gibbs measure with a general pair interaction. We exhibit a parallel dynamics (Probabilistic Cellular Automaton) which efficiently implements the sampling. In this dynamics the product measure that gives the new configuration in each site contains a term that tends to favour the original value of each spin. This is the main ingredient that allows to prove that the stationary distribution of the PCA is close in total variation to the Gibbs measure. The presence of the parameter that drives the "inertial" term mentioned above gives the possibility to control the degree of parallelism of the numerical implementation of the dynamics., Comment: 21 pages

In this paper we present, in the context of Diaconis' paradigm, a general method to detect the cutoff phenomenon. We use this method to prove cutoff in a variety of models, some already known and others not yet appeared in literature, including a chain which is non-reversible w.r.t. its stationary measure. All the given examples clearly indicate that a drift towards the opportune quantiles of the stationary measure could be held responsible for this phenomenon. In the case of birth- and-death chains this mechanism is fairly well understood; our work is an effort to generalize this picture to more general systems, such as systems having stationary measure spread over the whole state space or systems in which the study of the cutoff may not be reduced to a one-dimensional problem. In those situations the drift may be looked for by means of a suitable partitioning of the state space into classes; using a statistical mechanics language it is then possible to set up a kind of energy-entropy competition between the weight and the size of the classes. Under the lens of this partitioning one can focus the mentioned drift and prove cutoff with relative ease., Comment: 40 pages, 1 figure

We give a rigorous proof of two phase transitions for a disordered system designed to find large cliques inside Erdos random graphs. Such a system is associated with a conservative probabilistic cellular automaton inspired by the cavity method originally introduced in spin glass theory., Comment: 36 pages, 4 figures

Given a graph $G$ with maximum degree $\Delta\ge 3$, we prove that the acyclic edge chromatic number $a'(G)$ of $G$ is such that $a'(G)\le\lceil 9.62 (\Delta-1)\rceil$. Moreover we prove that: $a'(G)\le \lceil 6.42(\Delta-1)\rceil$ if $G$ has girth $g\ge 5\,$; $a'(G)\le \lceil5.77 (\Delta-1)\rc$ if $G$ has girth $g\ge 7$; $a'(G)\le \lc4.52(\D-1)\rc$ if $g\ge 53$; $a'(G)\le \D+2\,$ if $g\ge \lceil25.84\D\log\D(1+ 4.1/\log\D)\rceil$. We further prove that the acyclic (vertex) chromatic number $a(G)$ of $G$ is such that $a(G)\le \lc 6.59 \Delta^{4/3}+3.3\D\rc$. We also prove that the star-chromatic number $\chi_s(G)$ of $G$ is such that $\chi_s(G)\le \lc4.34\Delta^{3/2}+ 1.5\D\rc$. We finally prove that the $\b$-frugal chromatic number $\chi^\b(G)$ of $G$ is such that $\chi^\b(G)\le \lc\max\{k_1(\b)\D,\; k_2(\b){\D^{1+1/\b}/ (\b!)^{1/\b}}\}\rc$, where $k_1(\b)$ and $k_2(\b)$ are decreasing functions of $\b$ such that $k_1(\b)\in[4, 6]$ and $k_2(\b)\in[2,5]$. To obtain these results we use an improved version of the Lov\'asz Local Lemma due to Bissacot, Fern\'andez, Procacci and Scoppola \cite{BFPS}., Comment: Introduction revised. Added references. Corrected typos. Proof of Theorem 2 (items c-f) written in more details

An old result by Shearer relates the Lov\'asz Local Lemma with the independent set polynomial on graphs, and consequently, as observed by Scott and Sokal, with the partition function of the hard core lattice gas on graphs. We use this connection and a recent result on the analyticity of the logarithm of the partition function of the abstract polymer gas to get an improved version of the Lov\'asz Local Lemma. As applications we obtain tighter bounds on conditions for the existence of latin transversal matrices and the satisfiability of k-SAT forms., Comment: In this new version the abstract has been extended, an introduction has been added and a new application on k-sat has been given.

We prove clustering estimates for the truncated correlations, i.e., cumulants of an unbounded spin system on the lattice. We provide a unified treatment, based on cluster expansion techniques, of four different regimes: large mass, small interaction between sites, large self-interaction, as well as the more delicate small self-interaction or `low temperature' regime. A clustering estimate in the latter regime is needed for the Bosonic case of the recent result obtained by Lukkarinen and Spohn on the rigorous control on kinetic scales of quantum fluids., Comment: 50 pages, Latex

We prove that a class of random walks on $\Z^2$ with long-range self-repulsive interactions have a diffusive-ballistic phase transition., Comment: 7 pages, to appear in Letters in Mathematical Physics

We find an improved estimate of the radius of analyticity of the pressure of the hard-sphere gas in $d$ dimensions. The estimates are determined by the volume of multidimensional regions that can be numerically computed. For $d=2$, for instance, our estimate is about 40% larger than the classical one., Comment: 4 pages, to appear in Journal of Statistical Physics

In this paper we introduce a new algorithm to study some NP-complete problems. This algorithm is a Markov Chain Monte Carlo (MCMC) inspired by the cavity method developed in the study of spin glass. We will focus on the maximum clique problem and we will compare this new algorithm with several standard algorithms on some DIMACS benchmark graphs and on random graphs. The performances of the new algorithm are quite surprising. Our effort in this paper is to be clear as well to those readers who are not in the field., Comment: 21 pages, latex file

In this paper we extend our previous results on the connectivity functions and pressure of the Random Cluster Model in the highly subcritical phase and in the highly supercritical phase, originally proved only on the cubic lattice $\Z^d$, to a much wider class of infinite graphs. In particular, concerning the subcritical regime, we show that the connectivity functions are analytic and decay exponentially in any bounded degree graph. In the supercritical phase, we are able to prove the analyticity of finite connectivity functions in a smaller class of graphs, namely, bounded degree graphs with the so called minimal cut-set property and satisfying a (very mild) isoperimetric inequality. On the other hand we show that the large distances decay of finite connectivity in the supercritical regime can be polynomially slow depending on the topological structure of the graph. Analogous analyticity results are obtained for the pressure of the Random Cluster Model on an infinite graph, but with the further assumptions of amenability and quasi-transitivity of the graph., Comment: In this new version the introduction has been revised, some references have been added, and many typos have been corrected. 37 pages, to appear in Communications on Pure and Applied Analysis

Given an infinite graph $\GI$ quasi-transitive and amenable with maximum degree $\D$, we show that reduced ground state degeneracy per site $W_r(\GI,q)$ of the q-state antiferromagnetic Potts model at zero temperature on $\GI$ is analytic in the variable 1/q, whenever $|2\D e^3/q|< 1$. This result proves, in an even stronger formulation, a conjecture originally sketched in [KE] (Kim and Enting, 1979) and explicitly formulated in [ST] (Shrock and Tsai,1997), based on which a sufficient condition for $W_r(\GI,q)$ to be analytic at 1/q=0 is that $\GI$ is a regular lattice.