Natural bounded concentrators (Q1842573): Difference between revisions

An \((n, \theta, k,\alpha)\)-bounded concentrator is a bipartite graph with \(n\) inputs, \(\theta n\) outputs, \(\theta< 1\), at most \(kn\) edges, and any set of at most \(\alpha n\) inputs is covered by a perfect matching. The author provides a direct construction of a family of bounded concentrators in which \(n\) tends to infinity linearly and \(\theta\), \(k\), and \(\alpha\) are fixed.