Common graph (original) (raw)
In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking, is a common graph if it "commonly" appears as a subgraph, in a sense that the total number of copies of in any graph and its complement is a large fraction of all possible copies of on the same vertices. Intuitively, if contains few copies of , then its complement must contain lots of copies of in order to compensate for it.
Property | Value |
---|---|
dbo:abstract | In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking, is a common graph if it "commonly" appears as a subgraph, in a sense that the total number of copies of in any graph and its complement is a large fraction of all possible copies of on the same vertices. Intuitively, if contains few copies of , then its complement must contain lots of copies of in order to compensate for it. Common graphs are closely related to other graph notions dealing with homomorphism density inequalities. For example, common graphs are a more general case of Sidorenko graphs. (en) |
dbo:wikiPageID | 69389162 (xsd:integer) |
dbo:wikiPageLength | 9382 (xsd:nonNegativeInteger) |
dbo:wikiPageRevisionID | 1094769436 (xsd:integer) |
dbo:wikiPageWikiLink | dbc:Graph_families dbr:Cycle_(graph_theory) dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Graph_(discrete_mathematics) dbr:Graph_homomorphism dbr:Erdős–Rényi_model dbr:Complement_graph dbr:Cauchy–Schwarz_inequality dbr:Edge_coloring dbr:Graph_theory dbr:Graphon dbr:Jensen's_inequality dbc:Extremal_graph_theory dbr:Bipartite_graph dbr:Homomorphism_density dbr:Extremal_graph_theory dbr:Sidorenko's_conjecture dbr:Triangle_graph |
dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
dct:subject | dbc:Graph_families dbc:Extremal_graph_theory |
rdfs:comment | In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking, is a common graph if it "commonly" appears as a subgraph, in a sense that the total number of copies of in any graph and its complement is a large fraction of all possible copies of on the same vertices. Intuitively, if contains few copies of , then its complement must contain lots of copies of in order to compensate for it. (en) |
rdfs:label | Common graph (en) |
owl:sameAs | wikidata:Common graph https://global.dbpedia.org/id/GYgVv |
prov:wasDerivedFrom | wikipedia-en:Common_graph?oldid=1094769436&ns=0 |
foaf:isPrimaryTopicOf | wikipedia-en:Common_graph |
is dbo:wikiPageWikiLink of | dbr:List_of_graph_theory_topics dbr:Homomorphism_density dbr:Sidorenko's_conjecture |
is foaf:primaryTopic of | wikipedia-en:Common_graph |