Common graph: Difference between revisions

Revision as of 12:04, 24 June 2022

Revision as of 06:35, 20 February 2023

Line 15:

== Interpretations of definition ==

For a graph <math>G</math>, we have <math>t(F, G) = t(F, W_{G}) </math> and <math>t(F, \overline{G})=t(F, 1 - W_G)</math> for the [[Graphon#Analytic Formulation|associated graphon]] <math>W_G</math>, since graphon associated to the complement <math>\overline{G}</math> is <math>W_{\overline{G}}=1 - W_G</math>. Hence, this formula provides us with the very informal intuition to take a close enough approximation, whatever that means,<ref>{{Cite journal|last1=Borgs|first1=C.|last2=Chayes|first2=J. T.|last3=Lovász|first3=L.|authorlink3=László Lovász|last4=Sós|first4=V. T.|authorlink4=Vera T. Sós|last5=Vesztergombi|first5=K.|authorlink5=Katalin Vesztergombi|date=2008-12-20|title=Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing|url=https://www.sciencedirect.com/science/article/pii/S0001870808002053|journal=[[Advances in Mathematics]]|language=en|volume=219|issue=6|pages=1801–1851|doi=10.1016/j.aim.2008.07.008|doi-access=free|s2cid=5974912|issn=0001-8708}}</ref> <math>W</math> to <math>W_G</math>, and see <math>t(F, W)</math> as roughly the fraction of labeled copies of graph <math>F</math> in "approximate" graph <math>G</math>. Then, we can assume the quantity <math>t(F, W) + t(F, 1 - W)</math> is roughly <math>t(F, G) + t(F, \overline{G})</math> and interpret the latter as the combined number of copies of <math>F</math> in <math>G</math> and <math>\overline{G}</math>. Hence, we see that <math>t(F, G) + t(F, \overline{G}) \gtrsim 2^{-e(F)+1}</math> holds. This, in turn, means that common graph <math>F</math> commonly appears as subgraph.

In other words, if we think of edges and non-edges as [[Edge coloring|2-coloring of edges]] of complete graph on the same vertices, then at least <math>2^{-e(F)+1}</math> fraction of all possible copies of <math>F</math> are monochromatic. Note that in a [[Erdős–Rényi model|Erdős–Rényi random graph]] <math>G = G(n, p)</math> with each edge drawn with probability <math>p=1/2 </math>, each [[graph homomorphism]] from <math>F</math> to <math>G</math> have probability <math>2 \cdot 2^{-e(F)} = 2^ {-e(F) +1}</math>of being monochromatic. So, common graph <math>F</math> is a graph where it attains its minimum number of appearance as a monochromatic subgraph of graph <math>G</math> at the graph <math>G=G(n, p)</math> with <math>p=1/2</math>