About: Expander graph

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Sparse graph used in the combinatorics branch of mathematics

Property	Value
dbo:description	sparse graph used in the combinatorics branch of mathematics (en) сильносвязный разреженный граф (ru) сильнозв'язний розріджений граф (uk)
dbo:thumbnail	wiki-commons:Special:FilePath/Vertex_expansion.svg?width=300
dbo:wikiPageExternalLink	https://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/ https://www.ams.org/notices/200407/what-is.pdf http://www.wisdom.weizmann.ac.il/%7Eoded/COL/expander.pdf http://www.cs.huji.ac.il/~dinuri/mypapers/combpcp.pdf%7Cciteseerx=10.1.1.103.2644%7Cs2cid=53244523 http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf http://michaelnielsen.org/blog/archive/notes/expander_graphs.pdf http://ttic.uchicago.edu/~prahladh/teaching/spring05/index.html https://web.archive.org/web/20160629170338/http:/www.math.ias.edu/~boaz/ExpanderCourse/ https://www.quantamagazine.org/universal-method-to-sort-complex-information-found-20180813/ https://web.archive.org/web/20070523090323/http:/www.yann-ollivier.org/specgraph/specgraph.html
dbo:wikiPageWikiLink	dbr:Extremal_graph_theory dbr:PCP_theorem dbr:Salil_Vadhan dbr:Superstrong_approximation dbr:Riemannian_geometry dbr:Sorting_network dbr:Adjacency_matrix dbr:Chernoff_bound dbr:Omer_Reingold dbr:Cambridge_University_Press dbr:Abstract_algebra dbr:Independent_set_(graph_theory) dbr:Multigraph dbr:SL_(complexity) dbr:Vitali_Milman dbr:Cryptography dbr:Eigenvector dbr:Directed_graph dbr:Connectivity_(graph_theory) dbr:Finite_geometry dbr:Expander_code dbr:Expander_mixing_lemma dbr:Extractor_(mathematics) dbr:Hypercube_graph dbr:L_(complexity) dbr:Computer_network dbr:Vertex_(graph_theory) dbr:Algorithm dbr:Graph_theory dbr:Bipartite_graph dbr:Graph_coloring dbr:Sparse_graph dbr:Cheeger_bound dbr:Cheeger_constant dbr:Cheeger_constant_(graph_theory) dbr:Computer_science dbr:Spectral_theorem dbr:Linear_algebra dbr:Avi_Wigderson dbr:Noga_Alon dbr:Alexander_Lubotzky dbr:Eigenvalue dbr:Computational_complexity_theory dbr:Orthogonal dbr:Error-correcting_code dbr:Complete_graph dbr:Symmetric_matrix dbr:American_Mathematical_Society dbr:Random_graph dbr:Peter_Sarnak dbr:Stationary_distribution dbr:Ramanujan_graph dbr:Pseudorandom_generator dbr:Erdős–Rényi_model dbr:Rayleigh_quotient dbr:Journal_of_the_ACM dbr:Component_(graph_theory) dbr:Spectral_graph_theory dbr:Hash_function dbr:Laplacian_matrix dbr:Distance_(graph_theory) dbr:Zig-zag_product dbr:Degree_(graph_theory) dbr:Cayley_graph dbr:Random_regular_graph dbr:Edge_(graph_theory) dbc:Graph_families dbr:Derandomization dbr:Regular_graph dbr:Algebraic_connectivity dbr:ACM_SIGACT_News dbr:Boundary_(graph_theory) dbr:Additive_combinatorics dbr:Spectral_gap dbr:Alon-Boppana_bound dbr:2-norm dbr:Markov_chains dbr:Markov_transition_matrix dbr:Singular_values
dbp:date	2016-08-17 (xsd:date)
dbp:url	https://web.archive.org/web/20160817025506/http:/michaelnielsen.org/blog/archive/notes/expander_graphs.pdf
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Main dbt:Reflist dbt:Math dbt:Overline dbt:Sfn dbt:Sub dbt:Sup dbt:Citation dbt:Cite_arXiv dbt:Refend dbt:Sfrac dbt:Refbegin dbt:Mvar dbt:Abs dbt:Frac dbt:Harvtxt dbt:Webarchive dbt:Short_description
dct:subject	dbc:Graph_families
gold:hypernym	dbr:Graph
rdfs:label	Expander graph (en) Expander (graf) (cs) Expander-Graph (de) Taux d'expansion (théorie des graphes) (fr) Ekspander (pl) Экспандер (теория графов) (ru) Збільшувач (теорія графів) (uk) 扩展图 (zh)
owl:sameAs	freebase:Expander graph yago-res:Expander graph wikidata:Expander graph dbpedia-de:Expander graph dbpedia-fr:Expander graph dbpedia-zh:Expander graph dbpedia-he:Expander graph dbpedia-ru:Expander graph dbpedia-pl:Expander graph dbpedia-cs:Expander graph dbpedia-mn:Expander graph dbpedia-uk:Expander graph dbpedia-global:Expander graph
prov:wasDerivedFrom	wikipedia-en:Expander_graph?oldid=1296419009&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Vertex_expansion.svg
foaf:isPrimaryTopicOf	wikipedia-en:Expander_graph
is dbo:knownFor of	dbr:Grigory_Margulis
is dbo:wikiPageDisambiguates of	dbr:Expander
is dbo:wikiPageRedirects of	dbr:Expander_graphs dbr:Expander_graphs dbr:Expander_family dbr:Expanding_graph
is dbo:wikiPageWikiLink of	dbr:Bethe_lattice dbr:PCP_theorem dbr:Planar_separator_theorem dbr:Thin_group_(algebraic_group_theory) dbr:Glossary_of_graph_theory dbr:Sorting_network dbr:Adjacency_matrix dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:The_Princeton_Companion_to_Mathematics dbr:Sexual_dimorphism dbr:Connectivity_(graph_theory) dbr:Feedback_arc_set dbr:Expander_code dbr:Expander_mixing_lemma dbr:Expander_walk_sampling dbr:Isoperimetric_inequality dbr:Hypercube_graph dbr:Girth_(graph_theory) dbr:Cheeger_bound dbr:Cheeger_constant_(graph_theory) dbr:Alon–Boppana_bound dbr:The_Art_of_Computer_Programming dbr:Avi_Wigderson dbr:Michael_Sipser dbr:Expander dbr:Ramanujan_graph dbr:Spectral_graph_theory dbr:Bramble_(graph_theory) dbr:Disperser dbr:List_of_graph_theory_topics dbr:Tabulation_hashing dbr:Zig-zag_product dbr:Cayley_graph dbr:Grigory_Margulis dbr:Randomized_algorithm dbr:Connectomics dbr:Skip_graph dbr:Small_cancellation_theory dbr:Nati_Linial dbr:Symmetric_Turing_machine dbr:Computational_hardness_assumption dbr:Congruence_subgroup dbr:Book_embedding dbr:Lattice_(discrete_subgroup) dbr:Incompressibility_method dbr:Arithmetic_Fuchsian_group dbr:Generalized_polygon dbr:Gossip_protocol dbr:Approximate_group dbr:Kazhdan's_property_(T) dbr:GNRS_conjecture dbr:Supersingular_isogeny_graph dbr:Markov_Chains_and_Mixing_Times dbr:Chris_Umans dbr:Elementary_Number_Theory,_Group_Theory_and_Ramanujan_Graphs dbr:Graph_expansion dbr:Giuliana_Davidoff dbr:Expander_graphs dbr:Expander_family dbr:Expanding_graph
is dbp:knownFor of	dbr:Grigory_Margulis
is foaf:primaryTopic of	wikipedia-en:Expander_graph