We study inhomogeneous random graphs in the subcritical case. Among other results, we derive an exact formula for the size of the largest connected component scaled by log$n$, with$n$being the size of the graph. This generalizes a result for the “rank-1 case”. We also investigate branching processes associated with these graphs. In particular, we discover that the same well-known equation for the survival probability, whose positive solution determines the asymptotics of the size of the largest component in the supercritical case, also plays a crucial role in the subcritical case. However, now it is the$negative$solutions that come into play. We disclose their relationship to the distribution of the progeny of the branching process.
We study correlation bounds under pairwise independent distributions for functions with no large Fourier coefficients. Functions in which all Fourier coefficients are bounded by$δ$are called$δ$-$uniform$. The search for such bounds is motivated by their potential applicability to hardness of approximation, derandomization, and additive combinatorics.
A fundamental and very well studied region of the Erdős–Rényi process is the phase transition at$m$∼$n$/2 edges in which a giant component suddenly appears. We examine the process beginning with an initial graph. We further examine the Bohman–Frieze process in which edges between isolated vertices are more likely. While the positions of the phase transitions vary, the three processes belong, roughly speaking, to the same universality class. In particular, the growth of the giant component in the barely supercritical region is linear in all cases.