Online matching in lossless expanders
share
Bauwens and Zimand [BZ 2019] have shown that lossless expanders have an interesting online matching property. The result appears in an implicit form in [BZ 2019]. We present an explicit version of this property which is directly amenable to typical applications, prove it in a self-contained manner that clarifies the role of some parameters, and give two applications. A (K, ϵ) lossless expander is a bipartite graph such that any subset S of size at most K of nodes on the left side of the bipartition has at least (1-ϵ) D |S| neighbors, where D is the left degree.The main result is that any such graph, after a slight modification, admits (1-O(ϵ)D, 1) online matching up to size K. This means that for any sequence S=(x_1, …, x_K) of nodes on the left side of the bipartition, one can assign in an online manner to each node x_i in S a set A_i consisting of (1-O(ϵ)) fraction of its neighbors so that the sets A_1, …, A_K are pairwise disjoint. "Online manner" refers to the fact that, for every i, the set of nodes assigned to x_i only depends on the nodes assigned to x_1, …, x_i-1. The first application concerns storage schemes for representing a set S, so that a membership query "Is x ∈ S?" can be answered probabilistically by reading a single bit. All the previous one-probe storage schemes were for a static set S. We show that a lossless expander can be used to construct a one-probe storage scheme for dynamic sets, i.e., sets in which elements can be inserted and deleted without affecting the representation of other elements. The second application is about non-blocking networks.
READ FULL TEXT