|
== Proofs ==
In this section, we will prove some of the above examples.
===Sidorenko graphs are common===
Recall that a SidorenkoA graph <math>F</math> is a Sidorenko graph satisfyingif it satisfies <math>t(F, W) \ge t(K_2, W)^{e(F)}</math> for all graphons <math>W</math>.
In Hencethat case, we should also have <math>t(F, 1 - W) \ge t(K_2, 1 - W)^{e(F)}</math>. NowFurthermore, observe that <math>t(K_2, W) + t(K_2, 1 - W) = 1 </math>, which follows from the definition of homomorphism density. Combining this with [[Jensen's inequality]] for the function <math>f(x) = x^{e(F)}</math>, we can see that:
<math>t(F, W) + t(F, 1 - W) \ge t(K_2, W)^{e(F)} + t(K_2, 1 - W)^{e(F)}
===The triangle graph is common===
Here, we will expandExpand the integral expression for <math>t(K_3, 1 - W)</math> and take into account the symmetry between the variables:
<math>\int_{[0, 1]^3} (1 - W(x, y))(1 - W(y, z))(1 - W(z, x)) dx dy dz
= 1 - 3 \int_{[0, 1]^2} W(x, y) + 3 \int_{[0, 1]^3} W(x, y) W(x, z) dx dy dz - \int_{[0, 1]^3} W(x, y) W(y, z) W(z, x) dx dy dz</math>
Now, observe that eachEach term in the expression can be written in terms of homomorphism densities of smaller graphs. Indeed, byBy the definition of homomorphism densities, we have:
: <math>\int_{[0, 1]^2} W(x, y) dx dy = t(K_2, W) </math>
: <math>\int_{[0, 1]^3} W(x, y) W(y, z) W(z, x) dx dy dz = t(K_3, W)</math>
(Note thatwhere <math>K_{1, 2}</math> denotes the [[complete bipartite graph]] on <math>1</math> vertex on one part and <math>2</math> vertices on the other.) Hence, weIt getfollows:
: <math>t(K_3, W) + t(K_3, 1 - W) = 1 - 3 t(K_2, W) + 3 t(K_{1, 2}, W) </math>.
Now, in order to relate <math>t(K_{1, 2}, W)</math> can be related to <math>t(K_2, W)</math>, notethanks that we can exploitto the symmetry between the variables <math>y </math> and <math>z</math> to write:
<math display="block">\begin{alignat}{4}
t(K_{1, 2}, W) &= \int_{[0, 1]^3} W(x, y) W(x, z) dx dy dz && \\
&= \int_{x \in [0, 1]} \bigg( \int_{y \in [0, 1]} W(x, y) \bigg) \bigg( \int_{z \in [0, 1]} W(x, z) \bigg) && \\
&= \int_{x \in [0, 1]} \bigg( \int_{y \in [0, 1]} W(x, y) \bigg)^2 && \\
&\ge \bigg( \int_{x \in [0, 1]} \int_{y \in [0, 1]} W(x, y) \bigg)^2 = t(K_2, W)^2
\end{alignat}</math>
\end{alignat}</math>where we used the integral [[Cauchy–Schwarz inequality]] in the last step. Finally, our desired result follows from the above inequality:
where the last step follows from the integral [[Cauchy–Schwarz inequality]]. Finally:
<math>t(K_3, W) + t(K_3, 1 - W) \ge 1 - 3 t(K_2, W) + 3 t(K_{2}, W)^2
= 1/4 + 3 \big( t(K_2, W) - 1/2 \big)^2 \ge 1/4</math>.
This above proof can be obtained from taking the 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 ==
|
