Common graph: Difference between revisions

Revision as of 05:12, 18 January 2022

Revision as of 05:13, 18 January 2022

Line 1:

{{Short description|In extremal graph theory, common graphs arise as an interesting concept}}

{{Draft topics|stemcomputing}}

{{AfC topic|stem}}

{{AfC submission|||ts=20220118051301|u=Unubold Lake Munkhbat Choros|ns=118}}

{{AFC submission|d|nn|u=Unubold Lake Munkhbat Choros|ns=118|decliner=Bilorv|declinets=20211222014800|ts=20211221072630}} <!-- Do not remove this line! -->

Line 7 ⟶ 11:

----

{{Short description|In extremal graph theory, common graphs arise as an interesting concept}}

{{Draft topics|stem}}

{{AfC topic|stem}}

In [[graph theory]], an area of mathematics, '''common graphs''' belong to a branch of [[extremal graph theory]] concerning [[Homomorphism density|inequalities in homomorphism densities]]. Roughly speaking, <math>F</math> is a common [[Graph (discrete mathematics)|graph]] if it "commonly" appears as a subgraph, in a sense that the total number of copies of <math>F</math> in any graph <math>G</math> and its [[Complement graph|complement]] <math>\overline{G}</math> is a large fraction of all possible copies of <math>F</math> on the same vertices. Intuitively, if <math>G</math> contains few copies of <math>F</math>, then its complement <math>\overline{G}</math> must contain lots of copies of <math>F</math> in order to compensate for it.