Expander graph: Difference between revisions

Line 19:

Intuitively,

: <math>\min {|\partial S|} = \min E({S}, \overline{S})</math>

: <math>\min {|\partial S|} = \min |E({S}, \overline{S})|</math>

is the minimum number of edges that need to be cut in order to split the graph in two.

The edge expansion normalizes this concept by dividing with smallest number of vertices among the two parts.

Line 28:

Notice that in {{math|min {{abs|∂''S''}}}}, the optimization can be equivalently done either over {{math|0 ≤ {{abs|''S''}} ≤ {{frac|''n''|2}}}} or over any non-empty subset, since <math>E(S, \overline{S}) = E(\overline{S}, S)</math>. The same is not true for {{math|''h''(''G'')}} because of the normalization by {{math|{{abs|''S''}}}}.

If we want to write {{math|''h''(''G'')}} with an optimization over all non-empty subsets, we can rewrite it as

: <math>h(G) = \min_{\emptyset \subsetneq S\subsetneq V(G) } \frac{E({S}, \overline{S})}{\min\{|S|, |\overline{S}|\}}.</math>

: <math>h(G) = \min_{\emptyset \subsetneq S\subsetneq V(G) } \frac{|E({S}, \overline{S})|}{\min\{|S|, |\overline{S}|\}}.</math>

===Vertex expansion===

Line 126:

=== Zig-zag product ===

