Wireless Expanders
Shirel Attali∗

Merav Parter†

David Peleg‡

Shay Solomon§

Abstract

arXiv:1802.07177v1 [] 20 Feb 2018

This paper introduces an extended notion of expansion suitable for radio networks. A graph
G = (V, E) is said to be an (αw , βw )-wireless expander if for every subset S ⊆ V s.t. |S| ≤ αw · |V |,
there exists a subset S 0 ⊆ S s.t. there are at least βw · |S| vertices in V \S that are adjacent in G
to exactly one vertex in S 0 . 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 β ≥ 1/∆ is also a
(αw , βw ) wireless expander for βw = Ω(β/ log(2·min{∆/β, ∆·β})). Thus the wireless expansion can be
smaller than the ordinary expansion by at most a factor that is logarithmic in min{∆/β, ∆ · β}, which,
in turn, depends on the average degree rather than the maximum degree of the graph. In particular, for
low arboricity graphs (such as planar graphs), the wireless expansion matches the ordinary expansion
up to a constant factor. We complement this positive result by presenting an explicit construction of
a “bad” (α, β)-expander for which the wireless expansion is βw = O(β/ log(2 · min{∆/β, ∆ · β}).
We also analyze the theoretical properties of wireless expanders and their connection to unique
neighbor expanders, and then demonstrate their applicability: Our results (both the positive and the
negative) yield improved bounds for the spokesmen election problem that was introduced in the seminal
paper of Chlamtac and Weinstein [7] 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 [11] for a lower bound on the broadcast time in radio networks.

∗

The Weizmann
The Weizmann
‡
The Weizmann
§
IBM Research.

†

Institute of Science. Email: shirel.attali@weizmann.ac.il.
Institute of Science. Email: merav.parter@weizmann.ac.il.
Institute of Science. Email: david.peleg@weizmann.ac.il.
Email: solo.shay@gmail.com.

1
1.1

Introduction
Background and motivation

An expander is a sparse graph that has strong connectivity properties [10]. There are several definitions
for expanders, with natural connections between them. We focus on the following combinatorial definition.
Expanders: Let G = (V, E) be an undirected graph. For a set S ⊂ V , let Γ(S) denote the set of
neighbors of the verices of S, and define Γ− (S) = Γ(S) \ S. We say that G is an (α, β) expander, for
positive parameters α and β, if |Γ− (S)| ≥ β · |S| for every S ⊆ V s.t. |S| ≤ α · |V |.
One of the main advantages of expanders is that they enable fast and effective dissemination of
information from a small group of vertices to the outside world. This property becomes less immediate
when we consider using the expansion property in the context of wireless communication networks. Such
networks can be represented by a specific kind of graphs, called radio networks [8]. A radio network is an
undirected (multihop) network of processors that communicate in synchronous rounds in the following
manner. In each step, a processor can either transmit or keep silent. A processor receives a message in
a given step if and only if it keeps silent and precisely one of its neighbors transmits in this step. If none
of its neighbors transmits, it hears nothing. If more than one neighbor (including itself) transmits in a
given step, then none of the messages is received. In this case we say that a collision occurred. It is
assumed that the effect at processor u of more than one of its neighbors transmitting is the same as of
no neighbor transmitting, i.e., a node cannot distinguish a collision from silence.
The usual definition of expanders is not enough to ensure fast message propagation in radio networks.
Consider, for example, a radio network C + consisting of a complete graph C with one more vertex s0 ,
the source, connected to two vertices x and y from C. Obviously this is a good expander, but in this
case, after the first step of broadcast, if all the vertices that received the message (i.e., the three vertices
s0 , x and y) transmit it simultaneously to all their neighbors, then no one will hear it. This motivates
considering another definition of expanders, namely, unique neighbor expanders (or unique expanders, in
short) [2].
Unique neighbor expanders: Let G = (V, E) be an undirected graph. We say that G is an (αu , βu )unique neighbor expander if for every S ⊆ V s.t. |S| ≤ αu · |V |, there are at least βu · |S| vertices in V \S
that are adjacent in G to exactly one vertex in S.
Clearly, if G is a unique expander with good parameters, then broadcasting on it can be fast (again,
by requiring all the vertices that received the message to send it to all their neighbors). Unfortunately,
it seems that unique neighbor expansion might be hard to come by. For example, while the graph C +
described above is a good (ordinary) expander, it is clearly not a good unique expander, as can be realized
by considering the set S = {x, y, s0 }. (In general, ordinary expanders might have rather small unique
neighbor expansion, as will be shown soon.) In addition, explicit constructions of unique expanders are
rather scarce and known only for a limited set of parameters [2, 6].
The key observation triggering the current paper is that the property required from unique expanders
might be stronger than necessary. This is because there is no reason to require all the vertices that received
the message to send it. Rather, it may be enough to pick a subset X of this set, that has a large set of
unique neighbors, and require only the vertices of X to transmit. This may be an attractive alternative
since such a property may be easier to guarantee than unique neighbor expansion, and therefore may be
achievable with better parameters α and β. (Note, e.g., that this property holds for our example graph
C + .) This observation thus motivates our definition for a new variant of expanders.
Wireless expanders: Let G = (V, E) be an undirected graph. We say that G is an (αw , βw )-wireless
expander if for every S ⊆ V s.t. |S| ≤ αw · |V |, there exists a subset S 0 ⊆ S s.t. there are at least βw · |S|
vertices in V \S that are adjacent to exactly one vertex in S 0 .
In this paper we are interested in investigating the properties of wireless expanders and the relationships between these graphs and the classes of ordinary expanders and unique neighbor expanders. We

1

ask the following questions: by how much does the relaxed definition of wireless expanders (compared to
unique neighbor expanders) help us in providing expanders with better parameters that are suitable for
radio network communication? More specifically, given an (α, β)-expander, can we prove that it is also
an (αw , βw )-wireless expander with αw = f (α, β) and βw = g(α, β), for some functions f and g?

1.2

Our Contribution

We present several results relating the parameters of the different notions of expanders. We begin by
investigating the relationships between ordinary expanders and the more strict notion of unique neighbor
expanders.
• Let G = (V, E) be a d-regular graph that is an (αu , βu )-unique neighbor expander, and let λ = λ2
denote the second largest eigenvalue of its adjacency matrix, given by auv = 1 if (u, v) ∈ E and auv =
0 otherwise. Then G is an (α, β)-expander with α = αu and β ≥ (1 − 1/d) · βu + (d − λ)/d · (1 − αu ).
• Suppose G = (V, E) is an (α, β)-expander with maximum degree ∆. Then it is also an (αu , βu )unique expander with αu = α, and βu ≥ 2β − ∆. On the other hand, we show that there is an
(α, β) bipartite expander whose unique expansion is βu ≤ 2β − ∆.
We then turn to consider our new relaxed notion of wireless expander. Our key contribution is in providing
nearly tight characterization for the relation between ordinary expanders and wireless expanders. On the
positive side, using the probabilistic method, we show:
Theorem 1.1 (Positive Result) For every ∆ ≥ 1, β ≥ 1/∆, every (α, β)-expander G with maximum degree ∆ is a also an (αw , βw )-wireless expander with αw ≥ α and
βw = Ω(β/ log(2 · min{∆/β, ∆ · β})).
Our probabilistic argument has some similarity to the known decay method [5], which is a standard
technique for coping with collisions in radio networks. Roughly speaking, in the decay protocol of [5],
time is divided into phases of log n rounds and in the ith round of each phase, each node that holds a
message transmits it with probability 2−i . Hence, each node that has a neighbor that holds a message,
receives it within O(log n) phases. We use the idea of the decay method to show the existence of a subset
S 0 ⊆ S with a large unique neighborhood in Γ(S).
An important feature of our argument is that it bounds the deviation of the wireless expansion from the
ordinary expansion as a function of the average-degree rather than the maximum degree. As β gets closer
to ∆ or to 1/∆, this finer dependence leads to significantly better results than what could be achieved using
the standard decay argument; our argument is also arguably simpler than the standard decay argument.
As a technical note, we use the probabilistic method to prove a lower bound of Ω(β/ log(2 · ∆/β)) on
βw , and then we push it up to the bound of Theorem 1.1 via a separate deterministic argument. As
a corollary, for the important family of low arboricity graphs, which includes planar graphs and more
generally graphs excluding a fixed minor, the wireless expansion matches the ordinary expansion up to
a constant factor. (Indeed, the arboricity is at least min{∆/β, ∆ · β}; see Section 2.1 for the definition
of arboricity.) In particular, this shows that radio broadcast in low arboricity graphs can be done much
more efficiently than what was previously known!
Beyond the probabilistic argument, we also provide explicit deterministic arguments that obtain better
parameters (by a constant factor); these are deferred to the appendix.
We also show that asymptotically, no tighter connection can be established:
Theorem 1.2 (Negative Result) There exists an (α, β)-expander with maximum degree ∆, whose
wireless expansion is βw = O(β/ log(2 · min{∆/β, ∆ · β}).

2

The explicit construction of this bad graph example is perhaps the most technically challenging result of
this paper. Our explicit construction has interesting connections to related constructions that have been
studied in the context of broadcast in radio networks [3, 11]. For instance, our “core graph” from Section
4.3.1 is reminiscent of a fundamental construction from [3]. However, while the construction of [3] is
implicit (using the probabilistic method), our construction is explicit and can be viewed in some sense
as the deterministic counterpart of [3]; moreover, our construction is arguably much simpler than that
of [3]. We view this explicit construction as the technical highlight of our work, and anticipate that it
will find further applications.
An additional application of both our positive and negative results is to the Spokesman Election
problem introduced in the seminal paper of [7], where given a bipartite graph G = (S, N, E), the goal
is to compute a subset S 0 ⊆ S with the maximum number of unique neighbors Γ1 (S 0 ) in N . More
specifically, we provide tight bounds for this problem, which apply to any expansion and average degree
parameters, whereas the previous result of [7] applies only to one specific (very large) expansion parameter
and only with respect to the maximum degree (rather than the average degree, which is a finer measure).
In Section 4.2.1, we provide a detailed comparison to the bounds obtained by [7].
Finally, another application of our negative result, and of our explicit core graph in particular, is
in the context of broadcast lower bounds in radio networks. In their seminal paper, Kushilevitz and
Mansour [11] proved that there exist networks in which the expected time to broadcast a message is
Ω(D log(n/D)), where D is the network diameter and n is the number of vertices, and this lower bound
is tight for any D = Ω(log n) due to a highly nontrivial upper bound by Czumaj and Rytter [9]. Since
the upper bound of [9] holds with high probability, it implies that the lower bound Ω(D log(n/D)) of [11]
also holds with high probability. Newport [12] presented an interesting alternative proof to the one by
Kushilevitz and Mansour. Although short and elegant, Newport’s proof relies on two fundamental results
in this area, due to Alon et al. [1] and Alon et al. [3] – Lemma 3.1 in [12] – whose proof is intricate.
Also, as with Kushilevitz and Mansour’s proof, Newport only proves an expected lower bound on the
broadcast time, with the understanding that a high probability bound follows from [9]. By unwinding
the ingredients of Newport’s proof, the resulting proof (especially for a high probability bound on the
broadcast time) is long and intricate. Using the properties of our explicit core graph construction, we
derive a simple and self-contained proof for the same lower bound, arguably much simpler than that
of [11, 12]. An important advantage of our proof over [11, 12] is that it gives a high probability bound on
the broadcast time directly, i.e., without having to take a detour through the upper bound of [9].
Summarizing, besides the mathematical appeal of wireless expanders and their connections to wellstudied types of expanders, we demonstrate that they find natural applications in the well-studied area
of radio networks. We anticipate that a further study of wireless expanders will reveal additional applications, also outside the scope of radio networks, and we thus believe it is of fundamental importance.

1.3

Organization

In Section 2 we introduce the notation and definitions used throughout. We investigate the relations
between ordinary expanders and unique neighbor expanders in Section 3. Section 4 is devoted to our
new notion of wireless expanders, where we present nearly tight characterization for the relation between
ordinary expanders and wireless expanders. We start (Section 4.1) with describing our basic framework;
the positive and negative results are presented in Section 4.2 and Section 4.3, respectively. (As mentioned,
some positive results are deferred to the appendix. These improve on the parameters provided in Section
4.2 by constant factors, using explicit deterministic arguments.) Our results for the Spokesman Election
problem [7] are given in Section 4.2.1. Finally, Section 5 is devoted to our alternative lower bound proof
of Ω(D log(n/D)) on the broadcast time in radio networks.

3

2
2.1

Preliminaries
Graph Notation

For an undirected graph G = (V, E), vertex v ∈ V and
S a subset S ⊆ V , denote the set of v’s neighbors
in G by Γ(v) = {u | (u, v) ∈ E}, and let Γ(S) = v∈S Γ(v) be the neighborhood of a vertex set S in
G (including neighbors that belong to S itself), and Γ− (S) = Γ(S) \ S be the set of neighbors external
to S. Also define Γ(v, S) = Γ(v) ∩ S as the neighbors of v in the subset S. The expansion of S is the
ratio |Γ− (S)|/|S|. The unique-neighborhood of S, denoted by Γ1 (S), is the set of vertices outside S that
have a unique neighbor from S. The unique-neighbor expansion of S is the ratio |Γ1 (S)|/|S|. Let S 0
be an arbitrary subset of S. The S-excluding neighborhood of S 0 , denoted by ΓS (S 0 ), is the set of all
vertices outside S that have at least one neighbor from S 0 . Similarly, the S-excluding unique-neighborhood
of S 0 , denoted by Γ1S (S 0 ), is the set of all vertices outside S that have a unique neighbor from S 0 . In
particular, Γ1 (S) = Γ1S (S). The wireless expansion of S is the maximum ratio |Γ1S (S 0 )|/|S| over all
subsets S 0 of S. For two sets S, T ⊂ V , let e(S, T ) be the set of edges connecting S and T . For vertex
v ∈ V , let deg(v) = degG (v) denote the degree of v in G, i.e., the number of v 0 s neighbors, and let
∆(G) = max{deg(v) | v ∈ V } be the maximum degree over all the vertices in G. For set S ⊂ V and
vertex v ∈ V , let deg(v, S) = deg(v) ∩ S be the number of v 0 s neighbors that are in S. For two vertices
v, u ∈ V , let d(u, v) be the distance between u and v (i.e., the length of the shortest path connecting
them), and let D = D(G) = max{d(u, v) | u, v ∈ V } be the diameter of the graph, i.e. the maximum
distance between any two vertices.
We use the combinatorial definition for (vertex) expansion, which requires that every (not too large)
set of vertices of the graph has a relatively large set of neighbors. Specifically, an n-vertex graph G is
called an (α, β) vertex expander for positive parameters α and β, if every subset S ⊆ V s.t. |S| ≤ αn has
many external neighbors, namely, |Γ− (S)| ≥ β · |S|. The (ordinary) expansion β(G) of G is defined as the
minimum expansion over all vertex sets S ⊆ V of size |S| ≤ αn, namely, β(G) = min{|Γ− (S)|/|S| | S ⊆
V, |S| ≤ αn}. A similar definition appears in the literature for bipartite graph, namely, a bipartite graph
G = (L, R, E) with sides L and R, such that every edge from E ⊂ L × R connects one vertex of L and
one vertex of R is called an (α, β) bipartite vertex expander if every subset S ⊂ L s.t. |S| ≤ α|L| has
at least β|S| neighbors in R. It is usually assumed that the two sides L and R of the bipartition are of
(roughly) the same size.
A graph G = (V, E) has arboricity η = η(G) if


|E(U )|
η = max
,
U ⊆V |U | − 1
where E(U ) = {(u, v) ∈ E | u, v ∈ U }. Thus the arboricity is the same (up to a factor of 2) as the
maximum average degree over all induced subgraphs of G. It is easy to see that for any (α, β)-expander
with maximum degree ∆, the arboricity is at least min{∆/β, ∆ · β}.

2.2

Unique Neighbor and Wireless Expanders

Let us now define formally the notions of unique and wireless expanders. Let G = (V, E) be an n-vertex
undirected graph. We say that G is an (αu , βu )-unique expander [2] if for every S ⊆ V s.t. |S| ≤ αu n, there
are at least βu · |S| vertices in V \S that are adjacent to exactly one vertex in S, namely, |Γ1 (S)| ≥ βu · |S|.
The unique-neighbor expansion βu (G) of G is defined as the minimum unique-neighbor expansion over
all vertex sets S ⊆ V with |S| ≤ αu n, namely,
βu (G) = min{|Γ1 (S)|/|S| | S ⊆ V, |S| ≤ αu n}.
We say that G is an (αw , βw )-wireless expander if for every S ⊆ V s.t. |S| ≤ αw n, there exists a
subset S 0 ⊆ S s.t. there are at least βw · |S| vertices in V \S that are adjacent in G to exactly one vertex
4

in S 0 , i.e., |Γ1S (S 0 )| ≥ βw · |S|. The wireless expansion βw (G) of G is defined as the minimum wireless
expansion over all sets S ⊆ V with |S| ≤ αw n, namely,
βw (G) = min{max{|Γ1S (S 0 )|/|S| | S 0 ⊆ S} | S ⊆ V, |S| ≤ αw n}.
In our arguments, we usually fix α and study the relations between the β-values for different notions of
expanders. The following connection is easy to verify.
Observation 2.1 If α = αu = αw , then β(G) ≥ βw (G) ≥ βu (G).

3

Relations between β and βu

Let G = (V, E) be a d-regular undirected graph and let A = AG = (auv )u,v∈V be its adjacency matrix
given by auv = 1 if (u, v) ∈ E and auv = 0 otherwise. Since G is d-regular, the largest eigenvalue of A is
d, corresponding to the all-1 eigenvector (as 1/d · A is a stochastic matrix). Let λ = λ2 denote the second
largest eigenvalue of G.
Lemma 3.1 If a d-regular graph G = (V, E) is an (αu , βu )-unique expander, then it also an (α, β)expander with α = αu and β ≥ (1 − 1/d) · βu + (d − λ) · (1 − αu )/d.
Proof: Alon and Spencer [4] prove that every partition of the set of vertices V into two disjoint subsets
A and B satisfies |e(A, B)| ≥ (d − λ) · |A| · |B|/|V |. In our case (i.e. A = S, B = V \ S = S̄, and
|S| ≤ αu · |V |) we get that
|S| · |S̄|
|V |
|S| · (|V | − αu · |V |)
≥ (d − λ) ·
|V |
= (d − λ) · |S| · (1 − αu ).

|e(S, S̄)| ≥ (d − λ) ·

Moreover, by the expansion properties, there exists a set U of at least βu · |S| vertices in Γ− (S) that
have a unique neighbor in S. From uniqueness, we have e(S, U ) = |U | ≥ βu |S|. Thus, there are at least
(d − λ) · |S| · (1 − αu ) − |U | edges in e(S, S̄) that are not connect to the vertices in U (i.e. in e(S, S̄ \ U )).
Now, because G is d-regular, we get that there exist at least |U | + ((d − λ) · |S| · (1 − αu ) − |U |)/d vertices
in Γ− (S). Hence, we get
((d − λ) · |S| · (1 − αu ) − |U |)
|Γ− (S)| ≥ |U | +
d


1
(d − λ) · (1 − αu )
=
1−
· |U | +
· |S|
d
d


1
(d − λ) · (1 − αu )
≥
1−
· βu |S| +
· |S|
d
d



1
(d − λ) · (1 − αu )
=
1−
· βu +
· |S|
d
d
thus, G is a (α, β)-expander with α ≥ αu and β ≥ (1 − 1/d) · βu + ((d − λ) · (1 − αu )/d.
It is known (and easy to verify) that ordinary expanders whose expansion is close to the (maximum)
degree in the graph are also good unique expanders, or formally:
Lemma 3.2 Suppose G = (V, E) is an (α, β)-expander with maximum degree ∆. Then it is also a unique
(αu , βu )-expander, with αu = α and βu ≥ 2β − ∆.
5

Remark. Substituting β = (1 − ε)∆ (for ε ≤ 1/2), we obtain βu ≥ (1 − 2ε)∆.
The lower bound 2β − ∆ on the unique-neighbor expansion βu provided by Lemma 3.2 is meaningful
only when β is larger than ∆/2. The following example shows that this lower bound 2β − ∆ is tight.
Lemma 3.3 For any ∆ and β such that ∆/2 ≤ β ≤ ∆, there is an (α, β) bipartite expander Gbad =
(S, N, E) with maximum degree ∆ whose unique expansion is βu ≤ 2β − ∆.
Proof: Construct the graph Gbad as follows. Let S = {v1 , . . . , vs }, with s = |S|, and suppose that
each vertex vi ∈ S has exactly ∆ neighbors, all of which are in N . (For technical convenience, we define
v0 = vs , v1 = vs+1 ; that is, the vertices v1 and vs are not different than the other vertices (they should
not be viewed as “endpoints”, but rather part of an implicit “cycle”). Moreover, for each i = 1, . . . , s,
the vertices vi and vi+1 have exactly ∆ − β common neighbors; that is, |Γ(vi ) ∩ Γ(vi+1 )| = ∆ − β. More
concretely, writing Γ(vi ) = {vi1 , . . . , vi∆ }, we have that
∆−β
1
Γ(vi ) ∩ Γ(vi+1 ) = {viβ+1 , . . . , vi∆ } = {vi+1
, . . . , vi+1
}.
1 , . . . , v ∆−β
In other words, the “last” ∆−β neighbors viβ+1 , . . . , vi∆ of vi are the “first” ∆−β neighbors vi+1
i+1
of vi+1 , respectively. (See Figure 1 for an illustration.)

Figure 1: An illustration of a worst-case scenario for the unique-neighbor expansion.
This means that for each i = 1, . . . , s, the first (resp., last) ∆ − β neighbors of vi are also neighbors of
vi−1 (resp, vi+1 ). The remaining ∆ − 2(∆ − β) = 2β − ∆ neighbors of vi , however, are uniquely covered by
vi . It follows that the number of vertices in the neighborhood of S that are uniquely covered by vertices
from S is equal to s(2β − ∆). Consequently, the unique neighbor expansion βu is 2β − ∆, as claimed.
Noting that the ordinary expansion is β completes the proof of the lemma.
Remarks. (1) The meaning of Lemma 3.3 is that a graph with high (ordinary) expansion may have
unique neighbor expansion of zero. For example, in the graph Gbad described in the proof of Lemma 3.3,
the unique-neighbor expansion is 2β − ∆, but the wireless expansion is at least max{2β − ∆, ∆/2}. To
see that, let S 0 be a subset of S and suppose S 0 = S1 ∪ S2 ∪ . . . ∪ Sk such that each Si is a sequence
of consecutive vertices, i.e., using the previous notations, for Si of size l, Si = {vj , .., vj+l } for some
index 1 ≤ j ≤ s. Suppose also that between every two sets Si and Sj there is at least one vertex
that is not in S 0 (in other words, we can’t expand Si to be a longer secuence in S 0 ). Therefore, to
compute βw , it is enough to compute the expansion parameter for each Si = {vj , . . . , vj+l }. Consider
two options for choosing the set S 00 ⊂ Si . The first choice is to take S 00 = Si . Then we get an expansion
6

of f (l) = (l∆ − 2(l − 1)(∆ − β))/l = ((2 − l)∆ + 2(l − 1)β)/l. The second choice is to take into
S 00 every second vertex in the sequence of Si . Then we get an expansion of g(l) = l∆/(2l) if l is
even, and g(l) = (l + 1)∆/(2l) if l is odd. (In the case where S 0 = S we get in the first choice an
expansion of f (l) = l(2β − ∆)/l = 2β − ∆ and in the second an expansion of g(l) = (l − 1)∆/(2l)).
Thus, βw ≥ min{max{g(l) , f (l)} | l > 0}. As f 
(l) and g(l) are both decreasing functions, we get
that βw ≥ max{liml→∞ g(l) , liml→∞ f (l)} = max 2β − ∆ , ∆
2 . This calculation also shows that if
β = ∆/2, then the unique-neighbor expansion becomes 0, but the wireless expansion becomes ∆/2.
(2) Although the bipartite graph used in the proof of Lemma 3.3 is an ordinary bipartite expander
(according to the definition given in Section 2.1), note that the sizes of the two sides S and N differ by
a factor of β. Also, it does not provide an ordinary non-bipartite expander, because the expansion is
achieved only on one side, from S towards N . Nevertheless, one can plug this “bad” bipartite graph on
top of an ordinary (α, β)-expander with a possibly good unique-neighbor expansion, so that the graph
resulting from this tweak is an ordinary (α, β)-expander with a unique-neighbor expansion bounded by
2β − ∆. Notice, however, that the maximum degree in the resulting graph, denoted by ∆0 , may be as
large as the sum of the maximum degrees of the “bad” bipartite graph and the (α, β)-expander that we
started from. For example, if ∆0 = 2∆, then the unique-neighbor expansion of the resulting graph is
bounded by 2β − ∆ = 2β − ∆0 /2. Since we apply a similar tweak in Section 4.3 (in the context of wireless
expansion rather than unique expansion), we omit the exact details of this rather simple tweak from the
extended abstract.

4
4.1

Bounds on Wireless Expansion
Our Framework

Consider an arbitrary (ordinary) (α, β)-expander G. As shown in Section 3, the unique-neighbor expansion βu provided by G may be zero even if the ordinary expansion β is high. In what follows we
demonstrate that the wireless expansion βw (G) of G cannot be much lower than its ordinary expansion
β(G). Moreover, we prove asymptotically tight bounds on the ratio β(G)/βw (G). This yields a strong
separation between the unique-neighbor expansion and the wireless expansion, which provides a natural motivation for studying wireless expanders, particularly in applications where we are given a fixed
expander network (that cannot be changed).
First let us observe that by Obs. 2.1, Lemma 3.2 yields the following bound on βw .
Lemma 4.1 Suppose G = (V, E) is an (α, β)-expander with maximum degree ∆. Then it is also a
wireless (αw , βw )-expander with αw = α and βw ≥ 2β − ∆.
Throughout what follows, we simplify the discussion by focusing attention to an arbitrary bipartite
graph GS = (S, N, ES ) with sides S and N , such that |N | ≥ β · |S|. We assume that no vertex of GS is
isolated, i.e., all vertex degrees are at least 1.
Note that this bipartition can be thought of as representing all edges in the original graph G that
connect an arbitrary vertex set S with its neighborhood N = Γ− (S). While in G there might be edges
internal to S and/or N , ignoring these edges has no effect whatsoever on the expansion bounds.
Our goal is to show the existence of a subset S 0 of S in the graph GS , whose S-excluding uniqueneighborhood Γ1S (S 0 ) is not much smaller than the entire neighborhood N of S. Of course, this would
imply that the wireless expansion of an arbitrary set S in G (of any size) is close to its ordinary expansion,
yielding the required result.

4.2

Positive Results: Ordinary Expanders are Good Wireless Expanders

Let
the set S (resp., N ) in the graph GS . That is, δS =
P δS (resp., δN ) be the average
P degree of
0
u∈S deg(u, N )/|S| and δN =
u0 ∈N deg(u , S)/|N |. Clearly, δN , δS ≥ 1. In this section, we show that
βw can be bounded from below as a function of min{δS , δN }.
7

We begin by considering an (α, β)-expander G for β ≥ 1. We now show:
Lemma 4.2 For every β, ∆ ≥ 1, there exists a subset S ∗ ⊆ S, satisfying that
|Γ1S (S ∗ )| = Ω(|N |/ log 2δN ) = Ω(β/ log 2δN ) · |S|. Hence, βw = Ω(β/ log 2(∆/β)).
Proof: Since β ≥ 1, we have |S| ≤ |N |, 1 ≤ δN ≤ δS and δN ≤ ∆/β. The proof relies on the
probabilistic method. First, consider the set N 0 of all vertices from N with degree at most 2δN . Note
that |N 0 | ≥ |N |/2 and that all vertices of N 0 have positive degree. We now divide the subset N 0 into
k = blog 2δN c subsets depending on their degree in S, where the ith subset Ni consists of all vertices
u ∈ N 0 with deg(u, S) ∈ [2i , 2i+1 ). Let Nj be the largest subset among these k subsets. We have that
|Nj | ≥ |N |/k = Ω(|N |/ log 2δN ) = Ω(|N |/ log 2(∆/β)). We next show that there exists a subset S ∗ ⊆ S
such that Γ1S (S ∗ ) contains a constant fraction of the vertices of Nj .
Consider a random subset S 0 ⊆ S obtained by sampling each vertex u ∈ S independently with
probability 1/2j . For every vertex u ∈ Nj , let X(u) ∈ {0, 1} be the indicator random variable that takes
value 1 if u has exactly one neighbor in S 0 . As deg(u, S) ∈ [2j , 2j+1 ), we have that
IE (() X(u)) = IP(X(u) = 1) = deg(u, S)/2j · (1 − 1/2j )deg(u,S)−1
j+1 −1

≥ (1 − 1/2j )2

≥ e−3 .

P
Hence, u∈Nj IE (() X(u)) = Ω(|Nj |) = Ω(β|S|/ log 2(∆/β)). We get that the expected number of vertices
in N that are uniquely covered by a random subset S 0 is Ω(β|S|/ log 2(∆/β)). Hence, there exists a subset
S ∗ ⊆ S with
|Γ1S (S ∗ )| = Ω(β/ log 2(∆/β)) · |S|. The lemma follows.
In Appendix A, we provide a sequence of deterministic arguments that obtain better bounds for βw (by
constant factors) compared to the probabilistic argument shown above.
We now turn to consider the case β < 1. In this case the bound on the wireless expansion depends
on δS , namely, on the average degree in the larger set S. We show:
Lemma 4.3 For every ∆ ≥ 1 and β ∈ [1/∆, 1), there exists a subset S ∗ ⊆ S, satisfying that |Γ1S (S ∗ )| =
Ω(β/ log δS ) · |S|. Since δS ≤ β · ∆, we have βw = Ω(β/ log 2(∆ · β)).
Proof: Let S 0 ⊆ S be the set of all vertices u ∈ S with deg(u, N ) ≤ 2δS , and note that |S 0 | ≥ |S|/2. Let
N 0 = Γ− (S 0 ) be the set of neighbors of S 0 in N . By the expansion of G, we have |N 0 | ≥ β · |S 0 | ≥ β|S|/2.
We now claim that there exists a subset S 00 ⊆ S 0 satisfying Γ− (S 00 ) = N 0 and |S 00 | ≤ |N 0 |. To see this,
initially set S 00 to be empty. Iterate over the vertices of S 0 and add a vertex u ∈ S 0 to S 00 only if it
covers a new vertex of N 0 (i.e., it has a new neighbor in N 0 that has not been covered before). Then
|S 00 | ≤ |N 0 | and hence in the induced bipartite graph G0 with sides S 00 and N 0 , the expansion measure
β’, with β 0 = |N 0 |/|S 00 |, is at least 1. The average degree of a vertex u ∈ N 0 in the graph G0 is bounded
by |E(G0 )|/|N 0 | ≤ 2δS · |S 00 |/|N 0 | ≤ 2δS . Employing the argument of Lemma 4.2 on the bipartite graph
G0 , we get that there exists a subset S ∗ ⊆ S 00 satisfying |Γ1S 00 (S ∗ )| = Ω(|N 0 |/ log 4δS ) = Ω(β/ log 2δS )|S|.
Since δS ≤ ∆ · β, it follows that βw = Ω(β/ log 2(∆ · β)).
Theorem 1.1 follows from Lemmas 4.2 and 4.3.
4.2.1

Relation to the Spokesman Election problem [7]

Motivated by broadcasting in multihop radio networks, Chalmtac and Weinstien [7] defined the spokesmen
election problem. In this problem, given a bipartite graph G = (S, N, E), the goal is to compute a subset
S 0 ⊆ S with the maximum number of unique neighbors Γ1 (S 0 ) in N . This problem was shown in [8]
to be NP-hard. In [7], an approximation scheme is presented that computes a subset S 0 ⊆ S with
|Γ1 (S 0 )| ≥ |N |/ log |S|, and this approximation scheme was then used to devise efficient broadcasting
algorithms for multihop radio networks.

8

The bounds provided in Lemmas 4.2 and 4.3 refine and strengthen upon the bound of [7]. Our bounds
show that |Γ1 (S 0 )| cannot be smaller than |N | by more than a factor that is logarithmic in 2 min{δN , δS },
which depends on the average degree in G, whereas the bound of 4.3 did not preclude the possibility of
|Γ1 (S 0 )| being smaller than |N | by a factor of log |S|. Note that min{δN , δS } is always upper bounded by
|S|, but can be much smaller than it. In particular, min{δN , δS } is always low in low arboricity graphs
(even if the maximum degree is huge), regardless of |S|.
We remark that our randomized approach of choosing the subset S 0 ⊆ S is extremely simple, and in
particular, it yields a much simpler solution to the Spokesman Election problem than that of [7]. Since
the solution to this problem was used in [7] to devise efficient broadcasting algorithms for multihop radio
networks, our solution can be used to obtain simpler broadcasting algorithms for multihop radio networks
than those of [7].
In the next section (Section 4.3), we show that our positive results for (α, β)-expanders are essentially
the best that one can hope for, by providing a “bad” expander example. A bad graph expander example
for the related Spokesman Election problem was given in [7], but our graph example is stronger than that
of [7] in several ways, and is based on completely different ideas. The graph example of [7] is tailored
for the somewhat degenerate case where |N | = Ω(|S|!), whence N is exponentially larger than S, thus
the expansion of the bad graph (and the degree) is huge. In addition, in their example, one cannot
uniquely cover more than |N |/ log(|S|) = |N |/ log log |N | vertices of N , leaving a big gap between their
positive and negative results. Our bad graph example, in contrast, works for any expansion parameter
β. Moreover, similarly to our positive result, the bounds implied by our negative result depend on the
average degree of the graph rather than the maximum degree or the size of S. In particular, by taking β
to be constant and ∆ to be sufficiently large, our graph example shows that one cannot cover more than
|N |/ log |N | vertices of N , which not only matches our positive result, but also closes the gap left by [7].

4.3

Negative Results: Worst-Case Expanders

In this section we present a “bad graph ” expander construction. The description of our construction is
given in three stages. First, in Section 4.3.1 we construct a bipartite graph GS = (S, N, ES ) with sides
S and N that satisfies two somewhat contradictory requirements: On the one hand, for every subset S 0
of S, |Γ(S 0 )| ≥ log 2|S| · |S 0 |. Hence the ordinary expansion of GS , denoted by β, is at least log 2|S|.
On the other hand, for every subset S 0 of S, |Γ1S (S 0 )| ≤ (2/ log 2|S|) · |N |. Hence the wireless expansion
of GS , denoted βw , satisfies βw ≤ β(2/ log 2|S|). Although this graph is an ordinary bipartite expander
(according to the definition given in Section 2.1), note that the size of N is greater than that of S by a
factor of log 2|S|. Also, it does not provide an ordinary non-bipartite expander, because the expansion
is achieved only on one side, from S towards N . Nevertheless, it provides the core of our worst-case
expander, and is henceforth referred to as the core graph. Next, in Section 4.3.2 we describe a generalized
core graph G∗S = (S ∗ , N ∗ , ES∗ ) with an arbitrary expansion β ∗ , while preserving the same upper bound
on the wireless expansion. Finally, in Section 4.3.3 we plug the generalized core graph on top of an
ordinary expander G(V, E) with a possibly good wireless expansion, such that N ∗ ⊆ V and S ∗ ∩ V = ∅,
and demonstrate that the resulting graph G̃ = (V ∪ S ∗ , E ∪ ES∗ ) is an ordinary expander with a similar
expansion but a poor wireless expansion. While the generalized core graph is bipartite, the ordinary
expander G that we started from does not have to be bipartite. If the original expander G is bipartite,
we can ensure that the expander resulting from our modification will also be bipartite.
4.3.1

The Core Graph

Lemma 4.4 For any integer s ≥ 1, there is a bipartite graph GS = (S, N, ES ) such that:
1. s := |S| and |N | = s log 2s.
2. Each vertex in S has degree 2s − 1.

9

3. The maximum degree ∆N of a vertex in N is s, and the average degree δN of a vertex in N is at
most 2s/ log 2s.
4. For every subset S 0 of S, |Γ(S 0 )| ≥ log 2s · |S 0 |. (Hence the ordinary expansion, denoted β, is at
least log 2s.)
5. For every subset S 0 of S, |Γ1S (S 0 )| ≤ 2s = (2/ log 2s) · |N |. (Hence the wireless expansion, denoted
βw , satisfies βw ≤ β(2/ log 2s).)
Proof: We assume for simplicity that s is an integer power of 2, which may effect the bounds in the
statements of the lemma by at most a small constant. To describe the edge set ES of GS , consider a
perfect binary tree TS with s leaves (and s − 1 internal vertices). We identify each leaf z of TS with a
unique vertex of S. Each vertex v of TS is
Sassociated with a set Nv of vertices from N ; all these vertex sets
are pairwise disjoint, and we have N = v∈TS Nv . For a vertex v at level i of the tree, i = 0, 1, . . . , log s,
the set Nv contains s/2i vertices. Thus the sizes of these vertex sets decrease geometrically with the
level, starting with the set Nrt at the root rt that consists of s vertices, and ending with singletons at
the leaves. Denote by Ni the union of the sets Nv over all i-level vertices in TS . For all i = 0, 1, . . . , log s,
we have |Ni | = s, hence |N | = s log
in TS
S
S 2s. For a leaf z in TS , let A(z) denote the set of its ancestors
(including z itself), and let N̂z = w∈A(z) Nw . Define E(z) = {(z, v) | v ∈ N̂z }. Then ES = z∈S E(z).
(See Fig. 2 for an illustration.)

Figure 2
Observation 4.5 There is an edge between vertex z ∈ S and vertex v ∈ N iff the unique vertex w in TS
such that v ∈ Nw is an ancestor of z in TS .
P s i
Note that the degree of each vertex z ∈ S, namely |E(z)|, is equal to log
i=0 2 = 2s − 1. On the other
hand, the degrees of vertices in N are not uniform. For a vertex v in TS , each vertex in Nv is incident on
the descendant leaves of v. This means that if v is at level i of TS , then all vertices in Nv have degree
2log s−i = s/2i . Hence, the maximum degree ∆N of a vertex in N is s and the average degree δN of a
vertex in N is given by
log s

δN

=

1 X
(
|Ni |(s/2i ))
|N |
i=0

10

log s

=

1 X s2
2s2
2s
)
≤
(
=
.
i
|N |
2
s log 2s
log 2s
i=0

Next, we lower bound the expansion β of the graph GS . Fix an arbitrary set S 0 ⊆ S of size k, for any
1 ≤ k ≤ s, and consider the set of k leaves in TS identified with S 0 , denoted by s1 , . . . , sk . Recall that
the level of the root rt is 0, the level of its children is 1, etc., the level of the leaves of TS is log s; in
what follows we say that a vertex has inverse-level j if its level in TS is log s − j. For each vertex v at
inverse-level j in TS , the associated vertex set Nv has size 2j . Next, we distinguish between inverse-levels
at most blog kc and higher inverse-levels. For any inverse-level 0 ≤ j ≤ blog kc, the number of ancestors
of the k leaves s1 , . . . , sk in the tree TS is at least k/2j , hence the union of the corresponding vertex sets is
of size at least k. (The lower bound is realized when the k leaves are consecutive to each other in TS .) For
each inverse-level higher than blog kc, the number of ancestors of the k leaves s1 , . . . , sk may be as small
as 1, but the vertex set associated with such an ancestor is of size at least k. It follows that the union of
the corresponding vertex sets at each level is lower bounded by k, and so the union of the vertex sets of all
ancestors of the k leaves s1 , . . . , sk over all levels is at least (log s+1)·k. By Observation 4.5, all the vertices
in this union are neighbors of the vertices in S 0 , thereby yielding |Γ(S 0 )| ≥ (log s + 1) · k = log 2s · |S 0 |. It
follows that β ≥ log 2s.
It remains to upper bound the wireless expansion βw of the graph GS . Fix an arbitrary set S 0 ⊆ S,
and recall that Γ1S (S 0 ) denotes the set of all vertices outside S that have a single neighbor from S 0 .
For a S
vertex v in TS , let D(v) denote the set of its descendants in TS (including v itself), and let
Ňv = w∈D(v) Nw . We argue that for any vertex v at inverse-level j, for j = 0, 1, . . . , log s, it holds that
|Γ1S (S 0 ) ∩ Ňv | ≤ 2j+1 − 1. The proof is by induction on j. Basis j = 0. In this case v is a leaf, hence
Ňv = Nv = {v}, and so |Γ1S (S 0 ) ∩ Ňv | ≤ 1 = 2j+1 − 1. Induction step: Assume the correctness of the
statement for all smaller values of j, and prove it for j. Consider an arbitrary vertex v at level j, and
denote its left and right children by vL and vR , respectively. Suppose first that S 0 contains at least one
leaf zL from the subtree of vL and at least one leaf zR from the subtree of vR . By Observation 4.5, every
vertex in Nv is incident to both zL and zR , hence no vertex of Nv belongs to Γ1S (S 0 ). It follows that
Γ1S (S 0 ) ∩ Ňv = (Γ1S (S 0 ) ∩ ŇvL ) ∪ (Γ1S (S 0 ) ∩ ŇvR ). By the induction hypothesis, we conclude that
|Γ1S (S 0 ) ∩ Ňv | = |Γ1S (S 0 ) ∩ ŇvL | + |Γ1S (S 0 ) ∩ ŇvR |
≤ 2 · (2j − 1) ≤ 2j+1 − 1 .
We henceforth assume that no leaf in the subtree of either vL or vR , without loss of generality vL ,
belongs to S 0 . Hence, by Observation 4.5 again, no vertex of ŇvL belongs to Γ(S 0 ) ⊇ Γ1S (S 0 ), which gives
Γ1S (S 0 ) ∩ Ňv = (Γ1S (S 0 ) ∩ Nv ) ∪ (Γ1S (S 0 ) ∩ ŇvR ). Obviously |(Γ1S (S 0 ) ∩ Nv )| ≤ |Nv | = 2j . By the induction
hypothesis, we obtain |Γ1S (S 0 ) ∩ Ňv | = |Γ1S (S 0 ) ∩ Nv | + |Γ1S (S 0 ) ∩ ŇvR | ≤ 2j + 2j − 1 = 2j+1 − 1. This
completes the proof of the induction.
Since Ňrt = N , applying the induction statement for the root rt of TS yields
|Γ1S (S 0 )| = |Γ1S (S 0 ) ∩ Ňrt | ≤ 2log s+1 − 1 ≤ 2s = (2/ log 2s) · |N |.
It follows that βw ≤ β(2/ log 2s), which completes the proof of the lemma.
4.3.2

The Core Graph with Arbitrary Expansion

Notice that the expansion of the graph provided by Lemma 4.4 is logarithmic in the size of its vertex set
and also in the maximum and average degree (both in S and in N ). In what follows we show how to
construct a generalized core graph that has an arbitrary expansion.
Lemma 4.6 For any integer ∆∗ ≥ 1 and any β ∗ satisfying (2e)/∆∗ ≤ β ∗ ≤ ∆∗ /(2e) (where e is the
base of the natural logarithm), there exists a bipartite graph G∗S = (S ∗ , N ∗ , ES∗ ) with sides S ∗ and N ∗ of
maximum degree ∆∗ , such that
11

1. |S ∗ | ≤ ∆∗ /2, |N ∗ | = β ∗ · |S ∗ |.
2. For every subset S 0 of S ∗ , |Γ(S 0 )| ≥ β ∗ · |S 0 |. (Thus, ordinary expansion is at least β ∗ .)
3. For every subset S 0 of S ∗ ,
|Γ1S ∗ (S 0 )| ≤ (4/ log(min{∆∗ /β ∗ , ∆∗ ·β ∗ }))·|N ∗ |. (Hence the wireless expansion, denoted βw , satisfies
βw ≤ β ∗ (4/ log(min{∆∗ /β ∗ , ∆∗ · β ∗ })).)
To prove Lemma 4.6, we first present the following two lemmas which generalize Lemma 4.4 to get an
arbitrary expansion.
Lemma 4.7 For any integer s ≥ 1 and any β > log 2s, there exists a bipartite graph ĜS = (S, N̂ , ÊS )
such that
1. s := |S| and |N̂ | = s · β.
2. Each vertex in S has degree (2s − 1) · (β/ log 2s).
3. The maximum degree ∆N̂ of a vertex in N̂ is s, and the average degree δN̂ of a vertex in N̂ is at
most 2s/ log 2s.
4. For every subset S 0 of S, |Γ(S 0 )| ≥ β · |S 0 |. (Hence the ordinary expansion is at least β.)
5. For every subset S 0 of S, |Γ1S (S 0 )| ≤ 2s·(β/ log 2s) = (2/ log 2s)·|N̂ |. (Hence the wireless expansion,
denoted βw , satisfies βw ≤ β(2/ log 2s).)
Proof: We assume for simplicity that k = β/ log 2s is an integer, and modify the construction used
to prove Lemma 4.4 by creating k copies v1 , . . . , vk for each vertex v in N . Thus each vertex set Nv
is “expanded” by a factor of k; denote the expanded vertex set by N̂v . The vertex set N̂ of ĜS is the
union of all
S copies of all vertices in N , or in other words, it is the union of all the expanded vertex sets,
i.e., N̂ = v∈TS N̂v . The edge set ÊS of ĜS is obtained by translating each edge (v, u) in the original
graph GS , where v ∈ N , into the k edges (v1 , u), . . . , (vk , u) in ĜS . Other than this modification, the
construction remains intact. Note that S remains unchanged, and the degree of vertices in N̂ is the same
as the degree of vertices in N in the original graph GS (both the maximum and average degree). On the
other hand, we now have |N̂ | = (s log 2s) · (β/ log 2s) = s · β. Moreover, the expansion increases from at
least log 2s to at least β, and the degree of vertices in S increases from 2s − 1 to (2s − 1) · (β/ log 2s).
Finally, note that for every subset S 0 of S, |Γ1S (S 0 )| increases by a factor of β/ log 2s, hence |Γ1S (S 0 )| is at
most 2s · (β/ log 2s) = (2/ log 2s) · |N̂ |, thus the wireless expansion βw satisfies βw ≤ β(2/ log 2s).
Lemma 4.8 For any integer s ≥ 1 and any β ≤ log 2s, there exists a bipartite graph ǦS = (Š, N, ĚS )
with sides Š and N , such that
1. |Š| = s · (log 2s/β) and |N | = s log 2s.
2. Each vertex in Š has degree 2s − 1.
3. The maximum degree ∆N of a vertex in N is s · (log 2s/β), and the average degree δN of a vertex
in N is at most 2s/β.
4. For every subset S 0 of Š, |Γ(S 0 )| ≥ β · |S 0 |. (Hence the ordinary expansion is at least β.)
5. For every subset S 0 of Š, |Γ1Š (S 0 )| ≤ 2s = (2/ log 2s) · |N |. (Hence the wireless expansion, denoted
βw , satisfies βw ≤ β(2/ log 2s).)

12

Proof: We assume for simplicity that k = log 2s/β is an integer, and modify the construction used to
prove Lemma 4.4 by creating k copies v1 , . . . , vk for each vertex v in S. The vertex set Š of ǦS is the union
of all copies of all vertices in S, and the edge set ĚS is obtained by translating each edge (v, u) in the
original graph GS , where v ∈ S, into the k edges (v1 , u), . . . , (vk , u) in ǦS . Other than this modification,
the construction remains intact. Note that N remains unchanged, and the degree of vertices in Š is the
same as the degree of vertices in S in the original graph GS (both the maximum and average degree).
On the other hand, we now have |Š| = s · (log 2s/β). Moreover, the expansion decreases from at least
log 2s to at least β, and the degree of vertices in N increases by a factor of log 2s/β. Finally, note that
for every subset S 0 of Š, |Γ1Š (S 0 )| remains at most 2s = (2/ log 2s) · |N |, thus the wireless expansion βw
remains unchanged, satisfying βw ≤ β(2/ log 2s).
We are now ready to complete to proof of Lemma 4.6.
Proof: [Lemma 4.6] Since β ∗ ≤ ∆∗ /(2e), we may write ∆∗ = 2s · (β ∗ / log 2s), for s ≥ e. Suppose first
that β ∗ > log 2s. In this case we take G∗S to be the graph provided by Lemma 4.7 for dse and β ∗ = β;
we assume for simplicity that s is an integer, but this assumption has a negligible effect. The maximum
degree in the graph is (2s − 1) · (β ∗ / log 2s), which is bounded by ∆∗ := 2s · (β ∗ / log 2s). This in particular
yields ∆∗ ≥ 2s, and so |S ∗ | = s ≤ ∆∗ /2. We also have |N ∗ | = β ∗ · |S ∗ |. The second assertion follows
immediately from Lemma 4.7(4). It remains to prove the third assertion. Lemma 4.7(5) implies that for
every subset S 0 of S ∗ , |Γ1S ∗ (S 0 )| ≤ 2s · (β ∗ / log 2s) = (2/ log 2s) · |N ∗ |. Observe that
min{∆∗ /β ∗ , ∆∗ · β ∗ } = ∆∗ /β ∗ = 2s/ log 2s ≤ 2s.
Hence 2/ log 2s ≤ 2/ log(min{∆∗ /β ∗ , ∆∗ · β ∗ }), which implies that
|Γ1S ∗ (S 0 )| ≤ (2/ log 2s) · |N ∗ |
≤ (2/ log(min{∆∗ /β ∗ , ∆∗ · β ∗ })) · |N ∗ | .
We henceforth assume that β ∗ ≤ log 2s. Since β ∗ ≥ (2e)/∆∗ , we may write ∆∗ = 2s0 · (log 2s0 /β ∗ ), for
s0 ≥ e/2. Next, we argue that β ∗ ≤ log 2s0 . Since β ∗ ≤ log 2s and as ∆∗ is equal to both 2s · (β ∗ / log 2s)
and 2s0 · (log 2s0 /β), it follows that
((2s0 )/(2s)) log(2s0 ) log(2s) = (β ∗ )2 ≤ log2 (2s).
Thus (2s0 ) · log(2s0 ) ≤ (2s) · log(2s), and so s0 ≤ s. Next, we prove that (2s0 )/ log(2s0 ) ≤ (2s)/ log(2s)
by taking logarithms for both hand sides and noting that the function f (x) = x − log x is monotone
increasing for x > log e and that s ≥ s0 ≥ e/2. Rearranging, we get
(β ∗ )2 = ((2s0 )/(2s)) log(2s0 ) log(2s) ≤ log2 (2s0 ), thus β ∗ ≤ log 2s0 .
In this case we take G∗S to be the graph provided by Lemma 4.8 for ds0 e and β ∗ = β; we again assume
for simplicity that s is an integer, but this assumption has a negligible effect. The maximum degree
in the graph is max{2s0 − 1, s0 · (log 2s0 /β)}, which is bounded by ∆∗ := 2s0 · (log 2s0 /β ∗ ). Note that
|S ∗ | = s0 · (log 2s0 /β ∗ ) = ∆∗ /2 and |N ∗ | = s0 log 2s0 = β ∗ · |S ∗ |. The second assertion follows immediately
from Lemma 4.8(4). It remains to prove the third assertion. Lemma 4.8(5) implies that for every subset
S 0 of S ∗ , |Γ1S ∗ (S 0 )| ≤ 2s0 = (2/ log 2s0 ) · |N ∗ |. Observe that
min{∆∗ /β ∗ , ∆∗ · β ∗ } ≤ ∆∗ · β ∗ = 2s0 · log 2s0 .
Hence
2/ log 2s0 = 4/ log((2s0 )2 ) ≤ 4/ log(2s0 · log 2s0 )
≤ 4/ log(min{∆∗ /β ∗ , ∆∗ · β ∗ }),
which implies that
|Γ1S ∗ (S 0 )| ≤ (2/ log 2s0 ) · |N ∗ |
≤ (4/ log(min{∆∗ /β ∗ , ∆∗ · β ∗ })) · |N ∗ |.

13

4.3.3

Worst-Case Expanders

Let G be an arbitrary (α, β)-expander on n vertices with maximum degree ∆, and let 0 <  < 1/2 be
a “blow-up” parameter. That is,  will determine the extent by which the parameters of interest blow
up due to the modification that we perform on the original graph G to obtain poor wireless expansion.
There is a tradeoff between the wireless expansion and the other parameters: The stronger our upper
bound on the wireless expansion is, the larger the blow-up in the other parameters becomes.
For technical reasons, we require that ∆ · β ≥ 1/(1 − 2 ). We start by constructing the generalized
core graph G∗S = (S ∗ , N ∗ , ES∗ ) provided by Lemma 4.6 for ∆∗ =  · ∆ and expansion β ∗ = β/, thus
yielding |S ∗ | ≤ ∆∗ /2 = (∆/2) and |N ∗ | = β ∗ · |S ∗ | = (β/) · |S ∗ |. Our worst-case expander G̃ is obtained
by plugging G∗S on top of G. The vertices of S ∗ are not part of the original vertex set of G, but are rather
new vertices added to it. The vertices of N ∗ are chosen arbitrarily from V (G).
Remark. If G is a bipartite expander, expanding from the left side L to the right side R, and if we want
G̃ to remain bipartite and to expand from L̃ to R̃, then L̃ will be defined as the union of L and S ∗ , and
R̃ will be defined as the union of R and a dummy vertex set of the same size as S ∗ , to guarantee that
|L̃| = |R̃|.
In what follows we analyze the properties of G̃. Denoting the number of vertices in G̃ by ñ, we have
˜ = (1 + ) · ∆, and note that the maximum
n ≤ ñ ≤ n + 2|S ∗ | ≤ n + 2(∆/2) ≤ (1 + ) · n. Write ∆
∗
˜
degree in G̃ is bounded by ∆ + ∆ ≤ ∆ +  · ∆ = ∆.
Claim 4.9 G̃ is an ordinary (α̃, β̃)-expander, where β̃ = (1 − ) · β, α̃ = (1 − ) · α.
Proof: Since ñ < (1 + ) · n and as α̃ = (1 − ) · α, it follows that α̃ · ñ ≤ (1 − )α · (1 + ) · n =
(1−2 )α·n < α·n. Consider an arbitrary set X of at most α̃· ñ ≤ α·n vertices from G̃. By Lemma 4.6(2),
the expansion in G∗S is at least β ∗ = β/, hence |Γ− (X ∩ S ∗ )| ≥ (β/) · |X ∩ S ∗ |. If |X ∩ S ∗ | ≥  · |X|,
then we have |Γ− (X)| ≥ |Γ− (X ∩ S ∗ )| ≥ (β/) · |X ∩ S ∗ | ≥ (β/) · ( · |X|) = β · |X| > β̃ · |X|.
Otherwise, |X \ S ∗ | ≥ (1 − ) · |X|, and as the expansion in G is at least β, we have |Γ− (X)| ≥ |Γ− (X \
S ∗ )| ≥ β · |X \ S ∗ | ≥ β · (1 − ) · |X| = β̃ · |X|.
˜ · β̃ = (1 + )∆ · (1 − )β ≥ 1. We also have
Recall that ∆ · β ≥ 1/(1 − 2 ), and note that ∆
˜
˜
˜ · β̃}) is non-negative, and the upper bound
that ∆/β̃ > ∆/β ≥ 1. Hence the term log(min{∆/β̃, ∆
˜ β̃, ∆
˜ · β̃}))) in the following claim is well-defined.
O(β̃/(3 · log(min{∆/
˜ β̃, ∆
˜ · β̃}))).
Claim 4.10 The wireless expansion β̃w of G̃ satisfies β̃w = O(β̃/(3 · log(min{∆/
Proof: Note that β̃w is trivially upper bounded by β, thus the claim holds vacuously whenever 3 ·
˜ β̃, ∆
˜ · β̃}) < 2. We may henceforth assume that 3 · log(min{∆/
˜ β̃, ∆
˜ · β̃}) ≥ 2, which implies
log(min{∆/
3
2/
˜
˜
that both ∆/β̃ and ∆ · β̃ are at least 2
. Since  < 1/2, it follows that
˜
˜ · β̃ ≥ 22/3 ≥ 2e
∆∗ · β ∗ = ∆ · β ≥ (∆/(1
+ )) · (β̃/(1 − )) ≥ ∆
and
˜
∆∗ /β ∗ = 2 (∆/β) ≥ 2 (∆/(1
+ ))/(β̃/(1 − ))
2
˜
=  ((1 − )/(1 + )) · (∆/β̃)
≥ 2 ((1 − )/(1 + )) · 22/

3

≥ 2e.

In particular, we have (2e)/∆∗ ≤ β ∗ ≤ ∆∗ /(2e), as required in Lemma 4.6. Since all edges adjacent to
the vertices of S ∗ belong to the core graph G∗S with parameters ∆∗ and β ∗ , Lemma 4.6(3) implies that
for every subset S 0 of S ∗ ,
|Γ1S ∗ (S 0 )| ≤ (4/ log(min{∆∗ /β ∗ , ∆∗ · β ∗ })) · |N ∗ |
14

˜ β̃, ∆
˜ · β̃}))) · |N ∗ |.
≤ (4(1 + )/(2 (1 − ) · log(min{∆/
˜ β̃, ∆
˜ · β̃}))) · |N ∗ |.
≤ (12/(2 · log(min{∆/
˜ β̃, ∆
˜ · β̃}))) · β · |S ∗ |.
= (12/(3 · log(min{∆/
˜ β̃, ∆
˜ · β̃}))) · β̃ · |S ∗ |.
≤ (24/(3 · log(min{∆/
(It is easily verified that the third and last inequalities hold for  < 1/2.) The bottom-line constant 24
can be improved; we did not try to optimize it.
We derive the following corollary, which implies the existence of expanders with worst possible wireless
expansion. The bound on the wireless expansion is tight in the entire range of parameters, disregarding
constants and dependencies on .
Corollary 4.11 For any n, ∆, β and 0 <  < 1/2 such that ∆ · β ≥ 1/(1 − 2 ), if there exists an ordinary
(α, β)-expander G on n vertices with maximum degree ∆, then there exists an (α̃, β̃)-expander G̃ on
˜ and wireless expansion β̃w , where: (1) ∆ ≤ ∆
˜ ≤ (1 + ) · ∆; (2)
ñ vertices with maximum degree ∆
3
˜ β̃, ∆
˜ · β̃}))).
n ≤ ñ ≤ (1 + ) · n; (3) β̃ = (1 − ) · β; (4) α̃ = (1 − ) · α; and (5) β̃w = O(β̃/( · log(min{∆/
One may use Corollary 4.11 in conjunction with known constructions of explicit expanders (such as
Ramanujan graphs), which achieve near-optimal expansion for any degree parameter. Taking  to be a
sufficiently small constant thus completes the proof of Theorem 1.2.

5

A tight lower bound on the broadcast time in radio networks

In this section we provide a simple proof for obtaining a tight lower bound of Ω(D log(n/D)) on the
broadcast time in radio networks, which holds both in expectation and with high probability.
Consider our core bipartite graph GS = (S, N, ES ) from Lemma 4.4, with sides S and N , where
s = |S| and |N | = s log 2s. Suppose that we connect an additional vertex rt to all vertices of S and
initiate a (radio) broadcast at rt in the resulting graph. By Lemma 4.4(5), one cannot uniquely cover
more than 2s vertices (i.e., a (2/(log 2s))-fraction) of N using any subset S 0 ⊆ S. It follows that at any
round after the first, the broadcast may reach at most 2s new vertices of N , which yields the following
corollary.
Corollary 5.1 The number of rounds needed for the broadcast to reach a (2i/(log 2s))-fraction of N is
at least 1 + i, for any 0 ≤ i ≤ ((log 2s)/2).
Next, we construct a graph G of diameter Θ(D), for an arbitrary parameter D = Ω(log n), in which
the number of rounds needed to complete a broadcast is Ω(D log(n/D)).
The core graph GS has |S| + |N | = s(1 + log 2s) = s(log 4s) vertices. We take D/2 copies of this
D/2
graph, denoted by G1S , G2S , . . . , GS , each containing roughly n/D vertices. Thus we take s so that
n/D ≈ s(log 4s), and so log s = Θ(log(n/D)). Denote the sides of GiS by S i and N i . We connect the root
rt = rt0 to all vertices of S 1 , and for each 1 ≤ i ≤ D/2, we randomly sample a vertex from N i , denoted
by rti , and connect it (unless i = D/2) to all vertices of S i+1 . This completes the construction of the
graph G. It is easy to verify that the diameter of G is Θ(D), and to be more accurate, the diameter is
D + 2. In what follows we assume that none of the processors associated with the vertices of the graph
initially have any topological information on the graph (except for its size and diameter). This rather
standard assumption was also required in the proof of Kushilevitz and Mansour [11].
Consider a broadcast initiated at rt. We make the following immediate observation.
Observation 5.2 The message must reach rti−1 before reaching rti , for 1 ≤ i ≤ D/2.
Denote by Ri the random variable for the number of rounds needed for the message to be sent from rti−1
to rti , for each i, and let R be the random variable for the number of rounds needed to send the message
from rt to rtD/2 . We thus have R = R1 + R2 + . . . + RD/2 .
15

By Corollary 5.1, the number of rounds needed for the broadcast message to reach half of the vertices
of N 1 (from rt = rt0 ) is at least ((log 2s)/4) + 1 = Θ(log(n/D)). Since rt1 was sampled randomly
from all vertices N 1 and as none of the processors have any topological information on the graph, rt1
received this message within this many rounds with probability at most 1/2, hence R1 = Ω(log(n/D))
with constant probability. By Observation 5.2, the only way for the message to reach any vertex of
S 2 , and later rt2 , is via rt1 , hence we can repeat this argument, and carry it out inductively. Since
the D/2 variables R1 , R2 , . . . , RD/2 are independently and identically distributed, and as D = Ω(log n)
(where the constant hiding in the Ω-notation is sufficiently large), a Chernoff bound implies that IP(R =
Ω(D log(n/D))) ≥ 1 − n−c , where c is a constant as big as needed. For the expectation bound, note
that IE (() Ri ) > (log 2s)/4 = Ω(log(n/D)) by Corollary 5.1, for each i, and by linearity of expectation
we obtain IE (() R) = IE (() R1 ) + IE (() R2 ) + . . . + IE (() RD/2 ) = Ω(D log(n/D)). (The assumption that
D = Ω(log n) is used for deriving the high probability bound but not the expectation bound.)
Acknowledgments.
We are grateful to Mohsen Ghaffari for the useful discussions on the probabilistic arguments of Section
4.2.

References
[1] N. Alon, A. Bar-Noy, N. Linial, and D. Peleg. A lower bound for radio broadcast. J. Comput. Syst. Sci.,
43(2):290–298, 1991.
[2] N. Alon and M. R. Capalbo. Explicit unique-neighbor expanders. In Proc. 43rd FOCS, pages 73–82, 2002.
[3] N. Alon, M. Ghaffari, B. Haeupler, and M. Khabbazian. Broadcast throughput in radio networks: routing
vs. network coding. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms,
pages 1831–1843. SIAM, 2014.
[4] N. Alon and J. Spencer. The Probabilistic Method. John Wiley, 1992.
[5] R. Bar-Yehuda, O. Goldreich, and A. Itai. On the time-complexity of broadcast in radio networks: An
exponential gap between determinism and randomization. In Proceedings of the Sixth Annual ACM Symposium
on Principles of Distributed Computing, Vancouver, British Columbia, Canada, August 10-12, 1987, pages
98–108, 1987.
[6] O. Becker. Symmetric unique neighbor expanders and good LDPC codes. Discrete Applied Mathematics,
211:211–216, 2016.
[7] I. Chlamtac. The wave expansion approach to broadcasting in multihop radio networks. IEEE Transactions
on Communications, 39(3):426–433, 1991.
[8] I. Chlamtac and S. Kutten. On broadcasting in radio networks–problem analysis and protocol design. IEEE
Transactions on Communications, 33(12):1240–1246, 1985.
[9] A. Czumaj and W. Rytter. Broadcasting algorithms in radio networks with unknown topology. J. Algorithms,
60(2):115–143, 2006.
[10] S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American
Mathematical Society, 43(4):439–561, 2006.
[11] E. Kushilevitz and Y. Mansour. An ω(d\log(n/d)) lower bound for broadcast in radio networks. SIAM journal
on Computing, 27(3):702–712, 1998.
[12] C. C. Newport. Radio network lower bounds made easy. In Distributed Computing - 28th International
Symposium, DISC 2014, Austin, TX, USA, October 12-15, 2014. Proceedings, pages 258–272, 2014.

16

Appendix
A

Deterministic and Constructive Analysis with Improved Bounds

A.1
A.1.1

Bounds depending on the maximum degree
A naive approach

In this section we provide a simple argument showing that when the maximum degree is small, the wireless
expansion βw is not much smaller than the ordinary expansion β. Recall that we consider an arbitrary
bipartite graph GS = (S, N, ES ) with sides S and N , such that |N | = β · |S|. We assume that no vertex
of GS is isolated, i.e., all vertex degrees are at least 1. In what follows we define s = |S|, γ = |N |.
Lemma A.1 In GS = (S, N, ES ), if the maximum degree is ∆, then there is a subset S 0 of S with
|Γ1S (S 0 )| ≥ γ/∆.
Proof: We describe a procedure for computing vertex sets Suni ⊆ S and Nuni ⊆ N , such that |Nuni | ≥ γ/∆
and every vertex of Nuni has a unique neighbor in Suni .
Initialize Nuni = Suni = ∅, Ntmp = N, Stmp = S. At each step of the procedure, the sets Nuni and
Suni (respectively, Ntmp and Stmp ) grow (resp., shrink). The procedure maintains the following invariant
throughout.
Invariant:
(I1) Stmp ∪ Suni ⊆ S and Stmp ∩ Suni = ∅.
(I2) Ntmp ∪ Nuni ⊆ N and Ntmp ∩ Nuni = ∅.
(I3) Every vertex of Nuni has a unique neighbor in Suni .
(I4) Every vertex of Ntmp has at least one neighbor in Stmp , but has no neighbor in Suni .
For a vertex x ∈ Ntmp , recall that Γ(x, Stmp ) is the set of neighbors of x in Stmp . At each step we
pick a vertex v ∈ Ntmp minimizing |Γ(v, Stmp )|, i.e., a vertex with a minimum number of neighbors in
Stmp . (By invariant (I4), we have |Γ(v, Stmp )| ≥ 1.) Let Qv be the set of all vertices in Ntmp that
are incident on at least one vertex of Γ(v, Stmp ). By the choice of v, for any vertex u in Qv satisfying
Γ(u, Stmp ) ⊆ Γ(v, Stmp ), we must have Γ(u, Stmp ) = Γ(v, Stmp ). We partition Qv into two subsets Q0v and
Q00v , where Q0v contains all vertices u for which Γ(u, Stmp ) = Γ(v, Stmp ) and Q00v contains the remaining
vertices of Qv (all of which must have a neighbor in Stmp \ Γ(v, Stmp )). Obviously we have Q0v ⊇ {v}, so
|Q0v | ≥ 1.
We start by moving an arbitrary vertex w of Γ(v, Stmp ) from Stmp to Suni ; note that w is incident
on all vertices of Q0v . Then we remove all other vertices of Γ(v, Stmp ) from Stmp , which prevents these
vertices from entering Suni later on, thus guaranteeing that all vertices in Q0v will have w as their unique
neighbor in Suni . Subsequently, all vertices of Q0v are moved from Ntmp to Nuni . (See Figure 3 for an
illustration.)
In addition, to prevent violating invariant (I4) now and invariant (I3) in the future, all neighbors of w
that belong to Q00v are removed from Ntmp (they are incident to w which has just moved to Suni , and they
might have neighbors in Stmp that will be moved to Suni later on). It is clear that the first three invariants
(I1) − (I3) continue to hold following this step. As for invariant (I4), consider an arbitrary vertex u of
Ntmp at the beginning of this step. We know that u had no neighbors in Suni at the beginning of the
step. If u is not a neighbor of w, then u had no neighbors in Suni also at the end of the step. Otherwise,
If u is a neighbor of w, then its only new neighbor in Suni at the end of the step is w and u was removed
from Ntmp (it either moves to Nuni if it belongs to Q0v , or it is removed altogether if it belongs to Q00v ).
This shows that every vertex u of Ntmp has no neighbor in Suni at the end of the step. Next, if u has a
neighbor outside Γ(v, Stmp ), then this neighbor remains in Stmp following the step (since only the vertices
i

Figure 3: An illustration of a single step of the procedure. The dashed lines represent edges that connect
vertices in Qv with vertices in Stmp , where v is a vertex in Ntmp minimizing |Γ(v, Stmp )|. The vertices in
Q0v are colored black, and they move from Ntmp to Nuni ; the vertices in Q00v are colored green, and they are
removed from Ntmp ; the vertices in Γ(v, Stmp ) are colored red, and they are removed from Stmp , except for w
which moves to Suni .
of Γ(v, Stmp ) are removed from Stmp during the step). Otherwise, we have Γ(u, Stmp ) ⊆ Γ(v, Stmp ), which
by the choice of v implies that Γ(u, Stmp ) = Γ(v, Stmp ). By definition, u ∈ Q0v , and is thus removed from
Ntmp during the step. This shows that at the end of this step, every vertex of Ntmp has at least one
neighbor in Stmp , so (I4) holds.
This procedure terminates once Ntmp = ∅. By invariant (I3), every vertex of Nuni has a unique
neighbor in Suni . At each step of the procedure, we move |Q0v | ≥ 1 vertices from Ntmp to Nuni , all of which
are neighbors of some vertex w ∈ Γ(v, Stmp ), and remove some of the other (at most ∆ − 1) neighbors of
w from Ntmp . Consequently, at least one vertex among every ∆ vertices removed from Ntmp must move
to Nuni . Since initially we have Ntmp = N , it follows that |Nuni | ≥ γ/∆.
Note that the proof of this lemma takes into account the maximum degree ∆S of a vertex in S, rather
than the maximum degree ∆ in the entire graph.
Corollary A.2 Suppose G is an (α, β)-expander with maximum degree ∆. Then it is also an (αw , βw )wireless expander, with αw = α and βw ≥ β/∆.
A.1.2

Procedure Partition

Our next goal is to strengthen Corollary A.2. In this section we describe a procedure, hereafter named
Procedure Partition, which lies at the core of our lower bounds on the wireless expansion. This procedure
is then employed in various scenarios to conclude that the wireless expansion is close to the ordinary
expansion. The procedure partitions N into Nuni , Nmany , Ntmp and S into Suni and Stmp , such that the
following conditions hold. (In what follows we refer to these conditions as the “partition conditions”.)
(P1) Every vertex of Nuni has a unique neighbor in Suni .
(P2) Every vertex of Ntmp has at least one neighbor in Stmp , but has no neighbor in Suni .
(P3) |Nuni | ≥ |Nmany |.
(P4) Either Ntmp = ∅, or |Etmp | ≤ 2|Euni | holds, where Euni (resp., Etmp ) denotes the set of edges
connecting all vertices in Stmp with vertices in Nuni (resp., Ntmp ).
ii

At the outset, we initialize Nuni = Nmany = Suni = ∅, Ntmp = N, Stmp = S. At each step of the
procedure, the sets Nuni and Suni grow and the set Ntmp and Stmp shrink. The set Nmany also grows, but
not necessarily at each step; it contains “junk” vertices that once belonged to Nuni , but were removed
from Nuni due to new vertices added to Suni .
The first three aforementioned conditions are maintained throughout the execution of the procedure.
(Notice that initially all three of them hold trivially.) On the other hand, condition (P 4) is required to
hold only when the procedure terminates.
For a vertex x ∈ Stmp , denote by Ntmp (x) (resp., Nuni (x)) the set of neighbors of x in Ntmp (resp.,
Nuni ).
At each step we pick a vertex v ∈ Stmp maximizing gain(v) := |Ntmp (v)| − 2|Nuni (v)|. Assuming
gain(v) > 0, we move v from Stmp to Suni ; to preserve condition (P 1), we move the vertices of Nuni (v)
from Nuni to Nmany . Next, we move all vertices of Ntmp (v) from Ntmp to Nuni . Since gain(v) > 0,
condition (P 3) holds. The reason condition (P 2) holds is because once a vertex of Stmp moves to Suni ,
all its neighbors in Ntmp are moved to Nuni . Obviously the sets Nuni , Nmany , Ntmp (resp., Suni , Stmp ) form
a partition of N (resp., S).
Procedure Partition terminates once Stmp becomes empty or once gain(v) ≤ 0 for all v ∈ Stmp . In
the former case, condition (P 2) implies that Ntmp = ∅, and we are done. In the latter case, we have
|Ntmp (v)| ≤ 2|Nuni (v)| for any v ∈ Stmp , yielding
X
X
|Etmp | =
|Ntmp (v)| ≤
2|Nuni (v)| = 2|Euni |.
(1)
v∈Stmp

v∈Stmp

(See Figure 4 for an illustration.)

Figure 4: An illustration of the edge sets Euni and Etmp which connect Stmp to Nuni and Ntmp , respectively.
The vertices in Ntmp (v) and Nuni (v), as well as the edges connecting them to v, are colored red; here we have
gain(v) = |Ntmp (v)| − 2|Nuni (v)| = −2.

A.1.3

Constructive lower bound for βw in terms of the average degree

P
Let N = Γ− (S) and γ = |N |, and denote by δ the average degree of a vertex in N , i.e., δ = (1/γ) v∈N deg(v, S).
(As all vertex degrees are at least 1, we have δ ≥ 1.)
We next show a lower bound that takes into account the average degree δ rather than the maximum
degree ∆.
Lemma A.3 In the graph GS there exists a subset S 0 of S with |Γ1S (S 0 )| ≥ γ/(8δ).
iii

Proof: Denote by N 2δ the set of vertices of N = Γ− (S) with degree at most 2δ. Observe that at least
half the vertices of N have degree at most twice the average, implying that |N 2δ | ≥ γ/2. We apply
Procedure Partition, but consider the vertex set N 2δ rather than N . Thus we obtain a partition of
2δ , N 2δ , N 2δ and a partition of S into S
N 2δ rather than N into Nuni
uni and Stmp satisfying the partition
many
tmp
2δ
conditions (P 1) − (P 4). Next, we show that |Nuni | ≥ γ/(8δ).
2δ = ∅. By partition condition (P 3), 2|N 2δ | ≥
Suppose first that the procedure terminates because Ntmp
uni
2δ | + |N 2δ | = |N 2δ |. It follows that
|Nuni
many
2δ
|Nuni
| ≥

|N 2δ |
γ
γ
≥
≥
.
2
4
4δ

(2)

We henceforth assume that |Etmp | ≤ 2|Euni |. By definition, each vertex in N 2δ has at most 2δ neighbors
2δ has a single neighbor in S , so it has at most
in S. Condition (P 1) implies that each vertex in Nuni
uni
2δ |. By condition (P 2), each vertex of N 2δ is
2δ − 1 neighbors in Stmp , yielding |Euni | ≤ (2δ − 1)|Nuni
tmp
2δ |. It follows that
incident on at least one edge of Etmp , and so |Etmp | ≥ |Ntmp
2δ
2δ
|Ntmp
| ≤ |Etmp | ≤ 2|Euni | ≤ (4δ − 2)|Nuni
|.

Hence,
2δ
2δ
4δ · |Nuni
| = (2 + (4δ − 2))|Nuni
|
2δ
2δ
2δ
≥ |Nuni
| + |Nmany
| + |Ntmp
|
γ
= |N 2δ | ≥ ,
2
2δ | ≥ γ/(8δ).
which yields |Nuni

For every S ⊂ V denote by δS the average degree of a vertex in N = Γ− (S), i.e., δS = (1/|N |)
and denote δ̄ = max{δS | S ⊂ V, |S| ≤ αn}.

P

v∈N

deg(v, S)

Corollary A.4 Let G = (V, E) be an (α, β)-expander. Then
(1) G is an (αw , βw )-wireless expander with αw = α and βw ≥ β/(8δ̄) ≥ β/(8∆), where ∆ is the maximum
degree in the graph.
(2) In the regime β ≥ 1, we have δS ≤ ∆/β, for every S such that |S| ≤ αn, thus δ̄ ≤ ∆/β and we get
βw ≥ β 2 /(8∆).
A.1.4

“Convenient” degree constraints

The following lemmas show that if many vertices in Γ− (S) have roughly the same degree, then the
ordinary expansion β and the wireless expansion βw of GS are roughly the same.
Lemma A.5 In GS , for any c > 1 and any i ∈ {1, 2, . . . , logc |S|}, there is a subset S 0 of S with
|Γ1S (S 0 )| ≥ |N (i) |/2(1 + c), where N (i) denotes the set of vertices in N with degree in [ci−1 , ci ) for i <
logc |S| and for i = logc |S| is the set of vertices in N with degree in [ci−1 , ci ] = [|S|/c, |S|].
Corollary A.6 In GS , for any c > 1 there is a subset S 0 of S such that
|Γ1S (S 0 )| ≥

log2 c
·γ .
2(1 + c) log2 ∆

Proof: The previous lemma implies also that for every c > 1 and every i ∈ {1, 2, . . . , logc ∆} (rather then
logc |S|), there is a subset S 0 of S with |Γ1S (S 0 )| ≥ |N (i) |/2(1 + c), where N (i) denotes the set of vertices
in N with degree in [ci−1 , ci ) for i < logc ∆ and for i = logc ∆ is the set of vertices in N with degree in
iv

[ci−1 , ci ] = [∆/c, ∆]. Observe that there exists an index j ∈ {1, 2, . . . , logc ∆} s.t. |N (j) | ≥ γ/ logc ∆, for
this index j, we get |Γ1S (S 0 )| ≥ |N (j) |/2(1 + c) ≥ 2(1+c)γlog ∆ .
c

The maximum of f (c) = log2 c/(2(1 + c)) is attained at c ≈ 3.59112 and equals ≈ 0.20087, hence we
get the following.
Corollary A.7 Let G = (V, E) be an (α, β)-expander with maximum degree ∆. Then it is also an
(αw , βw )-wireless expander with αw ≥ α and βw ≥ 0.20087
log ∆ · β.
2

A.2

Bounds depending on the average degree

Recall that δ denotes the average degree of a vertex in N = Γ− (S). In case δ is known, we can state a
stronger bound than that of Corollary A.7, using δ in place of ∆.
Corollary A.8 In GS , for any c > 1 and t > 1 there is a subset S 0 of S such that


1
1
· γ.
|Γ1S (S 0 )| ≥ 1 −
t 2(1 + c) logc (tδ)
Corollary A.9 In GS , for every  > 0, and for sufficiently large1 δ, there is a subset S 0 of S such that
2.0087
|Γ1S (S 0 )| ≥ (1+)
log (δ) · γ.
2

Corollary A.10 Let G = (V, E) be an (α, β)-expander with maximum degree ∆ and let  > 0. Suppose
that for every S, δS is large2 enough. Then G is also an (αw , βw )-wireless expander with αw ≥ α and
βw ≥

2.0087
·β .
(1 + ) log2 (δ̄)

Proof: Given S ⊂ V with |S| ≤ α|V |, write γ = |Γ− (S)| and let GS = (S, Γ− (S), e(S, Γ− (S)). Note
that as G is an (α, β)-expander, γ ≥ β|S| and by Corollary A.9, there is a subset S 0 of S with
|Γ1S (S 0 )| ≥
≥
Hence βw ≥

2.0087
(1+) log2 (δ̄)

2.0087
·γ
(1 + ) log2 (δS )
2.0087
2.0087
· β|S| ≥
· β|S| .
(1 + ) log2 (δS )
(1 + ) log2 (δ̄)

· β.

Lemma A.11 Suppose there exists c > 1 and t > 1 such that for every subset N 0 of N in GS of
sufficiently large size (say, of size at least (γ/2)(1 − 1/t)), the average degree δ 0 of a vertex in N 0 is at
least tδ/c. Then there is a subset S 0 of S such that


γ
1
1
0
1−
.
|ΓS (S )| ≥
2(1 + c)
t
Proof: We apply Procedure Partition, but consider the vertex set N tδ of vertices in N = Γ− (S)
tδ , N tδ , N tδ and a
with degree at most tδ. Thus we obtain a partition of N tδ rather than N into Nuni
many
tmp
partition of S into Suni and Stmp satisfying the partition conditions (P 1) − (P 4). Next, we show that
tδ | ≥ |N tδ |/2(1 + c). This complete the proof as |N tδ | ≥ γ(1 − 1/t).
|Nuni
tδ | < (γ/2)(1 − 1/t), as |N tδ | ≥ γ(1 − 1/t) and by using partition condition (P 3) we get
If |Ntmp
tδ | ≥ |N tδ | + |N tδ | ≥ (γ/2)(1 − 1/t), hence |N tδ | ≥ (γ/4)(1 − 1/t) ≥ (γ/(2(1 + c)))(1 − 1/t).
2|Nuni
many
uni
uni
1
2

δ that that satisfies  ln(δ) − ln(ln δ) − ln(1 + ) − 1 ≥ 0 is enough.
i.e., satisfies  ln(δS ) − ln(ln δS ) − ln(1 + ) − 1 ≥ 0.

v

tδ | ≥ (γ/2)(1 − 1/t), in particular nonempty and it must hold that |E
Otherwise, if |Ntmp
tmp | ≤ 2|Euni |. By
definition, each vertex in N tδ has at most tδ neighbors in S. Condition (P 1) implies that each vertex in
tδ has a single neighbor in S , so it has at most tδ−1 neighbors in S
tδ
Nuni
tmp , yielding |Euni | ≤ (tδ−1)|Nuni |.
uni
tδ
tδ
By condition (P 2), each vertex of Ntmp is incident only on edges of Etmp . Since |Ntmp | ≥ (γ/2)(1 − 1/t),
tδ |. It follows that
the average degree in this set is at least tδ/c. Therefore, |Etmp | ≥ (tδ/c)|Ntmp

tδ 2δ
tδ
|N | ≤ |Etmp | ≤ 2|Euni | ≤ 2(tδ − 1)|Nuni
|.
c tmp
Hence

2




tδ
tδ
tδ
tδ
+ tδ |Nuni
| ≥
2·
+ 2(tδ − 1) |Nuni
|
c
c
tδ
tδ
tδ
tδ
≥
· (|Nuni
| + |Nmany
| + |Ntmp
|)
c
tδ tδ
=
|N |,
c

which yields
tδ
|Nuni
| ≥

|N tδ |
.
2(1 + c)

Corollary A.12 Let G = (V, E) be an (α, β)-expander and suppose there exists c > 1 and t > 1 such
that for every subset S of V of size |S| ≤ αn and for every subset M of Γ− (S) of sufficiently large size
(say, of size at least (|Γ− (S)|/2)(1 − 1/t)), the average degree δ 0 of a vertex in M is at least (tδS )/c. Then
G is also an (αw , βw )-wireless expander with αw ≥ α and


β
1
βw ≥
1−
.
4(1 + c)
t
Proof: The proof follows similar lines as those in the proof of Corollary A.10.
A.2.1

Near-optimal bounds

Lemma A.13 In GS there is a subset S 0 of S with |Γ1S (S 0 )| ≥ γ/(9 log(2δ)).
Proof: We prove the existence of vertex sets Suni ⊆ S and Nuni ⊆ N = Γ− (S), such that |Nuni | ≥
γ/(9 log(2δ)) and every vertex of Nuni has a unique neighbor in Suni . The proof is by induction on γ, for
all values of δ ≥ 1. (Since δ ≥ 1, we have log(2δ) ≥ 1.)
Basis: γ ≤ 9. Let v be an arbitrary vertex of S with at least one neighbor in N , let Suni = {v}, and let
Nuni be the (non-empty) neighborhood of v. We thus have |Nuni | ≥ 1 ≥ γ/(9 log(2δ)).
Induction step: Assume the correctness of the statement for all smaller values of γ, and prove it for γ.
We apply Procedure Partition (with the bipartite graph induced by the sets S and N ). If the procedure
terminates because Ntmp = ∅, then we have |Nuni | ≥ |N |/2 (cf. Equation (2)).
We henceforth assume that Ntmp 6= ∅, i.e., γ 0 = |Ntmp | ≥ 1. In particular, it must hold that |Etmp | ≤
2|Euni |. Denote by δ 0 the average degree of a vertex in Ntmp , counting only neighbors that belong to
Stmp . By partition condition (P 2), the entire neighborhood of Ntmp is contained in Stmp ; confusing as it
might be, we do not make use of this property here. We do use, however, another property guaranteed by
partition condition (P 2): Each vertex of Ntmp has at least one neighbor in Stmp , which implies that δ 0 ≥ 1,
thus log(2δ 0 ) ≥ 1. Since Ntmp is non-empty, it must hold that |Etmp | ≥ 1. Hence |Euni | ≥ |Etmp |/2 ≥ 1/2,
yielding |Euni | ≥ 1. Consequently, we have |Nuni | ≥ 1, which in turn yields 1 ≤ γ 0 ≤ γ − 1.

vi

Suppose first that γ 0 / log(2δ 0 ) ≥ γ/ log(2δ). By the induction hypothesis for γ 0 (restricting ourselves
to the subgraph of GS induced by the vertex sets Stmp and Ntmp ), we conclude that there is a subset S̃
of Stmp with |Γ1Stmp (S̃) ∩ Ntmp | ≥ γ 0 /(9 log(2δ 0 )), yielding
|Γ1S (S̃)| ≥ |Γ1Stmp (S̃) ∩ Ntmp | ≥
We may henceforth assume that

γ0
γ
≥
.
0
9 log(2δ )
9 log(2δ)

γ0
γ
<
.
0
log(2δ )
log(2δ)

(3)

Observe that |Euni | + |Etmp | ≤ |ES | = δ · γ. By definition, |Etmp | = δ 0 · γ 0 . It follows that
3δ 0 · γ 0 = 3|Etmp | ≤ 2(|Euni | + |Etmp |) ≤ 2δ · γ,
yielding
0

log(2δ ) ≤ log(2δ) + log

γ 
3


− log

γ0
2


.

(4)

Plugging Equation (4) into Equation (3), we obtain

 0 
γ 
γ
γ
0
γ <
log(2δ) + log
− log
.
log(2δ)
3
2

(5)

We may assume that |Nuni | < γ/9, as otherwise |Nuni | ≥ γ/9 ≥ γ/(9 log(2δ)) and we are done. By
partition condition (P 3), |Nuni | ≥ |Nmany |. Hence γ = |Nuni | + |Nmany | + γ 0 ≤ 2|Nuni | + γ 0 , yielding
(γ − γ 0 )/2 ≤ |Nuni | < γ/9. Hence 2/3(γ/γ 0 ) ≤ 6/7, which gives
 0
 
γ 
γ
6
2
log
− log
≤ log
≤ − .
3
2
7
9
It follows that

 0 
γ 
γ
γ
log(2δ) + log
− log
log(2δ)
3
2
γ
≤
log(2δ)



2
log(2δ) −
. (6)
9

Plugging Equation (6) into Equation (5) gives


2
2γ
γ
0
γ ≤
log(2δ) −
= γ−
log(2δ)
9
9 log(2δ)
2γ
≤ 2|Nuni | + γ 0 −
,
9 log(2δ)
implying that |Nuni | ≥ γ/(9 log(2δ)).
Corollary A.14 Let G = (V, E) be an (α, β)-expander. Then,
(1) G is an (αw , βw )-wireless expander with αw = α and βw ≥ β/(9 log(2δ̄)) ≥ β/(9 log(2∆)), where ∆
is the maximum degree in the graph.
(2) In the regime β ≥ 1, we have δS ≤ ∆/β, thus δ̄ ≤ ∆/β, and hence βw ≥ β/(9 log(2∆/β)).
Corollary A.15 In GS there is a subset S 0 of S with


γ
γ
1
0
,
|ΓS (S )| ≥ min
.
9 log δ 20
vii

Proof: We prove that if δ < 2 then there is a subset S 0 of S with |Γ1S (S 0 )| ≥ γ/20 and if δ ≥ 2 then
there is a subset S 0 of S with |Γ1S (S 0 )| ≥ γ/(9 log δ). The proof is by induction on γ.
Basis: γ ≤ 9. If δ < 2, by Lemma A.13 there is a subset S 0 of S with |Γ1S (S 0 )| ≥ γ/(9 log(2δ)) > γ/18 ≥
γ/20. For δ ≥ 2, let v be an arbitrary vertex of S with at least one neighbor in N , let S 0 = {v}, then
|Γ(v)| = |Γ1S (S 0 )| ≥ 1 ≥ γ/(9 log δ).
Induction step: Assume the correctness of the statement for all smaller values of γ, and prove it for γ.
If δ < 2, then the same proof holds as in the basis case. Let assume δ ≥ 2 and therefore log δ ≥ 1. We
apply Procedure Partition (with the bipartite graph induced by the sets S and N ). If the procedure
terminates because Ntmp = ∅, then we have |Nuni | ≥ |N |/2 (cf. Equation (2)).
We henceforth assume that Ntmp 6= ∅, i.e., γ 0 = |Ntmp | ≥ 1. In particular, it must hold that |Etmp | ≤
2|Euni |. Denote by δ 0 the average degree of a vertex in Ntmp , counting only neighbors that belong
to Stmp . By partition condition (P 2) each vertex of Ntmp has at least one neighbor in Stmp , which
implies that δ 0 ≥ 1, thus log(2δ 0 ) ≥ 1. Since Ntmp is non-empty, it must hold that |Etmp | ≥ 1. Hence
|Euni | ≥ |Etmp |/2 ≥ 1/2, yielding |Euni | ≥ 1. Consequently, we have |Nuni | ≥ 1, which in turn yields
1 ≤ γ 0 ≤ γ − 1.
There are two cases. The first case is when δ 0 < 2. By Lemma A.13, there is a subset S 0 of S s.t.
|Γ1S (S 0 )| ≥ |Γ1Stmp (S 0 ) ∩ Ntmp | ≥

γ0
γ0
≥
.
9 log(2δ 0 )
18

(7)

If γ 0 < γ(9/10), then as γ = |Nuni | + |Nmany | + γ 0 ≤ 2|Nuni | + γ 0 , we get |Nuni | ≥ γ/20. So we can assume
γ 0 ≥ γ(9/10), and by Equation (7),
γ0
γ
|Γ1S (S 0 )| ≥
≥ .
18
20
The second case is when δ 0 ≥ 2 and therefore log δ ≥ 1.
Suppose first that γ 0 / log δ 0 ≥ γ/ log δ. By the induction hypothesis for γ 0 (restricting ourselves to the
subgraph of GS induced by the vertex sets Stmp and Ntmp ), we conclude that there is a subset S̃ of Stmp
with |Γ1Stmp (S̃) ∩ Ntmp | ≥ γ 0 /(9 log δ 0 ), yielding
γ
γ0
≥
.
9 log δ 0
9 log δ

|Γ1S (S̃)| ≥ |Γ1Stmp (S̃) ∩ Ntmp | ≥
We may henceforth assume that

γ
γ0
<
.
0
log δ
log δ

(8)

Observe that |Euni | + |Etmp | ≤ |ES | = δ · γ. By definition, |Etmp | = δ 0 · γ 0 . It follows that
3δ 0 · γ 0 = 3|Etmp | ≤ 2(|Euni | + |Etmp |) ≤ 2δ · γ,
yielding
0

log δ ≤ log δ + log

γ 
3


− log

γ0
2


.

Plugging Equation (9) into Equation (8), we obtain

 0 
γ 
γ
γ
γ0 <
log δ + log
.
− log
log δ
3
2

(9)

(10)

We may assume that |Nuni | < γ/9, as otherwise |Nuni | ≥ γ/9 ≥ γ/(9 log δ) and we are done. By
partition condition (P 3), |Nuni | ≥ |Nmany |. Hence γ = |Nuni | + |Nmany | + γ 0 ≤ 2|Nuni | + γ 0 , yielding
(γ − γ 0 )/2 ≤ |Nuni | < γ/9. Hence 2/3(γ/γ 0 ) ≤ 6/7, which gives
 0
 
γ 
γ
6
2
log
− log
≤ log
≤ − .
3
2
7
9
viii

It follows that

γ
log δ


log δ + log

γ 
3


− log

γ0
2



γ
≤
log δ



2
log δ −
.
9

(11)

Plugging Equation (11) into Equation (10) gives


2
2γ
γ
2γ
0
log δ −
= γ−
γ ≤
≤ 2|Nuni | + γ 0 −
,
log δ
9
9 log δ
9 log δ
implying that |Nuni | ≥ γ/(9 log δ).
By corollaries A.13, A.8 and A.15 we get the following result. Denote


 min{1/(9 log x), 1/20},

1/(9 log(2x)),
MG (x) = max
.


max{(1 − 1/t)(2.0087/ log(tx)) | t > 1}
Corollary A.16 In GS , there is a subset S 0 of S with |Γ1S (S 0 )| ≥ γ · MG (δ) .
Observation A.17 max{min{γ/(9 log δ), γ/20}, γ/(9 log(2δ))} is given by


if δ ≤ 211/9
γ/(9 log(2δ))
γ/20
if 211/9 ≤ δ ≤ 220/9


γ/(9 log δ)
otherwise.
Moreover, for every  > 0, if δ satisfies  ln(δ) − ln(ln δ) − ln(1 + ) − 1 ≥ 0, then max{γ(1 −
2.0087
1/t)(2.0087/ log(tδ)) | t > 1} = γ (1+)
log(δ) . In that case,
2.0087
max{γ/(9 log δ), max{γ(1 − 1/t)(1/(2(1 + c) logc (tδ)) | t > 1}} ≥ γ (1+)
log(δ) if and only if  < 17.0783,
i.e., to understand which expression is the maximum, we need to take 0 = min{ |  ln(δ) − ln(ln δ) −
ln(1 + ) − 1 ≥ 0} and then check if 0 < 17.0783 or not.
Let G = (V, E) be an (α, β)-expander, and for every S in V , denote γS = |Γ− (S)|. As G is an
(α, β)-expander, γS ≥ β|S|. Then, Corollary A.16 yields the following bound on βw .
Lemma A.18 Let G = (V, E) be an (α, β)-expander. Then,
(1) G is an (αw , βw )-wireless expander with αw = α and βw ≥ β · MG (δ̄).
(2) In the regime β ≥ 1, we have δS ≤ ∆/β, thus δ̄ ≤ ∆/β, and hence βw ≥ β · MG (∆/β).
Proof: Let S in V s.t. |S| ≤ αn, and let
GS = (S, Γ− (S), ES ) be the corresponding graph. Then, by Corollary A.16, |Γ1S (S 0 )| ≥ γS · MG (δS ) ≥
β|S| · MG (δS ). Now, MG (x) is a decreasing function, and as δS ≥ δ̄, we get that MG (δS ) ≥ MG (δ̄) and
thus |Γ1S (S 0 )| ≥ β|S| · MG (δ̄). Moreover, in the regime β ≥ 1, we have δS ≤ ∆/β, thus δ̄ ≤ ∆/β, and
hence |Γ1S (S 0 )| ≥ β|S| · MG (∆/β).
The bounds presented in Section A.2 on βw are functions of δ̄ (like the inequality βw ≥ β/(9 log(2δ̄))
that we proved in Corollary A.14). Theses bounds are usually hard to use, since in most cases we cannot
give an evaluation of δ̄. But there are cases in which we can evaluate δ̄, and get a better lower bound for
βw than β/(9 log(2∆)). One such example is the class of bounded arboricity graphs.

ix

