Common graph: Difference between revisions

Revision as of 17:05, 24 May 2022

Revision as of 17:05, 24 May 2022

Line 1:

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

{{AFC submission|||u=Unubold Lake Munkhbat Choros|ns=118|ts=20220118051301}} <!-- Do not remove this line! -->

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

{{AFC comment|1=Good coverage in ''Large Networks and Graph Limits'', but I'd still like to see references inline for each piece of information. — [[User:Bilorv|Bilorv]] ('''[[User talk:Bilorv|<span style="color:purple">talk</span>]]''') 20:07, 20 January 2022 (UTC)}}

{{AFC comment|1=Really interesting read, but the Wikipedia style isn't there yet. I've gone through rewriting and formatting to be more in line with the Wikipedia style, but the referencing remains to be done.

We need more papers than this that mention/use/introduce theory around common graphs, and every fact in Wikipedia needs to be clearly attributed to a particular source. Which reference does each proof come from? Where does the definition, the intuitions and the examples come from? — [[User:Bilorv|Bilorv]] ('''[[User talk:Bilorv|<span style="color:purple">talk</span>]]''') 01:48, 22 December 2021 (UTC)}}

----

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

{{Draft topics|computing}}

{{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.

Line 23 ⟶ 10:

<math>t(F, W) + t(F, 1 - W) \ge 2^{-e(F)+1}</math>

holds for any [[graphon]] <math>W</math>, where <math>e(F)</math> is the number of edges of <math>F</math> and <math>t(F, W)</math> is the [[homomorphism density]] (see the book "''Large Networks and Graph Limits''".<ref>{{Cite web|title=Large Networks and Graph Limits|url=https://bookstore.ams.org/coll-60/|access-date=2022-01-13|website=bookstore.ams.org}}</ref> and a survey "''Very Large Graphs''"<ref>{{Cite journal|last=Lovasz|first=Laszlo|date=2009-02-01|title=Very large graphs|url=http://arxiv.org/abs/0902.0132|journal=arXiv:0902.0132 [math]|arxiv=0902.0132}}</ref> , both by [[László Lovász]], for introduction to the theory of [[graph limits]]). Here, note that the inequality attains the lower bound when <math>W</math> is the constant graphon <math>W \equiv 1/2</math>. So, the inequality is tight.       

== Interpretations of definition ==

Line 76 ⟶ 63:

= 1/4 + 3 \big( t(K_2, W) - 1/2 \big)^2 \ge 1/4</math>.

This above proof can be obtained from taking continuous analog of Theorem 1 in Goodman 1959 paper, "On Sets Of Acquaintances And Strangers At Any Party"<ref>{{Cite journal|last=Goodman|first=A. W.|date=1959|title=On Sets of Acquaintances and Strangers at any Party|url=https://www.jstor.org/stable/2310464|journal=The American Mathematical Monthly|volume=66|issue=9|pages=778–783|doi=10.2307/2310464|jstor=2310464|issn=0002-9890}}</ref>.

== See also ==

Line 83 ⟶ 70:

== References ==

<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->

{{reflist}}

[[Category:Mathematics]]

[[Category:Science]]

[[Category:Concepts]]