Editing Expander graph (section)

===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}}</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 2024 Alon produced an explicit construction for near Ramanujan graphs of every vertex size and degree pair.