Common graph (original) (raw)

About DBpedia

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