The k-orientability thresholds for Gn, p
Daniel Fernholz, Vijaya Ramachandran · 2007
We prove that, for k ≥ 2, the k-orientability threshold for the random graph Gn,p coincides with the threshold at which the (k + 1)-core has average degree 2k. The proof involves the analysis of a heuristic algorithm that attempts to find a k-orientation of the random graph. The k-orientation threshold has several applications including offline balanced allocation with a limit of k on maximum bin-size, perfect hashing with a limit of k on maximum chain-length, and concurrent access to parallel memories through redundancy, 1