Графон

Реализация сменного случайного графа, определяемого графоном . Графон показан в виде пурпурной тепловой карты (внизу справа). Случайный график размера $n$ генерируется путем независимого присвоения каждой вершине $k\in \{1,\dotsc ,n\}$ скрытая случайная величина $U_{k}\sim \mathrm {U} (0,1)$ (значения вдоль вертикальной оси) и включая каждое ребро $(k,\ell )$ независимо с вероятностью $f(U_{k},U_{\ell })$. Например, край $(3,5)$ (зеленый, пунктирный) присутствует с вероятностью $f(0.72,0.9)$; зеленые прямоугольники в правом квадрате представляют значения $(u_{3},u_{5})$ и $(u_{5},u_{3})$. На верхней левой панели показана реализация графа в виде матрицы смежности.

В теории графов и статистике графон . (также известный как предел графа ) — это симметричная измеримая функция $W:[0,1]^{2}\to [0,1]$, что важно при изучении плотных графов . Графоны возникают как естественное понятие предела последовательности плотных графов, так и как фундаментальные определяющие объекты моделей сменных случайных графов. Графоны привязаны к плотным графам следующей парой наблюдений: модели случайных графов, определенные графонами, почти наверняка приводят к плотным графам , и, по лемме о регулярности , графоны захватывают структуру произвольных больших плотных графов.

формулировка

Графон — симметричная измеримая функция $W:[0,1]^{2}\to [0,1]$. Обычно под графоном понимают модель сменного случайного графа по следующей схеме:

1. Каждая вершина $j$ графа присваивается независимая случайная величина $u_{j}\sim U[0,1]$
2. Край $(i,j)$ самостоятельно включается в граф с вероятностью $W(u_{i},u_{j})$.

Модель случайного графа является сменной моделью случайного графа тогда и только тогда, когда ее можно таким образом определить в терминах (возможно, случайного) графона.Модель на основе фиксированного графона $W$ иногда обозначается $\mathbb {G} (n,W)$,по аналогии с Эрдеша–Реньи моделью случайных графов .Граф, созданный из графона $W$ таким образом называется $W$-случайный график.

Из этого определения и закона больших чисел следует, что если $W\neq 0$модели сменных случайных графов почти наверняка плотны.

Примеры

Простейший пример графона: $W(x,y)\equiv p$ для некоторой константы $p\in [0,1]$. В этом случае связанной моделью сменных случайных графов является Эрдеша – Реньи. модель $G(n,p)$ который включает каждое ребро независимо с вероятностью $p$.

Если вместо этого мы начнем с графона, который является кусочно-постоянным по формуле:

1. деление единичного квадрата на $k\times k$ блоки и
2. параметр $W$ равный $p_{lm}$ на $(\ell ,m)^{\text{th}}$ блокировать,

результирующая модель сменного случайного графа представляет собой $k$ сообщества стохастическая блочная модель , обобщение модели Эрдеша – Реньи.Мы можем интерпретировать это как модель случайного графа, состоящую из $k$ отдельные графы Эрдеша – Реньи с параметрами $p_{\ell \ell }$ соответственно, с биграфами между ними, где каждое возможное ребро между блоками $(\ell ,\ell )$ и $(m,m)$ включается независимо с вероятностью $p_{\ell m}$.

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

смежности

Случайный график размера $n$ можно представить как случайное $n\times n$ матрица смежности . Чтобы обеспечить согласованность (в смысле проективности ) между случайными графами разных размеров, естественно изучить последовательность матриц смежности, возникающую как верхний левый $n\times n$ подматрицы некоторого бесконечного массива случайных величин; это позволяет нам генерировать $G_{n}$ добавив узел в $G_{n-1}$ и выборка краев $(j,n)$ для $j<n$. С этой точки зрения случайные графы определяются как случайные бесконечные симметричные массивы. $(X_{ij})$.

Учитывая фундаментальную важность сменных последовательностей в классической теории вероятностей, естественно искать аналогичное понятие в случае случайного графа. Одно из таких понятий дается совместно заменяемыми матрицами; т.е. случайные матрицы, удовлетворяющие

$(X_{ij})\ {\overset {d}{=}}\,(X_{\sigma (i)\sigma (j)})$

