CDAM: Computational, Discrete and Applicable Mathematics@LSE

CDAM Research Report, LSE-CDAM-2007-37

February 2008

Random Subgraphs of the 2D Hamming Graph: the Supercritical Phase

Remco van der Hofstad and Malwina J. Luczak

We study random subgraphs of the 2-dimensional Hamming graph H(2,n), which is the Cartesian product of two complete graphs on n vertices. Let p be the edge probability, and write p=(1+ε)/2(n-1) for some ε∈ R. In [4,5], the size of the largest connected component was estimated precisely for a large class of graphs including H(2,n) for ε≤ Λ V^-1/3, where Λ > 0 is a constant and V=n² denotes the number of vertices in H(2,n). Until now, no matching lower bound on the size in the supercritical regime has been obtained.

In this paper we prove that, when ε>> (log V)^1/3 V^-1/3, then the largest connected component has size close to 2ε V with high probability. We thus obtain a law of large numbers for the largest connected component size, and show that the corresponding values of p are supercritical. Barring the factor (log V)^1/3, this identifies the size of the largest connected component all the way down to the critical p window.

A PDF file (343 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2007-37, together with your name and postal address to:

CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.

Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-20-7955 7494. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk