About: Common graph

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

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
dbp:wikiPageUsesTemplate
dcterms:subject
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
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License