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

Для доказательства существования компоненты необходимо вначале доказать существование (с высокой вероятностью) достаточно длинного пути (логарифмической длины) в качестве основы для процесса обхода в ширину, начинающегося с вершин того пути, на основе которого создается компонент. В процессе довольно сложного доказательства используются соображения занятости (столбики диаграмм соответствуют вершинам графов, а круги – ребрам); однако упоминаемые в ходе него случайные переменные не являются независимыми, и для использования границ Черноффа-Хеффдинга для концентрации необходимо вначале доказать, что эти случайные переменные, не будучи независимыми, являются отрицательно связанными. Далее при оценке успешности процесса обхода в ширину используется более точный и детальный алгоритм «анализа в среднем».