Quadratic Stochastic Euclidean Bipartite Matching Problem.

We propose a new approach for the study of the quadratic stochastic Euclidean bipartite matching problem between two sets of N points each, N≫1. The points are supposed independently randomly generated on a domain Ω⊂R^{d} with a given distribution ρ(x) on Ω. In particular, we derive a general expression for the correlation function and for the average optimal cost of the optimal matching. A previous ansatz for the matching problem on the flat hypertorus is obtained as a particular case.

Planted matching problems on random hypergraphs.

We consider the problem of inferring a matching hidden in a weighted random k-hypergraph. We assume that the hyperedges' weights are random and distributed according to two different densities conditioning on the fact that they belong to the hidden matching or not. We show that for k>2 and in the large-graph-size limit, an algorithmic first-order transition in the signal strength separates a regime in which a complete recovery of the hidden matching is feasible from a regime in which partial recovery is possible. This is in contrast to the k=2 case, where the transition is known to be continuous. Finally, we consider the case of graphs presenting a mixture of edges and 3-hyperedges, interpolating between the k=2 and the k=3 cases, and we study how the transition changes from continuous to first order by tuning the relative amount of edges and hyperedges.

Recovery thresholds in the sparse planted matching problem.

We consider the statistical inference problem of recovering an unknown perfect matching, hidden in a weighted random graph, by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted matching. A recent work has demonstrated the existence of a phase transition, in the large size limit, between a full and a partial-recovery phase for a specific form of the weights distribution on fully connected graphs. We generalize and extend this result in two directions: we obtain a criterion for the location of the phase transition for generic weights distributions and possibly sparse graphs, exploiting a technical connection with branching random walk processes, as well as a quantitatively more precise description of the critical regime around the phase transition.

Fluctuations in the random-link matching problem.

Using the replica approach and the cavity method, we study the fluctuations of the optimal cost in the random-link matching problem. By means of replica arguments, we derive the exact expression of its variance. Moreover, we study the large deviation function, deriving its expression in two different ways, namely using both the replica method and the cavity method.

Mean-field model for the density of states of jammed soft spheres.

We propose a class of mean-field models for the isostatic transition of systems of soft spheres, in which the contact network is modeled as a random graph and each contact is associated to d degrees of freedom. We study such models in the hypostatic, isostatic, and hyperstatic regimes. The density of states is evaluated by both the cavity method and exact diagonalization of the dynamical matrix. We show that the model correctly reproduces the main features of the density of states of real packings and, moreover, it predicts the presence of localized modes near the lower band edge. Finally, the behavior of the density of states D(ω)∼ω^{α} for ω→0 in the hyperstatic regime is studied. We find that the model predicts a nontrivial dependence of α on the details of the coordination distribution.

One-loop diagrams in the random Euclidean matching problem.

The matching problem is a notorious combinatorial optimization problem that has attracted for many years the attention of the statistical physics community. Here we analyze the Euclidean version of the problem, i.e., the optimal matching problem between points randomly distributed on a d-dimensional Euclidean space, where the cost to minimize depends on the points' pairwise distances. Using Mayer's cluster expansion we write a formal expression for the replicated action that is suitable for a saddle point computation. We give the diagrammatic rules for each term of the expansion, and we analyze in detail the one-loop diagrams. A characteristic feature of the theory, when diagrams are perturbatively computed around the mean field part of the action, is the vanishing of the mass at zero momentum. In the non-Euclidean case of uncorrelated costs instead, we predict and numerically verify an anomalous scaling for the sub-sub-leading correction to the asymptotic average cost.

Random Euclidean matching problems in one dimension.

We discuss the optimal matching solution for both the assignment problem and the matching problem in one dimension for a large class of convex cost functions. We consider the problem in a compact set with the topology both of the interval and of the circumference. Afterwards, we assume the points' positions to be random variables identically and independently distributed on the considered domain. We analytically obtain the average optimal cost in the asymptotic regime of very large number of points N and some correlation functions for a power-law-type cost function in the form c(z)=z^{p}, both in the p>1 case and in the p<0 case. The scaling of the optimal mean cost with the number of points is N^{-p/2} for the assignment and N^{-p} for the matching when p>1, whereas in both cases it is a constant when p<0. Finally, our predictions are compared with the results of numerical simulations.

Finite-size corrections in the random assignment problem.

We analytically derive, in the context of the replica formalism, the first finite-size corrections to the average optimal cost in the random assignment problem for a quite generic distribution law for the costs. We show that, when moving from a power-law distribution to a Γ distribution, the leading correction changes both in sign and in its scaling properties. We also examine the behavior of the corrections when approaching a δ-function distribution. By using a numerical solution of the saddle-point equations, we provide predictions that are confirmed by numerical simulations.

Groups, information theory, and Einstein's likelihood principle.

We propose a unifying picture where the notion of generalized entropy is related to information theory by means of a group-theoretical approach. The group structure comes from the requirement that an entropy be well defined with respect to the composition of independent systems, in the context of a recently proposed generalization of the Shannon-Khinchin axioms. We associate to each member of a large class of entropies a generalized information measure, satisfying the additivity property on a set of independent systems as a consequence of the underlying group law. At the same time, we also show that Einstein's likelihood function naturally emerges as a byproduct of our informational interpretation of (generally nonadditive) entropies. These results confirm the adequacy of composable entropies both in physical and social science contexts.

Nonlinear inhomogeneous Fokker-Planck equations: Entropy and free-energy time evolution.

We extend a recently introduced free-energy formalism for homogeneous Fokker-Planck equations to a wide, and physically appealing, class of inhomogeneous nonlinear Fokker-Planck equations. In our approach, the free-energy functional is expressed in terms of an entropic functional and an auxiliary potential, both derived from the coefficients of the equation. With reference to the introduced entropic functional, we discuss the entropy production in a relaxation process towards equilibrium. The properties of the stationary solutions of the considered Fokker-Planck equations are also discussed.

Scaling hypothesis for the Euclidean bipartite matching problem. II. Correlation functions.

We analyze the random Euclidean bipartite matching problem on the hypertorus in d dimensions with quadratic cost and we derive the two-point correlation function for the optimal matching, using a proper ansatz introduced by Caracciolo et al. [Phys. Rev. E 90, 012118 (2014)] to evaluate the average optimal matching cost. We consider both the grid-Poisson matching problem and the Poisson-Poisson matching problem. We also show that the correlation function is strictly related to the Green's function of the Laplace operator on the hypertorus.

One-dimensional Euclidean matching problem: exact solutions, correlation functions, and universality.

We discuss the equivalence relation between the Euclidean bipartite matching problem on the line and on the circumference and the Brownian bridge process on the same domains. The equivalence allows us to compute the correlation function and the optimal cost of the original combinatorial problem in the thermodynamic limit; moreover, we solve also the minimax problem on the line and on the circumference. The properties of the average cost and correlation functions are discussed.