Percolation on finite graphs is known to exhibit a phase transition similar to the Erdős-Rényi Random Graph in presence of sufficiently weak geometry. We focus on the Hamming graph H(d,n) (the cartesian product of d complete graphs on n vertices each) when d is fixed and n\to\infty. We identify the critical point p_c(d) at which such phase transition happens and we analyse the structure of the largest connected components at criticality. We prove that the scaling limit of component sizes is identical to the one for critical Erdős-Rényi components, while the number of surplus edges is much higher. These results are obtained coupling percolation to the trace of branching random walks on the Hamming graph. Based on joint work with Remco van der Hofstad, Frank den Hollander and Tim Hulshof.
Critical percolation on the Hamming graph
2017. 11. 09. 16:15
Lorenzo Federico (TU Eindhoven)