The Expected Capacity of Concentrators

We determine the "expected capacity'' of a class of sparse concentrators called "modular concentrators''. 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. We consider two definitions of expected capacity. For the first (which is due to Masson and Morris), we assume that a batch of customers arrives 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. We also consider the situation in which customers arrive sequentially, 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.