Амплитуда случайных кубических графов

Рассмотрим связный случайный кубический граф $G=(V,E)$ для $n =|V|$ вершины, взятые из $G(n, 3$ -reg $)$ (как определено здесь , то есть $3n$ является четным и любые два графа имеют одинаковую вероятность).

Конечно , есть $n$ возможной ширину первых Поисковые, по одному для каждого начального узла $s \in V$ . Широтой первый поиск $B_G$ , начиная с узла $s \in V$ назначает уровня $d(s, v)$ для каждого узла $v \in V$ , где $d(s, v)$ является расстояние между $s$ и $v$ в $G$ .

$B_G$

L (s, {u, v}) = max {d (s, u), d (s, v)}

$L(s, \{u,v\}) = \max\{ d(s,u), d(s,v) \}$

e = {u, v} \in E

$e=\{u,v\} \in E$

Для конкретного поиска в , пусть будет числом ребер, которым присвоен уровень , и пусть . Другими словами - это число ребер уровня, содержащих больше ребер, чем любого другого уровня. Пусть , наконец, является максимальным для любого из Ширина первых Поиски . $B_G$ $\alpha(B_G,i)$ $i$ $\alpha(B_G) = max_i\{\alpha(B_G,i)\}$ $\alpha(B_G)$ $\alpha(G)$ $\alpha(B_G)$ $n$ $G$

Назовем $\alpha(G)$ с амплитудой в $G$ .

Вопрос

Как ожидаемое значение растет при стремлении к бесконечности? Напомним , что является случайной кубической . Точнее, я действительно хотел бы знать, принадлежит ли ожидаемое значение к . $\alpha(G)$ $n$ $G$ $\alpha(G)$ $o(n)$

Так как четное, предел считается таким, что мне наплевать на нечетные . $n$ $n$

graph-theory co.combinatorics Джорджио Камерани
источник

(1) Пожалуйста, укажите, из какого распределения вероятностей вы рисуете свой кубический график. (2) Вас интересует ожидание

как функции от

или что-то еще? (3) Я предполагаю, что

четно (иначе кубический граф не существует). Итак, я полагаю, что предел считается таким, чтобы вам было наплевать на нечетные

α (G)

$\alpha(G)$

n

$n$

n

$n$

n

$n$

Ёсио Окамото

@YoshioOkamoto: (1) Из

-reg

как определено в stanford.edu/class/msande337/notes/… (

четное и любые два графика имеют одинаковую вероятность). (2) Я обогатил вопрос, чтобы прояснить этот момент. (3) Да,

четное, и предел считается таким, что мне все равно, нечетные

G (n, 3

$G(n, 3$

)

$)$

3 n

$3n$

n

$n$

n

$n$

Джорджио Камерани

@SureshVenkat: Спасибо за улучшение читабельности вопроса ;-)

Джорджио Камерани

Позвольте мне сказать, что весьма вероятно, что на случайных кубических графиках есть результаты концентрации для

, что означает, что ожидаемое значение, значение высокой вероятности и т. Д. Все одинаковы. Если ОП не уточнит, я думаю, что ответ на любой из этих вопросов будет разумным ответом на этот вопрос.

α (G)

$\alpha(G)$

Питер Шор

@WalterBishop: Позвольте мне задать еще один вопрос. Как вы определяете

если

отключен?

α (G)

$\alpha(G)$

G

$G$

Йошио Окамото

Ответы:

Амплитуда для расширителей графов. Случайный 3-регулярный граф асимптотически почти наверняка является графом расширителя (см. Википедию) , поэтому ожидание амплитуды будет равно , поскольку вероятность того, что это не граф расширителя, переходит в а переходит в . $\alpha(n) = \Theta(n)$ $\Theta(n)$ $0$ $n$ $\infty$

Для графа расширителя с параметром для любого набора вершин с существуют соседей множества. Теперь пусть число вершин на уровне равно , а . Тогда из свойства разложения получаем, что пока не слишком велико (т. Е. Мы еще не включили половину вершин) $\beta$ $s$ $s \leq n/2$ $\beta s$ $j$ $\ell_j$ $\ell_0=1$ $j$ Теперь ищем уровенькоторый содержит вершину

ℓ_{j} \geq β \sum_{i = 0}^{j - 1} ℓ_{i}