[[Omer Reingold|Reingold]], [[Salil Vadhan|Vadhan]], and [[Avi Wigderson|Wigderson]] introduced the zig-zag product in ~~2003~~.<ref name=":0">{{Cite book|last1=Reingold|first1=O.|last2=Vadhan|first2=S.|last3=Wigderson|first3=A.|title=Proceedings 41st Annual Symposium on Foundations of Computer Science |chapter=Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors |chapter-url=http://dx.doi.org/10.1109/sfcs.2000.892006|year=2000|pages=3–13|publisher=IEEE Comput. Soc|doi=10.1109/sfcs.2000.892006|isbn=0-7695-0850-2|s2cid=420651}}</ref> Roughly speaking, the zig-zag product of two expander graphs produces a graph with only slightly worse expansion. Therefore, a zig-zag product can also be used to construct families of expander graphs. If {{mvar|G}} is a {{math|(''n'', ''d'', ''λ''{{sub|1}})}}-graph and {{mvar|H}} is an {{math|(''m'', ''d'', ''λ''{{sub|2}})}}-graph, then the zig-zag product {{math|''G'' ◦ ''H''}} is a {{math|(''nm'', ''d''{{sup|2}}, ''φ''(''λ''{{sub|1}}, ''λ''{{sub|2}}))}}-graph where {{mvar|φ}} has the following properties.

[[Omer Reingold|Reingold]], [[Salil Vadhan|Vadhan]], and [[Avi Wigderson|Wigderson]] introduced the zig-zag product in 2000.<ref name=":0">{{Cite book|last1=Reingold|first1=O.|last2=Vadhan|first2=S.|last3=Wigderson|first3=A.|title=Proceedings 41st Annual Symposium on Foundations of Computer Science |chapter=Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors |chapter-url=http://dx.doi.org/10.1109/sfcs.2000.892006|year=2000|pages=3–13|publisher=IEEE Comput. Soc|doi=10.1109/sfcs.2000.892006|isbn=0-7695-0850-2|s2cid=420651}}</ref> Roughly speaking, the zig-zag product of two expander graphs produces a graph with only slightly worse expansion. Therefore, a zig-zag product can also be used to construct families of expander graphs. If {{mvar|G}} is a {{math|(''n'', ''d'', ''λ''{{sub|1}})}}-graph and {{mvar|H}} is an {{math|(''m'', ''d'', ''λ''{{sub|2}})}}-graph, then the zig-zag product {{math|''G'' ◦ ''H''}} is a {{math|(''nm'', ''d''{{sup|2}}, ''φ''(''λ''{{sub|1}}, ''λ''{{sub|2}}))}}-graph where {{mvar|φ}} has the following properties.

# If {{math|''λ''{{sub|1}} < 1}} and {{math|''λ''{{sub|2}} < 1}}, then {{math|''φ''(''λ''{{sub|1}}, ''λ''{{sub|2}}) < 1}};

Line 147:

===Randomized constructions===

There are many results that show the existence of graphs with good expansion properties through probabilistic arguments. In fact, the existence of expanders was first proved by Pinsker<ref>{{Cite journal|last=Pinkser|first=M.|title=On the Complexity of a Concentrator|journal=[[SIAM Journal on Computing]]|year=1973|publisher=SIAM|citeseerx=10.1.1.393.1430}}</ref> who showed that for a randomly chosen {{mvar|n}} vertex left {{mvar|d}} regular [[bipartite graph]], {{math|{{abs|''N''(''S'')}} ≥ (''d'' – 2){{abs|''S''}}}} for all subsets of vertices {{math|{{abs|''S''}} ≤ ''c{{sub|d}}n''}} with high probability, where {{mvar|c{{sub|d}}}} is a constant depending on {{mvar|d}} that is {{math|''O''(''d''{{sup|-4}})}}. Alon and Roichman <ref>{{Cite journal|last1=Alon|first1=N.|last2=Roichman|first2=Y.|title=Random Cayley graphs and Expanders|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240050203|journal=Random Structures and Algorithms|year=1994|volume=5|issue=2|pages=271–284|publisher=Wiley Online Library|doi=10.1002/rsa.3240050203|url-access=subscription}}</ref> showed that for every {{math|1 > ''ε'' > 0}}, there is some {{math|''c''(''ε'') > 0}} such that the following holds: For a group {{mvar|G}} of order {{mvar|n}}, consider the Cayley graph on {{mvar|G}} with {{math|''c''(''ε'') log{{sub|2}} ''n''}} randomly chosen elements from {{mvar|G}}. Then, in the limit of {{mvar|n}} getting to infinity, the resulting graph is almost surely an {{math|''ε''}}-expander.

There are many results that show the existence of graphs with good expansion properties through probabilistic arguments. In fact, the existence of expanders was first proved by Pinsker<ref>{{Cite journal|last=Pinkser|first=M.|title=On the Complexity of a Concentrator|journal=[[SIAM Journal on Computing]]|year=1973|publisher=SIAM|citeseerx=10.1.1.393.1430}}</ref> who showed that for a randomly chosen {{mvar|n}} vertex left {{mvar|d}} regular [[bipartite graph]], {{math|{{abs|''N''(''S'')}} ≥ (''d'' – 2){{abs|''S''}}}} for all subsets of vertices {{math|{{abs|''S''}} ≤ ''c{{sub|d}}n''}} [[with high probability]], where {{mvar|c{{sub|d}}}} is a constant depending on {{mvar|d}} that is {{math|''O''(''d''{{sup|-4}})}}. Alon and Roichman <ref>{{Cite journal|last1=Alon|first1=N.|last2=Roichman|first2=Y.|title=Random Cayley graphs and Expanders|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240050203|journal=Random Structures and Algorithms|year=1994|volume=5|issue=2|pages=271–284|publisher=Wiley Online Library|doi=10.1002/rsa.3240050203|url-access=subscription}}</ref> showed that for every {{math|1 > ''ε'' > 0}}, there is some {{math|''c''(''ε'') > 0}} such that the following holds: For a group {{mvar|G}} of order {{mvar|n}}, consider the Cayley graph on {{mvar|G}} with {{math|''c''(''ε'') log{{sub|2}} ''n''}} randomly chosen elements from {{mvar|G}}. Then, in the limit of {{mvar|n}} getting to infinity, the resulting graph is almost surely an {{math|''ε''}}-expander.

In 2021, Alexander modified an MCMC algorithm to look for randomized constructions to produce Ramanujan graphs with a fixed vertex size and degree of regularity.<ref>{{cite arXiv | eprint=2110.01407 | last1=Alexander | first1=Clark | title=On Near Optimal Spectral Expander Graphs of Fixed Size | date=2021 | class=cs.DM }}</ref> The results show the Ramanujan graphs exist for every vertex size and degree pair up to 2000 vertices.

@@ Line 19: / Line 19: @@
 Intuitively,
-: <math>\min {|\partial S|} = \min E({S}, \overline{S})</math>
+: <math>\min {|\partial S|} = \min |E({S}, \overline{S})|</math>
 is the minimum number of edges that need to be cut in order to split the graph in two.
 The edge expansion normalizes this concept by dividing with smallest number of vertices among the two parts.
@@ Line 28: / Line 28: @@
 Notice that in {{math|min {{abs|∂''S''}}}}, the optimization can be equivalently done either over {{math|0 ≤ {{abs|''S''}} ≤ {{frac|''n''|2}}}} or over any non-empty subset, since  <math>E(S, \overline{S}) = E(\overline{S}, S)</math>. The same is not true for {{math|''h''(''G'')}} because of the normalization by {{math|{{abs|''S''}}}}.
 If we want to write {{math|''h''(''G'')}} with an optimization over all non-empty subsets, we can rewrite it as
-: <math>h(G) = \min_{\emptyset \subsetneq S\subsetneq V(G) } \frac{E({S}, \overline{S})}{\min\{|S|, |\overline{S}|\}}.</math>
+: <math>h(G) = \min_{\emptyset \subsetneq S\subsetneq V(G) } \frac{|E({S}, \overline{S})|}{\min\{|S|, |\overline{S}|\}}.</math>
 ===Vertex expansion===
@@ Line 126: / Line 126: @@
 === Zig-zag product ===
 {{Main|Zig-zag product}}
-[[Omer Reingold|Reingold]], [[Salil Vadhan|Vadhan]], and [[Avi Wigderson|Wigderson]] introduced the zig-zag product in 2003.<ref name=":0">{{Cite book|last1=Reingold|first1=O.|last2=Vadhan|first2=S.|last3=Wigderson|first3=A.|title=Proceedings 41st Annual Symposium on Foundations of Computer Science |chapter=Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors |chapter-url=http://dx.doi.org/10.1109/sfcs.2000.892006|year=2000|pages=3–13|publisher=IEEE Comput. Soc|doi=10.1109/sfcs.2000.892006|isbn=0-7695-0850-2|s2cid=420651}}</ref>  Roughly speaking, the zig-zag product of two expander graphs produces a graph with only slightly worse expansion. Therefore, a zig-zag product can also be used to construct families of expander graphs. If {{mvar|G}} is a {{math|(''n'', ''d'', ''λ''{{sub|1}})}}-graph and {{mvar|H}} is an {{math|(''m'', ''d'', ''λ''{{sub|2}})}}-graph, then the zig-zag product {{math|''G'' ◦ ''H''}} is a {{math|(''nm'', ''d''{{sup|2}}, ''φ''(''λ''{{sub|1}}, ''λ''{{sub|2}}))}}-graph where {{mvar|φ}} has the following properties.
+[[Omer Reingold|Reingold]], [[Salil Vadhan|Vadhan]], and [[Avi Wigderson|Wigderson]] introduced the zig-zag product in 2000.<ref name=":0">{{Cite book|last1=Reingold|first1=O.|last2=Vadhan|first2=S.|last3=Wigderson|first3=A.|title=Proceedings 41st Annual Symposium on Foundations of Computer Science |chapter=Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors |chapter-url=http://dx.doi.org/10.1109/sfcs.2000.892006|year=2000|pages=3–13|publisher=IEEE Comput. Soc|doi=10.1109/sfcs.2000.892006|isbn=0-7695-0850-2|s2cid=420651}}</ref>  Roughly speaking, the zig-zag product of two expander graphs produces a graph with only slightly worse expansion. Therefore, a zig-zag product can also be used to construct families of expander graphs. If {{mvar|G}} is a {{math|(''n'', ''d'', ''λ''{{sub|1}})}}-graph and {{mvar|H}} is an {{math|(''m'', ''d'', ''λ''{{sub|2}})}}-graph, then the zig-zag product {{math|''G'' ◦ ''H''}} is a {{math|(''nm'', ''d''{{sup|2}}, ''φ''(''λ''{{sub|1}}, ''λ''{{sub|2}}))}}-graph where {{mvar|φ}} has the following properties.
 # If {{math|''λ''{{sub|1}} < 1}} and {{math|''λ''{{sub|2}} < 1}}, then {{math|''φ''(''λ''{{sub|1}}, ''λ''{{sub|2}}) < 1}};
@@ Line 147: / Line 147: @@
 ===Randomized constructions===
-There are many results that show the existence of graphs with good expansion properties through probabilistic arguments. In fact, the existence of expanders was first proved by Pinsker<ref>{{Cite journal|last=Pinkser|first=M.|title=On the Complexity of a Concentrator|journal=[[SIAM Journal on Computing]]|year=1973|publisher=SIAM|citeseerx=10.1.1.393.1430}}</ref> who showed that for a randomly chosen {{mvar|n}} vertex left {{mvar|d}} regular [[bipartite graph]],  {{math|{{abs|''N''(''S'')}} ≥ (''d'' – 2){{abs|''S''}}}} for all subsets of vertices {{math|{{abs|''S''}} ≤ ''c{{sub|d}}n''}} with high probability, where {{mvar|c{{sub|d}}}} is a constant depending on {{mvar|d}} that is {{math|''O''(''d''{{sup|-4}})}}. Alon and Roichman <ref>{{Cite journal|last1=Alon|first1=N.|last2=Roichman|first2=Y.|title=Random Cayley graphs and Expanders|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240050203|journal=Random Structures and Algorithms|year=1994|volume=5|issue=2|pages=271–284|publisher=Wiley Online Library|doi=10.1002/rsa.3240050203|url-access=subscription}}</ref> showed that for every {{math|1 > ''ε'' > 0}}, there is some {{math|''c''(''ε'') > 0}} such that the following holds: For a group {{mvar|G}} of order {{mvar|n}}, consider the Cayley graph on {{mvar|G}} with {{math|''c''(''ε'') log{{sub|2}} ''n''}} randomly chosen elements from {{mvar|G}}. Then, in the limit of {{mvar|n}} getting to infinity, the resulting graph is almost surely an {{math|''ε''}}-expander.
+There are many results that show the existence of graphs with good expansion properties through probabilistic arguments. In fact, the existence of expanders was first proved by Pinsker<ref>{{Cite journal|last=Pinkser|first=M.|title=On the Complexity of a Concentrator|journal=[[SIAM Journal on Computing]]|year=1973|publisher=SIAM|citeseerx=10.1.1.393.1430}}</ref> who showed that for a randomly chosen {{mvar|n}} vertex left {{mvar|d}} regular [[bipartite graph]],  {{math|{{abs|''N''(''S'')}} ≥ (''d'' – 2){{abs|''S''}}}} for all subsets of vertices {{math|{{abs|''S''}} ≤ ''c{{sub|d}}n''}} [[with high probability]], where {{mvar|c{{sub|d}}}} is a constant depending on {{mvar|d}} that is {{math|''O''(''d''{{sup|-4}})}}. Alon and Roichman <ref>{{Cite journal|last1=Alon|first1=N.|last2=Roichman|first2=Y.|title=Random Cayley graphs and Expanders|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240050203|journal=Random Structures and Algorithms|year=1994|volume=5|issue=2|pages=271–284|publisher=Wiley Online Library|doi=10.1002/rsa.3240050203|url-access=subscription}}</ref> showed that for every {{math|1 > ''ε'' > 0}}, there is some {{math|''c''(''ε'') > 0}} such that the following holds: For a group {{mvar|G}} of order {{mvar|n}}, consider the Cayley graph on {{mvar|G}} with {{math|''c''(''ε'') log{{sub|2}} ''n''}} randomly chosen elements from {{mvar|G}}. Then, in the limit of {{mvar|n}} getting to infinity, the resulting graph is almost surely an {{math|''ε''}}-expander.
 In 2021, Alexander modified an MCMC algorithm to look for randomized constructions to produce Ramanujan graphs with a fixed vertex size and degree of regularity.<ref>{{cite arXiv | eprint=2110.01407 | last1=Alexander | first1=Clark | title=On Near Optimal Spectral Expander Graphs of Fixed Size | date=2021 | class=cs.DM }}</ref> The results show the Ramanujan graphs exist for every vertex size and degree pair up to 2000 vertices.

Expander graph: Difference between revisions

Navigation menu

Search