для всех перестановок $\sigma$ натуральных чисел, где ${\overset {d}{=}}$ означает равное распределение . Интуитивно это условие означает, что распределение случайного графа не меняется при перемаркировке его вершин: то есть метки вершин не несут никакой информации.

Существует теорема о представлении совместно заменяемых матриц смежности, аналогичная теореме де Финетти о представлении заменяемых последовательностей. Это частный случай теоремы Олдоса – Гувера для совместно заменяемых массивов, и в этом случае он утверждает, что случайная матрица $(X_{ij})$ генерируется:

1. Образец $u_{j}\sim U[0,1]$ независимо
2. $X_{ij}=X_{ji}=1$ независимо случайно с вероятностью $W(u_{i},u_{j}),$

где $W:[0,1]^{2}\to [0,1]$ — это (возможно, случайный) графон. То есть модель случайного графа имеет совместно заменяемую матрицу смежности тогда и только тогда, когда она является совместно заменяемой моделью случайного графа, определенной в терминах некоторого графона.

Оценка графона

Из-за проблем с идентификацией невозможно оценить ни функцию графона, ни $W$ или скрытые позиции узла $u_{i},$ и существует два основных направления оценки графонов. Одно направление направлено на оценку $W$до класса эквивалентности, или оценить матрицу вероятностей, индуцированную $W$.

формулировка

Любой график на $n$ вершины $\{1,2,\dots ,n\}$ можно отождествить с его матрицей смежности $A_{G}$.Эта матрица соответствует ступенчатой ​​функции $W_{G}:[0,1]^{2}\to [0,1]$,определяется путем разделения $[0,1]$ на интервалы $I_{1},I_{2},\dots ,I_{n}$ такой, что $I_{j}$ имеет интерьер

$$\left({\frac {j-1}{n}},{\frac {j}{n}}\right)$$

и для каждого $(x,y)\in I_{i}\times I_{j}$, параметр $W_{G}(x,y)$ равный $(i,j)^{\text{th}}$запись $A_{G}$.Эта функция $W_{G}$ является ассоциированным графоном графа $G$.

В общем случае, если у нас есть последовательность графов $(G_{n})$ где количество вершин $G_{n}$ стремится к бесконечности, мы можем проанализировать предельное поведение последовательности, рассматривая предельное поведение функций $(W_{G_{n}})$. Если эти графики сходятся (согласно некоторому подходящему определению сходимости ), то мы ожидаем, что предел этих графиков будет соответствовать пределу этих связанных функций.

Это мотивирует определение графона (сокращение от «график-функция») как симметричной измеримой функции. $W:[0,1]^{2}\to [0,1]$ который отражает понятие предела последовательности графов. Оказывается, что для последовательностей плотных графов несколько, казалось бы, различных понятий сходимости эквивалентны, и для всех них естественным предельным объектом является графон.

Примеры

Возьмите последовательность $(G_{n})$ Случайные графы Эрдеша – Реньи $G_{n}=G(n,p)$ с некоторым фиксированным параметром $p$.Интуитивно, как $n$ стремится к бесконечности, предел этой последовательности графов определяется исключительно плотностью ребер этих графов.В пространстве графонов оказывается, что такая последовательность почти наверняка сходится к константе $W(x,y)\equiv p$, что отражает вышеизложенную интуицию.

Полуграфон

Возьмите последовательность $(H_{n})$ полуграфиков , определяемых взятием $H_{n}$ быть двудольным графом на $2n$ вершины $u_{1},u_{2},\dots ,u_{n}$ и $v_{1},v_{2},\dots ,v_{n}$ такой, что $u_{i}$ находится рядом с $v_{j}$ именно тогда, когда $i\leq j$. Если вершины перечислены в представленном порядке, томатрица смежности $A_{H_{n}}$ имеет два угла блочных матриц «полуквадрата», заполненных единицами, а остальные элементы равны нулю. Например, матрица смежности $H_{3}$ дается

$${\begin{bmatrix}0&0&0&1&1&1\\0&0&0&0&1&1\\0&0&0&0&0&1\\1&0&0&0&0&0\\1&1&0&0&0&0\\1&1&1&0&0&0\end{bmatrix}}.$$

Как $n$ становится большим, эти углы «сглаживаются».В соответствии с этой интуицией последовательность $(H_{n})$ сходится к полуграфону $W$ определяется $W(x,y)=1$ когда $|x-y|\geq 1/2$ и $W(x,y)=0$ в противном случае.

