The Connection Between Multicomponent Smoluchowski's Equation, Multidimensional Inviscid Burgers' Equations and Random Graphs

Abstract

We consider multicomponent Smoluchowski's coagulation equation with a bilinear kernel and mono-dispersed initial conditions. Because of the choice for the kernel, this equation maps to a partial di����erential equation called the inviscid Burgers' equation. We show in one-dimension, and claim it also holds in higher dimensions, that con- nected components in coloured Erdös-Renyi random graph asymptotically describe the solution to the Smoluchowski's equations for monodispersed intial conditions and the nonlinear PDE associated to it. Using Joyal's formalism of combinatorial species, we obtain a closed-form solution for these equations by counting connected components in the random graph. We also derive a simple equation for the blow up time of the Burgers' inviscid equation with the chosen bilinear form. Using the insights obtained from our method, and adapting previous algorithms, we additionally propose a randomized numerical scheme that constructs d-coloured random graphs with N vertices and expected degree distribution in time O((d+1)N). Using this algorithm we can inexpensively compute solutions to the multiplicative multicomponent Smoluchowski's equation (and consequently to Burgers' inviscid equation) at any time before solution blow up, hence resolving the curse of dimen- sionality for this problem.