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

В своей работе [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.