Common graph

Add links
From English Wikipedia @ Freddythechick

In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is a common graph if it "commonly" appears as a subgraph, in a sense that the total number of copies of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} in any graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} and its complement Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline{G}} is a large fraction of all possible copies of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} on the same vertices. Intuitively, if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} contains few copies of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} , then its complement Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline{G}} 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.

Definition

A graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is common if the inequality:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(F, W) + t(F, 1 - W) \ge 2^{-e(F)+1}}

holds for any graphon Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e(F)} is the number of edges of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(F, W)} is the homomorphism density.[1]

The inequality is tight because the lower bound is always reached when Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W} is the constant graphon Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W \equiv 1/2} .

Interpretations of definition

For a graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} , we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(F, G) = t(F, W_{G}) } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(F, \overline{G})=t(F, 1 - W_G)} for the associated graphon Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_G} , since graphon associated to the complement Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline{G}} is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_{\overline{G}}=1 - W_G} . Hence, this formula provides us with the very informal intuition to take a close enough approximation, whatever that means,[2] Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_G} , and see Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(F, W)} as roughly the fraction of labeled copies of graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} in "approximate" graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} . Then, we can assume the quantity Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(F, W) + t(F, 1 - W)} is roughly Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle t(F,G)+t(F,{\overline {G}})} and interpret the latter as the combined number of copies of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline{G}} . Hence, we see that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(F, G) + t(F, \overline{G}) \gtrsim 2^{-e(F)+1}} holds. This, in turn, means that common graph commonly appears as subgraph.

In other words, if we think of edges and non-edges as 2-coloring of edges of complete graph on the same vertices, then at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{-e(F)+1}} fraction of all possible copies of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} are monochromatic. Note that in a Erdős–Rényi random graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = G(n, p)} with each edge drawn with probability Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p=1/2 } , each graph homomorphism from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} have probability Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2 \cdot 2^{-e(F)} = 2^ {-e(F) +1}} of being monochromatic. So, common graph is a graph where it attains its minimum number of appearance as a monochromatic subgraph of graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} at the graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G=G(n, p)} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p=1/2}

. The above definition using the generalized homomorphism density can be understood in this way.

Examples

  • As stated above, all Sidorenko graphs are common graphs.[3] Hence, any known Sidorenko graph is an example of a common graph, and, most notably, cycles of even length are common.[4] However, these are limited examples since all Sidorenko graphs are bipartite graphs while there exist non-bipartite common graphs, as demonstrated below.
  • The triangle graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{3}} is one simple example of non-bipartite common graph.[5]
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_4 ^{-}} , the graph obtained by removing an edge of the complete graph on 4 vertices Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_4} , is common.[6]
  • Non-example: It was believed for a time that all graphs are common. However, it turns out that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{t}} is not common for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t \ge 4} .[7] In particular, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_4} is not common even though Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{4} ^{-}} is common.

Proofs

Sidorenko graphs are common

A graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is a Sidorenko graph if it satisfies Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(F, W) \ge t(K_2, W)^{e(F)}} for all graphons Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W} .

In that case, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(F, 1 - W) \ge t(K_2, 1 - W)^{e(F)}} . Furthermore, Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle t(K_{2},W)+t(K_{2},1-W)=1} , which follows from the definition of homomorphism density. Combining this with Jensen's inequality for the function Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(x)=x^{e(F)}} :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(F, W) + t(F, 1 - W) \ge t(K_2, W)^{e(F)} + t(K_2, 1 - W)^{e(F)} \ge 2 \bigg( \frac{t(K_2, W) + t(K_2, 1 - W)}{2} \bigg)^{e(F)} = 2^{-e(F) + 1}}

Thus, the conditions for common graph is met.[8]

The triangle graph is common

Expand the integral expression for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(K_3, 1 - W)} and take into account the symmetry between the variables:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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}

Each term in the expression can be written in terms of homomorphism densities of smaller graphs. By the definition of homomorphism densities:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_{[0, 1]^2} W(x, y) dx dy = t(K_2, W) }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int{[0, 1]^3} W(x, y) W(x, z) dx dy dz = t(K_{1, 2}, W) }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_{[0, 1]^3} W(x, y) W(y, z) W(z, x) dx dy dz = t(K_3, W)}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{1, 2}} denotes the complete bipartite graph on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} vertex on one part and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2} vertices on the other. It follows:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(K_3, W) + t(K_3, 1 - W) = 1 - 3 t(K_2, W) + 3 t(K_{1, 2}, W) } .

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(K_{1, 2}, W)} can be related to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(K_2, W)} thanks to the symmetry between the variables Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z} : Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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}}

where the last step follows from the integral Cauchy–Schwarz inequality. Finally:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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} .

This proof can be obtained from taking the continuous analog of Theorem 1 in "On Sets Of Acquaintances And Strangers At Any Party"[9]

See also

References

  1. ^ Large Networks and Graph Limits. American Mathematical Society. p. 297. Retrieved 2022-01-13.
  2. ^ Borgs, C.; Chayes, J. T.; Lovász, L.; Sós, V. T.; Vesztergombi, K. (2008-12-20). "Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing". Advances in Mathematics. 219 (6): 1801–1851. arXiv:math/0702004. doi:10.1016/j.aim.2008.07.008. ISSN 0001-8708. S2CID 5974912.
  3. ^ Large Networks and Graph Limits. American Mathematical Society. p. 297. Retrieved 2022-01-13.
  4. ^ Sidorenko, A. F. (1992). "Inequalities for functionals generated by bipartite graphs". Discrete Mathematics and Applications. 2 (5). doi:10.1515/dma.1992.2.5.489. ISSN 0924-9265. S2CID 117471984.
  5. ^ Large Networks and Graph Limits. American Mathematical Society. p. 299. Retrieved 2022-01-13.
  6. ^ Large Networks and Graph Limits. American Mathematical Society. p. 298. Retrieved 2022-01-13.
  7. ^ Thomason, Andrew (1989). "A Disproof of a Conjecture of Erdős in Ramsey Theory". Journal of the London Mathematical Society. s2-39 (2): 246–255. doi:10.1112/jlms/s2-39.2.246. ISSN 1469-7750.
  8. ^ Lovász, László (2012). Large Networks and Graph Limits. United States: American Mathematical Society Colloquium publications. pp. 297–298. ISBN 978-0821890851.
  9. ^ Goodman, A. W. (1959). "On Sets of Acquaintances and Strangers at any Party". The American Mathematical Monthly. 66 (9): 778–783. doi:10.2307/2310464. ISSN 0002-9890. JSTOR 2310464.
Retrieved from "https://enwiki.freddythechick.net/index.php?title=Common_graph&oldid=4993656"