Expander graph (original) (raw)

About DBpedia

Expander je graf, v němž pro každou množinu vrcholů V velikosti menší než k a pro množinu V' obsahující právě sousedy vrcholů z množiny V platí, že velikost V' je větší než velikost V. Jako ε-expander označujeme takový expander, kde |V'| ≥ (1+ε) |V|

Property Value
dbo:abstract Expander je graf, v němž pro každou množinu vrcholů V velikosti menší než k a pro množinu V' obsahující právě sousedy vrcholů z množiny V platí, že velikost V' je větší než velikost V. Jako ε-expander označujeme takový expander, kde |V' ≥ (1+ε)
dbo:wikiPageExternalLink https://web.archive.org/web/20070523090323/http:/www.yann-ollivier.org/specgraph/specgraph.html http://michaelnielsen.org/blog/archive/notes/expander_graphs.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://ttic.uchicago.edu/~prahladh/teaching/spring05/index.html https://web.archive.org/web/20160629170338/http:/www.math.ias.edu/~boaz/ExpanderCourse/ https://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/ https://www.ams.org/notices/200407/what-is.pdf https://www.quantamagazine.org/universal-method-to-sort-complex-information-found-20180813/
dbo:wikiPageID 9313 (xsd:integer)
dbo:wikiPageLength 33702 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1121114256 (xsd:integer)
dbo:wikiPageWikiLink dbr:Cambridge_University_Press dbr:Multigraph dbr:Algebraic_connectivity dbr:Algorithm dbc:Graph_families dbr:Hypercube_graph dbr:Peter_Sarnak dbr:Regular_graph dbr:Vitali_Milman dbr:Degree_(graph_theory) dbr:Derandomization dbr:Independent_set_(graph_theory) dbr:Pseudorandom_generator dbr:Complete_graph dbr:Computer_network dbr:Connectivity_(graph_theory) dbr:Cryptography dbr:SL_(complexity) dbr:Orthogonal dbr:Symmetric_matrix dbr:Salil_Vadhan dbr:Eigenvalue dbr:Eigenvector dbr:Graph_coloring dbr:Boundary_(graph_theory) dbr:Erdős–Rényi_model dbr:L_(complexity) dbr:Zig-zag_product dbr:Linear_algebra dbr:Component_(graph_theory) dbr:Computational_complexity_theory dbr:Computer_science dbr:PCP_theorem dbr:Superstrong_approximation dbr:Avi_Wigderson dbr:Additive_combinatorics dbr:Hash_function dbr:Laplacian_matrix dbr:Spectral_graph_theory dbr:Stationary_distribution dbr:Adjacency_matrix dbr:Alexander_Lubotzky dbr:Alon-Boppana_bound dbr:American_Mathematical_Society dbr:Edge_(graph_theory) dbr:Noga_Alon dbr:Cayley_graph dbr:Cheeger_bound dbr:Cheeger_constant dbr:Directed_graph dbr:Graph_theory dbr:Journal_of_the_ACM dbr:Rayleigh_quotient dbr:Riemannian_geometry dbr:ACM_SIGACT_News dbr:Abstract_algebra dbr:Cheeger_constant_(graph_theory) dbr:Chernoff_bound dbr:Bipartite_graph dbr:Distance_(graph_theory) dbr:Markov_chains dbr:Sorting_network dbr:Spectral_theorem dbr:Omer_Reingold dbr:Ramanujan_graph dbr:Vertex_(graph_theory) dbr:Expander_code dbr:Expander_mixing_lemma dbr:Extractor_(mathematics) dbr:Extremal_graph_theory dbr:Random_regular_graph dbr:Finite_geometry dbr:Random_graph dbr:Spectral_gap dbr:2-norm dbr:Markov_transition_matrix dbr:Singular_values dbr:Error-correcting_code dbr:Sparse_graph
dbp:wikiPageUsesTemplate dbt:Citation dbt:Cite_book dbt:Frac dbt:Harvtxt dbt:Main_article dbt:Main_articles dbt:Math dbt:Mvar dbt:Overline dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfn dbt:Sfrac dbt:Short_description dbt:Sub dbt:Sup dbt:Abs
dct:subject dbc:Graph_families
gold:hypernym dbr:Graph
rdf:type dbo:Software yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659
rdfs:comment Expander je graf, v němž pro každou množinu vrcholů V velikosti menší než k a pro množinu V' obsahující právě sousedy vrcholů z množiny V platí, že velikost V' je větší než velikost V. Jako ε-expander označujeme takový expander, kde |V' ≥ (1+ε)
rdfs:label Expander (graf) (cs) Expander-Graph (de) Expander graph (en) 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-cs:Expander graph dbpedia-de:Expander graph dbpedia-fr:Expander graph dbpedia-he:Expander graph http://mn.dbpedia.org/resource/Экспандер_граф dbpedia-pl:Expander graph dbpedia-ru:Expander graph dbpedia-uk:Expander graph dbpedia-zh:Expander graph https://global.dbpedia.org/id/4x1f6
prov:wasDerivedFrom wikipedia-en:Expander_graph?oldid=1121114256&ns=0
foaf:isPrimaryTopicOf wikipedia-en:Expander_graph
is dbo:wikiPageDisambiguates of dbr:Expander
is dbo:wikiPageRedirects of dbr:Expander_graphs dbr:Expander_family dbr:Expanding_graph
is dbo:wikiPageWikiLink of dbr:Elementary_Number_Theory,_Group_Theory_and_Ramanujan_Graphs dbr:Book_embedding dbr:Approximate_group dbr:Hypercube_graph dbr:Bethe_lattice dbr:List_of_graph_theory_topics dbr:Incompressibility_method dbr:Connectivity_(graph_theory) dbr:Generalized_polygon dbr:Girth_(graph_theory) dbr:Glossary_of_graph_theory dbr:Gossip_protocol dbr:Bramble_(graph_theory) dbr:Congruence_subgroup dbr:Connectomics dbr:The_Princeton_Companion_to_Mathematics dbr:Zig-zag_product dbr:Arithmetic_Fuchsian_group dbr:Computational_hardness_assumption dbr:Feedback_arc_set dbr:PCP_theorem dbr:Planar_separator_theorem dbr:Markov_Chains_and_Mixing_Times dbr:Avi_Wigderson dbr:GNRS_conjecture dbr:Giuliana_Davidoff dbr:Lattice_(discrete_subgroup) dbr:Graph_expansion dbr:Spectral_graph_theory dbr:Adjacency_matrix dbr:Alon–Boppana_bound dbr:Cayley_graph dbr:Cheeger_bound dbr:Isoperimetric_inequality dbr:Kazhdan's_property_(T) dbr:Sexual_dimorphism dbr:Grigory_Margulis dbr:Cheeger_constant_(graph_theory) dbr:Thin_group_(algebraic_group_theory) dbr:Disperser dbr:Sorting_network dbr:Expander dbr:Michael_Sipser dbr:Ramanujan_graph dbr:Randomized_algorithm dbr:Chris_Umans dbr:Expander_code dbr:Expander_mixing_lemma dbr:Expander_walk_sampling dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:The_Art_of_Computer_Programming dbr:Symmetric_Turing_machine dbr:Nati_Linial dbr:Small_cancellation_theory dbr:Tabulation_hashing dbr:Skip_graph dbr:Supersingular_isogeny_graph dbr:Expander_graphs dbr:Expander_family dbr:Expanding_graph
is foaf:primaryTopic of wikipedia-en:Expander_graph