Полный двудольный графон

Возьмите последовательность $(K_{n,n})$ полных двудольных графов с частями одинакового размера.Если мы упорядочим вершины, поместив все вершины в одну часть в началеи поместив вершины другой части в конец, матрица смежности $(K_{n,n})$ выглядит как блочная недиагональная матрица с двумя блоками единиц и двумя блоками нулей.Например, матрица смежности $K_{2,2}$ дается

$${\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}.$$

Как $n$ становится больше, эта блочная структура матрицы смежности остается постоянной, так что эта последовательность графов сходится к «полному двудольному» графону $W$определяется $W(x,y)=1$ в любое время $\min(x,y)\leq 1/2$ и $\max(x,y)>1/2$и настройка $W(x,y)=0$ в противном случае.

Если вместо этого мы упорядочим вершины $K_{n,n}$ чередуя части,Матрица смежности имеет шахматную структуру из нулей и единиц.Например, при таком порядке матрица смежности $K_{2,2}$ дается

$${\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}.$$

Как $n$ становится больше, матрицы смежности становятся все более тонкой шахматной доской.Несмотря на такое поведение, нам все равно нужен предел $(K_{n,n})$ быть уникальным и привести к графону из примера 3.Это означает, что когда мы формально определяем сходимость последовательности графов, определение предела не должно зависеть от перемаркировки вершин.

Предел W

Возьмите случайную последовательность $(G_{n})$ из $W$-случайные графики путем рисования $G_{n}\sim \mathbb {G} (n,W)$ для какого-то фиксированного графона $W$.Тогда так же, как и в первом примере из этого раздела, получается, что $(G_{n})$ сходится к $W$ почти наверняка.

Восстановление параметров графа из графонов

Данный график $G$ со связанным графоном $W=W_{G}$, мы можем восстановить теоретико-графовые свойства и параметры $G$ путем интеграции преобразований $W$. Например, плотность ребер (т.е. средняя степень, деленная на количество вершин) $G$ определяется интегралом

$$\int _{0}^{1}\int _{0}^{1}W(x,y)\;\mathrm {d} x\,\mathrm {d} y.$$

Это потому, что $W$ является $\{0,1\}$-значно, и каждое ребро $(i,j)$в $G$ соответствует региону $I_{i}\times I_{j}$площади $1/n^{2}$ где $W$ равно $1$.

Аналогичные рассуждения показывают, что плотность треугольников в $G$ равно

$${\frac {1}{6}}\int _{0}^{1}\int _{0}^{1}\int _{0}^{1}W(x,y)W(y,z)W(z,x)\;\mathrm {d} x\,\mathrm {d} y\,\mathrm {d} z.$$

Понятия конвергенции

Существует много разных способов измерения расстояния между двумя графиками.Если нас интересуют метрики , «сохраняющие» экстремальные свойства графов,тогда нам следует ограничить наше внимание метриками, которые идентифицируют случайные графы как схожие.Например, если мы случайным образом нарисуем два графика независимо от модели Эрдеша – Реньи. $G(n,p)$ для некоторых фиксированных $p$, расстояние между этими двумя графиками при «разумной» метрике должно быть с высокой вероятностью близко к нулю для больших $n$.

Наивно, учитывая два графа в одном и том же наборе вершин, можно было бы определить их расстояние как количество ребер, которые необходимо добавить или удалить, чтобы перейти от одного графа к другому, то есть их расстояние редактирования . Однако расстояние редактирования не идентифицирует случайные графики как похожие; фактически, два графика, построенные независимо от $G(n,{\tfrac {1}{2}})$ иметь ожидаемое (нормализованное) расстояние редактирования ${\tfrac {1}{2}}$.

Есть две естественные метрики, которые хорошо ведут себя на плотных случайных графах в том смысле, в котором мы хотим.Первый — это метрика выборки, которая говорит, что два графа близки, если их распределения подграфов близки.Второй — это метрика несоответствия ребер , которая говорит, что два графа близки, когда плотность их ребер близка на всех соответствующих подмножествах вершин.

