The expected capacity of a class of sparse concentrators called modular concentrators is determined. In these concentrators, each input is connected to exactly two outputs, each output is connected to exactly three inputs, and the girth (the length of the shortest cycle in the connexion graph) is large. Two definitions of expected capacity are considered. For the first (which is due to Masson and Morris), it is assumed that a batch of customers arrive at a random set of inputs and that a maximum matching of these customers to servers at the outputs is found. The number of unsatisfied requests is negligible if customers arrive at fewer than one-half of the inputs, and it grows quite gracefully even beyond this threshold. The situation in which customers arrive sequentially is considered, and the decision as to how to serve each is made randomly, without knowledge of future arrivals. In this case, the number of unsatisfied requests is larger but still quite modest.
© 1991 Society for Industrial and Applied Mathematics
Nicholas Pippenger. "The Expected Capacity of Concentrators", Society for Industrial and Applied Mathematics Journal of Discrete Mathematics, 4, 121 (1991).