Common graph

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking, F is a common graph if it "commonly" appears as a subgraph, in a sense that the total number of copies of F in any graph G and its complement \overline{G} is a large fraction of all possible copies of F on the same vertices. Intuitively, if G contains few copies of F , then its complement \overline{G} must contain lots of copies of F 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.

In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking, F is a common graph if it "commonly" appears as a subgraph, in a sense that the total number of copies of F in any graph G and its complement \overline{G} is a large fraction of all possible copies of F on the same vertices. Intuitively, if G contains few copies of F , then its complement \overline{G} must contain lots of copies of F 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. For a graph G , we have t(F, G) = t(F, W_{G}) and t(F, \overline{G})=t(F, 1 - W_G) for the associated graphon W_G , since graphon associated to the complement \overline{G} is 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, W to W_G , and see t(F, W) as roughly the fraction of labeled copies of graph F in "approximate" graph G . Then, we can assume the quantity t(F, W) + t(F, 1 - W) is roughly t(F, G) + t(F, \overline{G}) and interpret the latter as the combined number of copies of F in G and \overline{G} . Hence, we see that t(F, G) + t(F, \overline{G}) \gtrsim 2^{-e(F)+1} holds. This, in turn, means that common graph F 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 2^{-e(F)+1} fraction of all possible copies of F are monochromatic. Note that in a Erdős–Rényi random graph G = G(n, p) with each edge drawn with probability p=1/2 , each graph homomorphism from F to G have probability 2 \cdot 2^{-e(F)} = 2^ {-e(F) +1} of being monochromatic.

So, common graph F is a graph where it attains its minimum number of appearance as a monochromatic subgraph of graph G at the graph G=G(n, p) with p=1/2 p=1/2 . The above definition using the generalized homomorphism density can be understood in this way.

Sidorenko graphs are common

A graph F is a Sidorenko graph if it satisfies t(F, W) \ge t(K_2, W)^{e(F)} for all graphons W . In that case, t(F, 1 - W) \ge t(K_2, 1 - W)^{e(F)} . Furthermore, 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 f(x) = x^{e(F)} : 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.

The triangle graph is common

Expand the integral expression for t(K_3, 1 - W) and take into account the symmetry between the variables: \int_{[0, 1]^3} (1 - W(x, y))(1 - W(y, z))(1 - W(z, x)) dx dy dz \int{[0, 1]^3} W(x, y) W(x, z) dx dy dz = t(K_{1, 2}, W) \int_{[0, 1]^3} W(x, y) W(y, z) W(z, x) dx dy dz = t(K_3, W) where K_{1, 2} denotes the complete bipartite graph on 1 vertex on one part and 2 vertices on the other.

It follows: t(K_3, W) + t(K_3, 1 - W) = 1 - 3 t(K_2, W) + 3 t(K_{1, 2}, W) . t(K_{1, 2}, W) can be related to t(K_2, W) thanks to the symmetry between the variables y and z : \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: 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"

Text derived from https://en.wikipedia.org/w/index.php?oldid=1292431244 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.