Независимые множества в случайных графах пересечений: различия между версиями

'''Определение 1 (равномерные случайные графы пересечений)'''. Рассмотрим совокупность элементов <math>M = \{1, 2, ..., m \}</math> и множество вершин <math>V = \{ v_1, v_2, ..., v_n \} </math>. Если каждой вершине <math>v_j, j = 1, 2, ..., n</math> независимым образом присвоить подмножество <math>S_{v_j}</math> множества M посредством независимого выбора каждого элемента с вероятностью p и проложить ребро между двумя вершинами <math>v_{j_1}, v_{j_2}</math> в том и только том случае, если <math>S_{v_{j_1}} \cap S_{v_{j_2}} \ne \empty </math>, то полученный граф будет представлять собой экземпляр равномерных случайных графов пересечений <math>G_{n,m,p} \;</math>.

Совокупность M иногда называется ''множеством меток'', а ее элементы – ''метками''. Обозначим за <math>L_l</math> для <math>l \in M</math> множество вершин, выбравших метку l.

В силу зависимостей от ребер эта модель способна более точно (по сравнению с моделью случайных графов Бернулли <math>G_{n,p}</math>, предполагающей независимость от ребер) абстрагировать многие практические задачи. Кроме того, Филл, Шайнерманн и Сингер-Коэн в работе [3] показали, что для некоторых диапазонов параметров <math>n, m, p (m = n^{\alpha}, \alpha > 6)</math> пространства <math>G_{n, m, p}</math> и <math>G_{n, \hat{p}}</math> являются эквивалентными в том смысле, что суммарное вариационное расстояние между переменными случайного графа имеет предел, равный 0. Николетсис, Раптопулос и Спиракис [7] предложили две новых модели, а именно модель ''случайных графов пересечений общего вида'' <math>G_{n, m,\overrightarrow{p}}, \overrightarrow{p} = [p_1, p_2, ..., p_m]</math> и модель ''регулярных случайных графов пересечений'' <math>G_{n, m, \lambda}, \lambda > 0</math>, использующих различные способы случайного присвоения меток вершинам, но применяющих одно и то же правило вхождения ребер. Модель <math>G_{n, m,\overrightarrow{p}}</math> является обобщением равномерной модели, в котором каждая метка <math>i \in M</math> выбирается независимо с вероятностью <math>p_i</math>, тогда как в модели <math>G_{n, m, \lambda}</math> каждая вершина выбирает случайное подмножество M, содержащее в точности <math>\lambda</math> меток.