Чудесным образом последовательность графов сходится относительно одной метрики именно тогда, когда она сходится относительно другой.При этом предельные объекты по обеим метрикам оказываются графонами.Эквивалентность этих двух понятий сходимости отражает различных понятий квазислучайных графов. эквивалентность

Плотности

Один из способов измерения расстояния между двумя графиками $G$ и $H$ заключается в сравнении их относительного количества подграфов.То есть для каждого графика $F$ мы можем сравнить количество копий $F$ в $G$ и $F$ в $H$.Если эти числа близки для каждого графа $F$, затеминтуитивно $G$ и $H$ похожие графики.Однако вместо того, чтобы иметь дело непосредственно с подграфами, оказывается, чтопроще работать с гомоморфизмами графов.Это нормально при работе с большими плотными графами, поскольку в этом сценарии количество подграфов и количество гомоморфизмов графов фиксированного графа асимптотически равны.

Учитывая два графика $F$ и $G$, плотность гомоморфизма $t(F,G)$ из $F$ в $G$ определяется как количество гомоморфизмов графов из $F$ к $G$.Другими словами, $t(F,G)$ — вероятность случайно выбранной карты из вершин $F$ к вершинам $G$ отправляет соседние вершины в $F$ к соседним вершинам в $G$.

Графоны предлагают простой способ вычисления плотности гомоморфизма.Действительно, учитывая график $G$ со связанным графоном $W_{G}$ и еще один $F$, у нас есть

$$t(F,G)=\int \prod _{(i,j)\in E(F)}W_{G}(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}$$

где интеграл многомерен, взят по единичному гиперкубу $[0,1]^{V(F)}$.Это следует из определения ассоциированного графона, учитывая, что указанное выше подынтегральное выражение равно $1$.Затем мы можем распространить определение плотности гомоморфизма на произвольные графоны. $W$, используя тот же интеграл и определяя

$$t(F,W)=\int \prod _{(i,j)\in E(F)}W(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}$$

для любого графика $F$.

Учитывая эту настройку, мы говорим, что последовательность графов $(G_{n})$ сходится слева, если для любого фиксированного графа $F$, последовательность плотностей гомоморфизма $\left(t(F,G_{n})\right)$ сходится.Хотя это и не очевидно из самого определения, если $(G_{n})$ сходится в этом смысле, то всегда существует графон $W$ такой, что для каждого графа $F$, у нас есть

$$\lim _{n\to \infty }t(F,G_{n})=t(F,W)$$

одновременно.

Расстояние обрезки

Возьмите два графика $G$ и $H$ на том же множестве вершин.Поскольку эти графы имеют одни и те же вершины,один из способов измерить их расстояние — ограничиться подмножествами $X,Y$ множества вершин и для каждой такой пары подмножеств сравниваем количество ребер $e_{G}(X,Y)$ от $X$ к $Y$ в $G$ по количеству ребер $e_{H}(X,Y)$ между $X$ и $Y$ в $H$. Если эти числа одинаковы для каждой пары подмножеств (относительно общего числа вершин), то это предполагает $G$ и $H$ похожие графики.

В качестве предварительной формализации понятия расстояния для любой пары графов $G$ и $H$ на том же наборе вершин $V$ размера $|V|=n$, определите обозначенное расстояние разреза между $G$ и $H$ быть

$$d_{\square }(G,H)={\frac {1}{n^{2}}}\max _{X,Y\subseteq V}\left|e_{G}(X,Y)-e_{H}(X,Y)\right|.$$

Другими словами, обозначенное расстояние разреза кодирует максимальное несоответствие плотностей краев между $G$ и $H$.Мы можем обобщить эту концепцию на графоны, выразив плотность ребер ${\tfrac {1}{n^{2}}}e_{G}(X,Y)$ с точки зрения связанного графона $W_{G}$, давая равенство

