Statistical mechanics of random graphs

We provide an annotated bibliography for the study of Hamilton cycles in random graphs and hypergraphs.

In these lectures I will present an introduction to the results that have been recently obtained in constraint optimization of random problems using statistical mechanics techniques. After presenting the general results, in order to simplify the presentation I will describe in details only the problems related to the coloring of a random graph.

We apply in this article (non rigorous) statistical mechanics methods to the problem of counting long circuits in graphs. The outcomes of this approach have two complementary flavours. On the algorithmic side, we propose an approximate counting procedure, valid in principle for a large class of graphs. On a more theoretical side, we study the typical number of long circuits in random graph ensembles, reproducing rigorously known results and stating new conjectures.

Here I will present an introduction to the results that have been recently obtained in constraint optimization of random problems using statistical mechanics techniques. After presenting the general results, in order to simplify the presentation I will describe in details the problems related to the coloring of a random graph.

The problem of vertex coloring in random graphs is studied using methods of statistical physics and probability. Our analytical results are compared to those obtained by exact enumeration and Monte-Carlo simulations. We critically discuss the merits and shortcomings of the various methods, and interpret the results obtained. We present an exact analytical expression for the 2-coloring problem as well as general replica symmetric approximated solutions for the thermodynamics o...

This PhD thesis deals with a number of different problems in mathematical physics with the common thread that they have probabilistic aspects. The problems all stem from mathematical studies of lattice systems in statistical and quantum physics; however beyond that, the selection of the concrete problems is to a certain extent arbitrary. This thesis consists of an introduction and seven papers.

Random graphs have proven to be one of the most important and fruitful concepts in modern Combinatorics and Theoretical Computer Science. Besides being a fascinating study subject for their own sake, they serve as essential instruments in proving an enormous number of combinatorial statements, making their role quite hard to overestimate. Their tremendous success serves as a natural motivation for the following very general and deep informal questions: what are the essential ...

The Krakow-Orsay collaboration has applied methods borrowed from equilibrium statistical mechanics and analytic combinatorics to study the geometry of random networks. Results contained in a series of recent publications and concerning networks that are either uncorrelated or causal are briefly overviewed.

The extremal characteristics of random structures, including trees, graphs, and networks, are discussed. A statistical physics approach is employed in which extremal properties are obtained through suitably defined rate equations. A variety of unusual time dependences and system-size dependences for basic extremal properties are obtained.

Using a maximum entropy principle to assign a statistical weight to any graph, we introduce a model of random graphs with arbitrary degree distribution in the framework of standard statistical mechanics. We compute the free energy and the distribution of connected components. We determine the size of the percolation cluster above the percolation threshold. The conditional degree distribution on the percolation cluster is also given. We briefly present the analogous discussion...