Proceedings of the American Mathematical Society

Vol. 143, num. 3, p. 925-936

Date of publication: 2015-03-01

Abstract:

Let G(n, M) be the uniform random graph with n vertices and M edges. Erdos and Renyi (1960) conjectured that the limiting probability; lim(n ->infinity) Pr{G(n, n/2) is planar}; exists and is a constant strictly between 0 and 1. Luczak, Pittel and Wierman (1994) proved this conjecture, and Janson, Luczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this paper we determine the exact limiting probability of a random graph being planar near the critical point M = n/2. For each lambda, we find an exact analytic expression for; p(lambda) = lim(n ->infinity) Pr {G (n, n/2 (1 + lambda(n-1/3))) is planar}.; In particular, we obtain p(0) approximate to 0.99780. We extend these results to classes of graphs closed under taking minors. As an example, we show that the probability of G(n, n/2) being series-parallel converges to 0.98003. For the sake of completeness and exposition we reprove in a concise way several basic properties we need of a random graph near the critical point.]]>

Abstract:

The project addresses a set of problems which are at the forefront of contemporary combinatorics. The main objectives include the following: an extension of Szemerédi type theorems for solutions of linear systems to the sparse setting, which is the arithmetic side of recent developments leading to random versions of Ramsey and density results in combinatorics; the extension to minor closed classes of graphs of the celebrated results on enumeration and parameter analysis of planar graphs, which involve the asymptotic probability distribution of significant parameters and may lead, among other results, to the first known subquadratic algorithm for 4-coloring random planar graphs; the study of a random model for tranversal matroids, which would be a novel contribution to random models for complex combinatorial structures; a longstanding conjecture of Stanley on the feasibility of h-vectors in matroids in terms of pure simplicial complexes, for which only few simple cases have been verified; the use of polynomial methods in the study of the so-called MDS conjecture, proved by one of the members of the team in the prime case, and the improvement of constants involved in Kakeya sets and of Bourgain sets in finite geometries, as well as their extensions to higher dimensions; the extension to the geometric setting of classical results in additive combinatorics, which is connected to the existence of a class of MDS codes in the space of bilinear symmetric forms with respect to a particular metric; the asymptotic analysis of pattern densities in permutations, a novel project strongly connected to extremal graph theory and the theory of graph limits. The treatment of these problems involves a development and interleaving of algebraic, geometric and probabilistic methods in combinatorics. Building a solid ground for this set of techniques is one of the side objectives of the proposal.]]>

Random structures and algorithms

Vol. 42, num. 4, p. 438-479

DOI: 10.1002/rsa.20421

Date of publication: 2013

Abstract:

Consider a family equation image of 3-connected graphs of moderate growth, and let equation image be the class of graphs whose 3-connected components are graphs in equation image. We present a general framework for analyzing such graphs classes based on singularity analysis of generating functions, which generalizes previously studied cases such as planar graphs and series-parallel graphs. We provide a general result for the asymptotic number of graphs in equation image, based on the singularities of the exponential generating function associated to equation image. We derive limit laws, which are either normal or Poisson, for several basic parameters, including the number of edges, number of blocks and number of components. For the size of the largest block we find a fundamental dichotomy: classes similar to planar graphs have almost surely a unique block of linear size, while classes similar to series-parallel graphs have only sublinear blocks. This dichotomy was already observed by Panagiotou and Steger [25], and we provide a finer description. For some classes under study both regimes occur, because of a critical phenomenon as the edge density in the class varies. Finally, we analyze the size of the largest 3-connected component in random planar graphs.]]>

Discrete applied mathematics

Vol. 157, num. 7, p. 1509-1520

DOI: 10.1016/j.dam.2008.06.018

Date of publication: 2009-04

Journal of combinatorial mathematics and combinatorial computing

Vol. 57, p. 97-102

Date of publication: 2006-01