$$d_{\square }(G,H)=\max _{X,Y\subseteq V}\left|\int _{I_{X}}\int _{I_{Y}}W_{G}(x,y)-W_{H}(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|$$

где $I_{X},I_{Y}\subseteq [0,1]$ являются объединениями интервалов, соответствующих вершинам в $X$ и $Y$. Обратите внимание, что это определение все еще можно использовать, даже если сравниваемые графы не имеют общего набора вершин.Это мотивирует следующее более общее определение.

Определение 1. Для любой симметричной измеримой функции $f:[0,1]^{2}\to \mathbb {R}$, определим разреза норму $f$ быть количеством

$$\lVert f\rVert _{\square }=\sup _{S,T\subseteq [0,1]}\left|\int _{S}\int _{T}f(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|$$

взяты все измеримые подмножества $S,T$ единичного интервала.

Это отражает наше более раннее представление о помеченном расстоянии отреза, поскольку мы имеем равенство $\lVert W_{G}-W_{H}\rVert _{\square }=d_{\square }(G,H)$.

У этой меры расстояния все еще есть одно серьезное ограничение: она может присваивать ненулевое расстояние двум изоморфным графам.Чтобы убедиться, что изоморфные графы имеют нулевое расстояние, мы должны вычислить минимальную норму разреза для всех возможных «перемаркировок» вершин.Это мотивирует следующее определение расстояния отреза.

Определение 2. Для любой пары графонов $U$ и $W$, определите расстояние их разреза как

$$\delta _{\square }(U,W)=\inf _{\varphi }\lVert U-W^{\varphi }\rVert _{\square }$$

где $W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))$ это состав $W$ с картой $\varphi$, а нижняя грань берется по всем сохраняющим меру биекциям из единичного интервала в себя.

Расстояние разреза между двумя графами определяется как расстояние разреза между связанными с ними графонами.

Теперь мы говорим, что последовательность графов $(G_{n})$ сходится под разрезом, если это последовательность Коши под разрезом $\delta _{\square }$. Хотя это и не является прямым следствием определения, если такая последовательность графов является Коши, то она всегда сходится к некоторому графону $W$.

Эквивалентность конвергенции

Оказывается, для любой последовательности графов $(G_{n})$, левая сходимость эквивалентна сходимости по разрезному расстоянию, и, кроме того, предельный графон $W$ то же самое. Мы также можем рассмотреть конвергенцию самих графонов, используя те же определения, и справедлива та же эквивалентность. Фактически, оба понятия сходимости более тесно связаны через так называемые леммы о подсчете .

Счетная лемма. Для любой пары графонов $U$ и $W$, у нас есть

$$|t(F,U)-t(F,W)|\leq e(F)\delta _{\square }(U,W)$$

для всех графиков $F$.

Название «лемма о подсчете» происходит от оценок, которые эта лемма дает для плотностей гомоморфизма. $t(F,W)$, которые аналогичны подсчету подграфов графов. Эта лемма является обобщением леммы о подсчете графов , которая появляется в области регулярности разбиений , и сразу показывает, что сходимость под расстоянием разреза влечет за собой сходимость слева.

Обратная лемма о счете. Для каждого действительного числа $\varepsilon >0$, существует действительное число $\eta >0$ и положительное целое число $k$ такая, что для любой пары графонов $U$ и $W$ с

$$|t(F,U)-t(F,W)|\leq \eta$$

для всех графиков $F$ удовлетворяющий $v(F)\leq k$,мы должны иметь $\delta _{\square }(U,W)<\varepsilon$.

Эта лемма показывает, что левая сходимость влечет за собой сходимость на расстоянии разреза.

Пространство графонов

Мы можем превратить расстояние разреза в метрику, взяв набор всех графонов и идентифицировав два графона. $U\sim W$ в любое время $\delta _{\square }(U,W)=0$.Полученное пространство графонов обозначим ${\widetilde {\mathcal {W}}}_{0}$, и вместе с $\delta _{\square }$ образует метрическое пространство .

Это пространство оказывается компактным .Более того, он содержит множество всех конечных графов, представленных связанными с ними графонами, в виде плотного подмножества .Эти наблюдения показывают, что пространство графонов является пополнением пространства графов относительно расстояния разреза. Одним из непосредственных последствий этого является следующее.

Следствие 1. Для любого действительного числа $\varepsilon >0$, существует целое число $N$ такой, что для каждого графона $W$, есть график $G$ с максимум $N$ вершины такие, что $\delta _{\square }(W,W_{G})<\varepsilon$.

