diff --git a/metadata/entries/Expander_Graphs.toml b/metadata/entries/Expander_Graphs.toml new file mode 100644 --- /dev/null +++ b/metadata/entries/Expander_Graphs.toml @@ -0,0 +1,36 @@ +title = "Expander Graphs" +date = 2023-03-03 +topics = [ + "Computer science/Algorithms/Graph", + "Mathematics/Graph theory", + "Mathematics/Probability theory", +] +abstract = """ +Expander Graphs are low-degree graphs that are highly connected. They have diverse +applications, for example in derandomization and pseudo-randomness, error-correcting codes, as well +as pure mathematical subjects such as metric embeddings. This entry formalizes the concept and +derives main theorems about them such as Cheeger's inequality or tail bounds on distribution of +random walks on them. It includes a strongly explicit construction for every size and spectral gap. +The latter is based on the Margulis-Gabber-Galil graphs and several graph operations +that preserve spectral properties. The proofs are based on the survey papers/monographs +by Hoory et al. and Vadhan, as well as results from Impagliazzo and Kabanets and Murtagh et al.""" +license = "bsd" +note = "" + +[authors] + +[authors.karayel] +email = "karayel_email" + +[contributors] + +[notify] +karayel = "karayel_email" + +[history] + +[extra] + +[related] +dois = [] +pubs = []