$\ell_j \geq \beta\, \sum_{i=0}^{j-1} \ell_{i}$

ℓ_{j}

$\ell_j$

. То есть, так

. Если этот уровень большой, т.

, то все готово. В противном случае следующий уровень имеет размер

\frac{n}{3}

$\frac{n}{3}$

\sum_{i = 0}^{j - 1} ℓ_{i} < n / 3

$\sum_{i=0}^{j-1} \ell_i < n/3$

\sum_{i = 0}^{j} ℓ_{i} \geq n / 3

$\sum_{i=0}^{j} \ell_i \geq n/3$

ℓ_{j} \geq n / 6

$\ell_j \geq n/6$

и мы сделали.

ℓ_{j + 1} \geq β \sum_{i = 0}^{j} ℓ_{i} \geq β \frac{n}{3},

$\ell_{j+1} \geq \beta \, \sum_{i=0}^{j} \ell_{i} \geq \beta \frac{n}{3},$

Хотя в этом доказательстве рассматривается количество вершин на уровне, а не количество ребер (о которых спрашивал OP), на шаге всегда добавляется как минимум столько же ребер, сколько и вершин на уровне , поскольку каждая вершина должна быть достигнута. каким-то краем. $i$ $i$

Питер Шор
источник

Спасибо за Ваш ответ! Это очень удивительно (по крайней мере для меня): даже если общее количество ребер равно

, а количество уровней равно

, самый переполненный уровень имеет еще

ребер. Таким образом, края не распределены равномерно по уровням: моя (эмпирическая, неправильная) интуиция заключалась в том, что, за исключением нескольких начальных уровней и нескольких конечных уровней, должно было быть

m = 1.5 \cdot n \in Θ (n)

$m = 1.5 \cdot n \in \Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

Θ (n)

$\Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$ центральные уровни, между которыми края были бы разбросаны несколько равномерно.

Джорджио Камерани

с "эмпирическим" вы имеете в виду, что вы на самом деле запускали тесты?

составляет около

для кубических случайных графиков, см. ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/Bol88.pdf

β

$\beta$

0.1845

$0.1845$

от

Да, я провел тесты от

до

и измерил величину

n = 100

$n = 100$

n = 150000

$n = 150000$

. Если бы

приблизилось к

приувеличении

, это дало бы эмпирическое доказательство того, что

. Около

было около

, а около

было около

(конечно, я никогда не рассматривал эти числа как эмпирическое доказательство, потому что

все еще слишком мало, чтобы представлять асимптотику). Однако, когда я сказал «эмпирическая интуиция»

k = \frac{α (G)}{m}

$k = \frac{\alpha(G)}{m}$

k

$k$

0

$0$

n

$n$

α (G) \in o (n)

$\alpha(G) \in o(n)$

n = 100

$n=100$

k

$k$

0.3

$0.3$

n = 150000

$n=150000$

k

$k$

0.26

$0.26$

n = 150000

$n = 150000$

Джорджио Камерани

... Я имел в виду реальное (неправильное) чувство, а не результат тестов: я несколько чувствовал, что эти BFS должны иметь форму "колбасы" (то есть крошечные в крайних точках и с постоянной тиканью посередине). «Они должны быть такими», - подумал я. Приведенное выше доказательство показывает, насколько ошибочной была моя интуиция. Тем не менее, я до сих пор удивляюсь:

ребрами,

уровней, а не

Θ (n)

$\Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

ребер на каждом уровне.

O (\frac{n}{l o g (n)})

$O(\frac{n}{log(n)})$

Джорджио Камерани

Ответ Питера Шора действительно хорош, но есть и другой способ ответить на этот вопрос: доказать, что ширина дерева ограничена сверху в два раза по амплитуде (вершинная версия). Поскольку мы знаем, что 3-регулярные расширители имеют линейную ширину дерева, мы закончили.

См. Конструкцию разложения дерева по дереву BFS, слайд 15 этой презентации: http://www.liafa.jussieu.fr/~pierref/ALADDIN/MEETING2/soto.pdf

Легко видеть, что размер каждой сумки ограничен сверху в два раза самым широким уровнем.

didest
источник

Спасибо за ваш ответ, эта презентация была очень полезной.

Джорджио Камерани