Independence complex (original) (raw)
The independence complex of a graph is a mathematical object describing the independent sets of the graph. Formally, the independence complex of an undirected graph G, denoted by I(G), is an abstract simplicial complex (that is, a family of finite sets closed under the operation of taking subsets), formed by the sets of vertices in the independent sets of G. Any subset of an independent set is itself an independent set, so I(G) is indeed closed under taking subsets.
| Property | Value |
|---|---|
| dbo:abstract | The independence complex of a graph is a mathematical object describing the independent sets of the graph. Formally, the independence complex of an undirected graph G, denoted by I(G), is an abstract simplicial complex (that is, a family of finite sets closed under the operation of taking subsets), formed by the sets of vertices in the independent sets of G. Any subset of an independent set is itself an independent set, so I(G) is indeed closed under taking subsets. Every independent set in a graph is a clique in its complement graph, and vice versa. Therefore, the independence complex of a graph equals the clique complex of its complement graph, and vice versa. (en) |
| dbo:wikiPageID | 64659151 (xsd:integer) |
| dbo:wikiPageLength | 7052 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1104072729 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Rook_(chess) dbr:Meshulam's_game dbr:Total_dominating_set dbr:Undirected_graph dbr:Independent_set_(graph_theory) dbr:Induced_matching dbr:Matching_(graph_theory) dbr:Chessboard dbr:Line_graph dbr:Clique_(graph_theory) dbr:Clique_complex dbr:Complement_graph dbr:Abstract_simplicial_complex dbc:Simplicial_homology dbc:Graph_theory dbc:Simplicial_sets dbr:Chordal_graph dbr:Bipartite_graph dbr:Homological_connectivity dbr:Reduced_homology dbr:Dominating_set dbr:Graph_(graph_theory) dbr:Rainbow-independent_set dbr:Homology_group |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Rp |
| dct:subject | dbc:Simplicial_homology dbc:Graph_theory dbc:Simplicial_sets |
| rdfs:comment | The independence complex of a graph is a mathematical object describing the independent sets of the graph. Formally, the independence complex of an undirected graph G, denoted by I(G), is an abstract simplicial complex (that is, a family of finite sets closed under the operation of taking subsets), formed by the sets of vertices in the independent sets of G. Any subset of an independent set is itself an independent set, so I(G) is indeed closed under taking subsets. (en) |
| rdfs:label | Independence complex (en) |
| owl:sameAs | wikidata:Independence complex https://global.dbpedia.org/id/FRePr |
| prov:wasDerivedFrom | wikipedia-en:Independence_complex?oldid=1104072729&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Independence_complex |
| is dbo:wikiPageRedirects of | dbr:Matching_complex |
| is dbo:wikiPageWikiLink of | dbr:Meshulam's_game dbr:Paul_Seymour_(mathematician) dbr:Clique_complex dbr:Abstract_simplicial_complex dbr:Hall-type_theorems_for_hypergraphs dbr:Homological_connectivity dbr:Rainbow-independent_set dbr:Matching_complex |
| is foaf:primaryTopic of | wikipedia-en:Independence_complex |