Common graph

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

A graph ${\displaystyle F}$ is common if the inequality:

$\displaystyle t(F,W)+t(F,1-W)\geq 2^{-e(F)+1}}$

holds for any graphon${\displaystyle W}$, where ${\displaystyle e(F)}$ is the number of edges of ${\displaystyle F}$ and ${\displaystyle t(F,W)}$ is the homomorphism density.^[1]

The inequality is tight because the lower bound is always reached when ${\displaystyle W}$ is the constant graphon ${\displaystyle W\equiv 1/2}$.

For a graph ${\displaystyle G}$, we have ${\displaystyle t(F,G)=t(F,W_{G})}$ and ${\displaystyle t(F,{\overline {G}})=t(F,1-W_{G})}$ for the associated graphon${\displaystyle W_{G}}$, since graphon associated to the complement ${\displaystyle {\overline {G}}}$ is ${\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]${\displaystyle W}$ to ${\displaystyle W_{G}}$, and see ${\displaystyle t(F,W)}$ as roughly the fraction of labeled copies of graph ${\displaystyle F}$ in "approximate" graph ${\displaystyle G}$. Then, we can assume the quantity ${\displaystyle t(F,W)+t(F,1-W)}$ is roughly ${\displaystyle t(F,G)+t(F,{\overline {G}})}$ and interpret the latter as the combined number of copies of ${\displaystyle F}$ in ${\displaystyle G}$ and ${\displaystyle {\overline {G}}}$. Hence, we see that ${\displaystyle t(F,G)+t(F,{\overline {G}})\gtrsim 2^{-e(F)+1}}$ holds. This, in turn, means that common graph ${\displaystyle 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 ${\displaystyle 2^{-e(F)+1}}$ fraction of all possible copies of ${\displaystyle F}$ are monochromatic. Note that in a Erdős–Rényi random graph${\displaystyle G=G(n,p)}$ with each edge drawn with probability ${\displaystyle p=1/2}$, each graph homomorphism from ${\displaystyle F}$ to ${\displaystyle G}$ have probability ${\displaystyle 2\cdot 2^{-e(F)}=2^{-e(F)+1}}$of being monochromatic. So, common graph ${\displaystyle F}$ is a graph where it attains its minimum number of appearance as a monochromatic subgraph of graph ${\displaystyle G}$ at the graph ${\displaystyle G=G(n,p)}$ with ${\displaystyle p=1/2}$

${\displaystyle p=1/2}$. The above definition using the generalized homomorphism density can be understood in this way.

• 上記のように、すべてのシドレンコグラフは共通グラフです。^{[ 3 ]}したがって、既知のシドレンコグラフはすべて共通グラフの例であり、特に偶数長のサイクルは共通です。^{[ 4 ]}ただし、すべてのシドレンコグラフは二部グラフであるのに対し、以下に示すように二部グラフではない共通グラフも存在するため、これらは限られた例です。
• 三角形のグラフ${\displaystyle K_{3}}$これは、非二部グラフの一般的な例の1つです。^{[ 5 ]}
• ${\displaystyle K_{4}^{-}}$4つの頂点を持つ完全グラフから辺を1つ取り除いて得られるグラフ${\displaystyle K_{4}}$は一般的である。^{[ 6 ]}
• 非例: かつてはすべてのグラフは共通であると考えられていた。しかし、実際には${\displaystyle K_{t}}$一般的ではない$t ≥ 4$[ ^{7 ]}特に^、${\displaystyle K_{4}}$一般的ではないが、${\displaystyle K_{4}^{-}}$よくあることだ。

• シドレンコの推測