Общий график

В теории графов , области математики, общие графы принадлежат к разделу экстремальной теории графов, касающемуся неравенств в плотностях гомоморфизма . Грубо говоря, $F$ является общим графом , если он «обычно» появляется как подграф, в том смысле, что общее количество копий графа $F$ в любом графике $G$ и его дополнение ${\overline {G}}$ представляет собой большую часть всех возможных копий $F$ на тех же вершинах. Интуитивно, если $G$ содержит мало копий $F$, то его дополнение ${\overline {G}}$ должно содержать большое количество копий $F$ чтобы компенсировать это.

Общие графы тесно связаны с другими понятиями графов, связанными с неравенствами плотности гомоморфизма. Например, общие графы — это более общий случай графов Сидоренко .

Определение

График $F$ является общим, если неравенство:

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

справедливо для любого графона $W$, где $e(F)$ это количество ребер $F$ и $t(F,W)$ – плотность гомоморфизма .

Неравенство строгое, поскольку нижняя граница всегда достигается, когда $W$ это постоянный графон $W\equiv 1/2$.

Интерпретации определения

Для графика $G$, у нас есть $t(F,G)=t(F,W_{G})$ и $t(F,{\overline {G}})=t(F,1-W_{G})$ для связанного графона $W_{G}$, поскольку графон связан с дополнением ${\overline {G}}$ является $W_{\overline {G}}=1-W_{G}$. Следовательно, эта формула дает нам очень неформальную интуицию, позволяющую сделать достаточно близкое приближение, что бы это ни значило: $W$ к $W_{G}$и посмотреть $t(F,W)$ примерно как доля помеченных копий графика $F$ в "приблизительном" графике $G$. Тогда мы можем принять величину $t(F,W)+t(F,1-W)$ примерно $t(F,G)+t(F,{\overline {G}})$ и интерпретировать последнее как совокупное количество копий $F$ в $G$ и ${\overline {G}}$. Следовательно, мы видим, что $t(F,G)+t(F,{\overline {G}})\gtrsim 2^{-e(F)+1}$ держит. Это, в свою очередь, означает, что общий граф $F$ обычно появляется как подграф.

Другими словами, если мы будем думать о ребрах и неребрах как о 2-раскраске ребер полного графа в одних и тех же вершинах, то по крайней мере $2^{-e(F)+1}$ часть всех возможных копий $F$ являются однотонными. Обратите внимание, что в случайном графе Эрдеша–Реньи $G=G(n,p)$ где каждое ребро нарисовано с вероятностью $p=1/2$, каждый гомоморфизм графа из $F$ к $G$ иметь вероятность $2\cdot 2^{-e(F)}=2^{-e(F)+1}$быть монохромным. Итак, общий график $F$ - это граф, в котором он достигает минимального количества появлений как монохроматический подграф графа $G$ на графике $G=G(n,p)$ с $p=1/2$

$p=1/2$. Приведенное выше определение с использованием плотности обобщенного гомоморфизма можно понять таким образом.

Примеры

• Как говорилось выше, все графы Сидоренко являются обычными графами. Следовательно, любой известный граф Сидоренко является примером обычного графа, и, что особенно важно, циклы четной длины . часто встречаются Однако это ограниченные примеры, поскольку все графы Сидоренко являются двудольными графами, хотя существуют недвудольные общие графы, как показано ниже.
• Треугольный график $K_{3}$ является одним простым примером недвудольного общего графа.
• $K_{4}^{-}$, граф, полученный удалением ребра полного графа на 4 вершинах $K_{4}$, является обычным явлением.
• Непример: какое-то время считалось, что все графики являются общими. Однако оказывается, что $K_{t}$ не является обычным для $t\geq 4$. В частности, $K_{4}$ не является распространенным, хотя $K_{4}^{-}$ является общим.

Доказательства

Графики Сидоренко распространены

График $F$ является графом Сидоренко, если он удовлетворяет условию $t(F,W)\geq t(K_{2},W)^{e(F)}$ для всех графонов $W$.

В этом случае $t(F,1-W)\geq t(K_{2},1-W)^{e(F)}$. Более того, $t(K_{2},W)+t(K_{2},1-W)=1$, что следует из определения плотности гомоморфизма. Объединив это с неравенством Йенсена для функции $f(x)=x^{e(F)}$:

$t(F,W)+t(F,1-W)\geq t(K_{2},W)^{e(F)}+t(K_{2},1-W)^{e(F)}\geq 2{\bigg (}{\frac {t(K_{2},W)+t(K_{2},1-W)}{2}}{\bigg )}^{e(F)}=2^{-e(F)+1}$

Таким образом, условия общего графа соблюдены.

Треугольный график распространен

Разверните интегральное выражение для $t(K_{3},1-W)$ и учтем симметрию между переменными:

$\int _{[0,1]^{3}}(1-W(x,y))(1-W(y,z))(1-W(z,x))dxdydz=1-3\int _{[0,1]^{2}}W(x,y)+3\int _{[0,1]^{3}}W(x,y)W(x,z)dxdydz-\int _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz$

Каждый член выражения можно записать через плотности гомоморфизма меньших графов. По определению плотностей гомоморфизма:

$\int _{[0,1]^{2}}W(x,y)dxdy=t(K_{2},W)$

$\int {[0,1]^{3}}W(x,y)W(x,z)dxdydz=t(K_{1,2},W)$

$\int _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz=t(K_{3},W)$

где $K_{1,2}$ обозначает полный двудольный граф на $1$ вершина на одной части и $2$ вершины с другой. Отсюда следует:

$t(K_{3},W)+t(K_{3},1-W)=1-3t(K_{2},W)+3t(K_{1,2},W)$.

$t(K_{1,2},W)$ может быть связано с $t(K_{2},W)$ благодаря симметрии между переменными $y$ и $z$: $${\begin{alignedat}{4}t(K_{1,2},W)&=\int _{[0,1]^{3}}W(x,y)W(x,z)dxdydz&&\\&=\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}&&\\&\geq {\bigg (}\int _{x\in [0,1]}\int _{y\in [0,1]}W(x,y){\bigg )}^{2}=t(K_{2},W)^{2}\end{alignedat}}$$

где последний шаг следует из интегрального неравенства Коши–Шварца . Окончательно:

$t(K_{3},W)+t(K_{3},1-W)\geq 1-3t(K_{2},W)+3t(K_{2},W)^{2}=1/4+3{\big (}t(K_{2},W)-1/2{\big )}^{2}\geq 1/4$.

Это доказательство можно получить, взяв непрерывный аналог теоремы 1 из книги «О группах знакомых и незнакомцев на любой вечеринке».

См. также

• Гипотеза Сидоренко