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

Следующие теоремы рассматривают существование независимых множеств вершин мощности k в случайных графах пересечений. Доказательство теоремы 1 использует факт линейности математического ожидания суммы случайных переменных.

'''а <math>\gamma(k, s) = \prod_{i=1}^m \Big( (1 - p_i)^{k - s} + (k - s)p_i (1 - p_i)^{k - s - 1} \Big) \Big( 1 - \frac{sp_i}{1 + (k - 1) p_i} \Big).</math>'''

Для доказательства теоремы 2 вначале запишем дисперсию в виде суммы ковариаций, а затем применим технику сжатия вершин, выполняющую слияние нескольких вершин в одну супер-вершину со схожим вероятностным поведением, для вычисления ковариаций. При помощи метода моментов второго порядка (см. [1]) можно вычислить порог для существования независимых множеств размера.

Один из трех предложенных в работе [7] алгоритмов приведен далее. Алгоритм начинает работу с V (т. е. множества всех вершин графа) в качестве «кандидата» на роль независимого множества. На каждом последующем шаге он выбирает метку и удаляет из текущего кандидата на роль независимого множества все вершины, содержащие эту метку в назначенном им множестве меток, кроме одной. В силу правила вхождения ребер этот подход гарантирует, что после выполнения этой операции для всех меток множества M финальный кандидат на роль независимого множества будет содержать только вершины, не имеющие ребер между ними, и потому по определению будет являться независимым множеством.

   4. выбрать случайную метку <math>l_i \in L</math>; положить <math>L := L - \{ l_i \}</math>;

   5. положить <math>D_i := \{ v \in A_{i - 1} : l_i \in S_v \}</math>;

   6. '''if''' <math>(|D_i| \ge 1)</math> '''then''' выбрать случайную вершину <math>u \in D_i</math> и положить <math>D_i := D_i - \{ u \}</math>;

   7. положить <math>A_i := A_{i - 1} - D_i</math>;

Следующая теорема рассматривает мощность независимого множества, вычисляемого алгоритмом. При анализе алгоритма используются уравнение Вальда (см. [9]) для сумм случайного количества случайных переменных, позволяющее вычислить среднее значение <math>|A_m|</math>, и границы Чернова (см, например, [6]) для концентрации вокруг среднего значения.

Прежде всего отметим, что, как доказано в работе [5], любой граф может быть преобразован в граф пересечений. Таким образом, модели случайных графов пересечений могут быть очень обобщенными. Кроме того, для некоторых диапазонов параметров <math>n, m, p \; (m = n^{\alpha}, \alpha > 6)</math> пространства <math>G_{n,m,p}</math> и <math>G_{n,p}</math> эквивалентны (что было доказано Филлом, Шайнерманом и Сингер-Коэн в работе [3], которые показали, что в этом диапазоне суммарное вариационное расстояние между переменными случайного графа имеет предел, равный 0).

В своей работе [4] Каронски и коллеги рассматривают задачу возникновения графов с константным числом вершин как порожденных подграфов графов <math>G_{n,m,p}</math>. Заметив, что модель <math>G_{n,m,p}</math> генерирует графики при помощи кликовых покрытий (например, множества <math>L_l, l \in M</math> представляют собой очевидное кликовое покрытие), они вывели естественный способ их использования совместно с методами моментов первого и второго порядков для нахождения, чтобы определить пороговые значения для появления любого фиксированного графа H как порожденного подграфа <math>G_{n,m,p}</math> для различных значений параметров n, m и p.

Порог связности для <math>G_{n,m,p}</math> Карен Сингер-Коэн рассматривала в работе [10]. Она изучала случай <math>m = n^{\alpha}, \alpha > 0</math>, различая два случая в соответствии со значением <math>\alpha</math>. Для случая <math>\alpha > 1</math> результаты выглядят похожими на графы <math>G_{n, p}</math>, так как среднее число ребер на порогах связности оказывается (приблизительно) одинаковым. С другой стороны, при <math>\alpha \le 1</math> мы получаем более плотные графы в <math>G_{n,m,p}</math>. Помимо связности, в [10] также рассматривался размер наибольшей клики в равномерных случайных графах пересечений для определенных значений n, m и p.

Эфтимиу и Спиракис [2] рассматривали существование гамильтоновых циклов в графах <math>G_{n,m,p}</math>. Используя соображения о связи, авторы показали, что порог возникновения гамильтоновых циклов достаточно близок к порогу связности <math>G_{n,m,p}</math>. Эффективные вероятностные алгоритмы нахождения гамильтоновых циклов в в равномерных случайных графах пересечений представили Раптопулос и Спиракис в работе [8]. Анализ этих алгоритмов подтверждает, что они хорошо работают с высокой вероятностью даже при значениях p, близких к порогу связности <math>G_{n,m,p}</math>. Кроме того, в той же работе предложен алгоритм нахождения гамильтоновых циклов графах в <math>G_{n,m,p}</math> с константой p с ожидаемым полиномиальным временем выполнения.

В [11] Старк представил аппроксимацию распределения степени фиксированной вершины в модели <math>G_{n,m,p}</math>. Точнее говоря, применяя метод решета, автор предлагает точную формулу для производящей функции вероятности, генерирующей степень некоторой фиксированной вершины, а затем анализирует эту формулу для различных значений параметров n, m и p.

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