Чтобы понять, почему, позвольте ${\mathcal {G}}$ быть множеством графов. Рассмотрим для каждого графа $G\in {\mathcal {G}}$ открытый шар $B_{\square }(G,\varepsilon )$ содержащий все графоны $W$ такой, что $\delta _{\square }(W,W_{G})<\varepsilon$. Множество открытых шаров для всех графов покрывает ${\widetilde {\mathcal {W}}}_{0}$, поэтому из компактности следует, что существует конечное подпокрытие $\{B_{\square }(G,\varepsilon )\mid G\in {\mathcal {G}}_{0}\}$ для некоторого конечного подмножества ${\mathcal {G}}_{0}\subset {\mathcal {G}}$. Теперь мы можем взять $N$ быть наибольшим числом вершин среди графов в ${\mathcal {G}}_{0}$.

Приложения

Лемма

Компактность пространства графонов $({\widetilde {\mathcal {W}}}_{0},\delta _{\square })$ можно рассматривать как аналитическую формулировку леммы Семереди о регулярности ; на самом деле это более сильный результат, чем исходная лемма. Лемму Семереди о регулярности можно перевести на язык графонов следующим образом. Определите ступенчатую функцию как графон $W$ то есть кусочно-постоянно, т.е. для некоторого разбиения ${\mathcal {P}}$ из $[0,1]$, $W$ постоянно включен $S\times T$ для всех $S,T\in {\mathcal {P}}$. Утверждение о том, что граф $G$ имеет разбиение по регулярности, это эквивалентно утверждению, что связанный с ним графон $W_{G}$ близка к ступенчатой ​​функции.

Для доказательства компактности требуется только лемма о слабой регулярности :

Лемма о слабой регулярности для графонов. Для каждого графона $W$ и $\varepsilon >0$, есть ступенчатая функция $W'$ с максимум $\lceil 4^{1/\varepsilon ^{2}}\rceil$ шаги такие, что $\lVert W-W'\rVert _{\square }\leq \varepsilon$.

но его можно использовать для доказательства более сильных результатов о регулярности, таких как лемма о сильной регулярности :

Лемма о сильной регулярности для графонов. Для каждой последовательности $\mathbf {\varepsilon } =(\varepsilon _{0},\varepsilon _{1},\dots )$ положительных действительных чисел существует целое положительное число $S$ такой, что для каждого графона $W$, есть графон $W'$ и ступенчатая функция $U$ с $k<S$ шаги такие, что $\lVert W-W'\rVert _{1}\leq \varepsilon _{0}$ и $\lVert W'-U\rVert _{\square }\leq \varepsilon _{k}.$

Доказательство леммы о сильной регулярности по своей сути аналогично следствию 1, приведенному выше. Оказывается, каждый графон $W$ можно аппроксимировать ступенчатой ​​функцией $U$ в $L_{1}$ норма , показывающая, что набор шаров $B_{1}(U,\varepsilon _{0})$ крышка ${\widetilde {\mathcal {W}}}_{0}$. Эти наборы не открыты в $\delta _{\square }$ метрические, но их можно немного увеличить, чтобы они были открытыми. Теперь мы можем взять конечное подпокрытие и показать, что требуемое условие следует.

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

Основная статья: гипотеза Сидоренко

Аналитическая природа графонов обеспечивает большую гибкость при рассмотрении неравенств, связанных с гомоморфизмами.

Например, гипотеза Сидоренко является основной открытой проблемой экстремальной теории графов , которая утверждает, что для любого графа $G$ на $n$ вершины средней степени $pn$ (для некоторых $p\in [0,1]$) и двудольный граф $H$ на $v$ вершины и $e$ ребер, число гомоморфизмов из $H$ к $G$ по крайней мере $p^{e}n^{v}$. Поскольку эта величина представляет собой ожидаемое количество помеченных подграфов $H$ в случайном графике $G(n,p)$,гипотезу можно интерпретировать как утверждение что для любого двудольного графа $H$, случайный граф достигает (в ожидании) минимального количества копий $H$ по всем графам с некоторой фиксированной плотностью ребер.

Многие подходы к гипотезе Сидоренко формулируют проблему как интегральное неравенство на графонах, что затем позволяет решить проблему, используя другие аналитические подходы.

Обобщения

Графоны естественным образом ассоциируются с плотными простыми графами. Существуют расширения этой модели для плотных ориентированных взвешенных графов, часто называемых декорированными графонами. Существуют также недавние расширения режима разреженных графов как с точки зрения моделей случайных графов, так и с точки зрения моделей случайных графов. и теория предела графов.