imported>Rynoryno: corrected date of publication

2026-04-17T12:51:34Z

corrected date of publication

← Older revision		Revision as of 13:51, 17 April 2026
Line 19:		Line 19:

	Intuitively,		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.		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.		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''}}}}.		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		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===		===Vertex expansion===
Line 126:		Line 126:
	=== Zig-zag product ===		=== Zig-zag product ===
	{{Main\|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}};		# If {{math\|''λ''{{sub\|1}} < 1}} and {{math\|''λ''{{sub\|2}} < 1}}, then {{math\|''φ''(''λ''{{sub\|1}}, ''λ''{{sub\|2}}) < 1}};
Line 147:		Line 147:

	===Randomized constructions===		===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.		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.

imported>OAbot: Open access bot: url-access updated in citation with #oabot.

2025-06-19T22:16:20Z

Open access bot: url-access updated in citation with #oabot.

Show changes

Expander graph - Revision history

imported>Rynoryno: corrected date of publication

imported>OAbot: Open access bot: url-access updated in citation with #oabot.