Wireless Expanders

This paper introduces an extended notion of expansion suitable for radio networks. A graph $G=(V,E)$ is called an $(α_w, β_w)$-{wireless expander} if for every subset $S \subseteq V$ s.t. $|S|\leq α_w \cdot |V|$, there exists a subset $S'\subseteq S$ s.t. there are at least $β_w \cdot |S|$ vertices in $V\backslash S$ adjacent in $G$ to exactly one vertex in $S'$. The main question we ask is the following: to what extent are ordinary expanders also good {wireless} expanders? We answer this question in a nearly tight manner. On the positive side, we show that any $(α, β)$-expander with maximum degree $Δ$ and $β\geq 1/Δ$ is also a $(α_w, β_w)$ wireless expander for $β_w = Ω(β/ \log (2 \cdot \min\{Δ/ β, Δ\cdot β\}))$. Thus the wireless expansion is smaller than the ordinary expansion by at most a factor logarithmic in $\min\{Δ/ β, Δ\cdot β\}$, which depends on the graph \emph{average degree} rather than maximum degree; e.g., for low arboricity graphs, the wireless expansion matches the ordinary expansion up to a constant. We complement this positive result by presenting an explicit construction of a "bad" $(α, β)$-expander for which the wireless expansion is $β_w = O(β/ \log (2 \cdot \min\{Δ/ β, Δ\cdot β\})$. We also analyze the theoretical properties of wireless expanders and their connection to unique neighbor expanders, and demonstrate their applicability: Our results yield improved bounds for the {spokesmen election problem} that was introduced in the seminal paper of Chlamtac and Weinstein (1991) to devise efficient broadcasting for multihop radio networks. Our negative result yields a significantly simpler proof than that from the seminal paper of Kushilevitz and Mansour (1998) for a lower bound on the broadcast time in radio networks.