Расширитель - это разреженный (низкий градус) график с высоким «расширением», измеренный одним из нескольких способов; обычно сродни минимальному отношению размера границы подграфа к объему подграфа.
Если неориентированный -регулярный граф и представляет собой подмножество вершин мощности , вызови расширение края в г. количестваd S ≤ | V | / 2 SG=(V,E)G=(V,E)G=(V,E)dddSSS≤|V|/2≤|V|/2\leq |V|/2SSS ϕ(S):=Edges(S,V−S)d⋅|S|⋅|V−S|ϕ(S):=Edges(S,V−S)d⋅|S|⋅|V−S|\phi(S) := \frac {Edges(S,V-S)}{d\cdot...
Недавно я преподавал расширители и ввел понятие рамануджановских графов. Майкл Форбс спросил, почему их так называют, и я должен был признать, что не знаю. Кто...
Лемма о регулярности Семереди говорит, что каждый плотный граф может быть аппроксимирован как объединение многих двудольных графов расширителей. Точнее, существует большинство разбиений вершин на наборов, так что большинство пар множеств образуют двудольные расширители (количество множеств в...
Я ищу несбалансированные расширители, которые "хороши" и "экономичны". В частности, двудольный лево-регулярный граф , , , с левой степенью является -расширителем, если для любого размером не более , число различных соседей в , по крайней мере, Известно, что вероятностный метод дает такой граф с и ....
Этот вопрос вдохновлен полиномиальной гипотезой Хирша (PHC). Учитывая гранный многогранник в , ограничена ли спектральная щель графа вершин и вершин (назовем его ) снизу ? Обратите внимание, что граф циклов на вершинах показывает, что даже при спектральная щель может быть такой маленькой, как ; так...
В презентации 2006 года под названием EXPANDER GRAPHS - ОСТАЮТСЯ ЛИ какие-то ТАЙНЫ? Нати Линиал поставил следующую открытую проблему: Какие трудные вычислительные задачи на графе остаются сложными, когда они ограничены графами расширителей?NпNпNP С тех пор был ли достигнут какой-либо прогресс в...
Учитывая неориентированный регулярный граф , какова связь между его диаметром - определенным как наибольшее расстояние между двумя узлами - и его проводимостью, определенной как где e (S, S ^ c) - количество ребер, пересекающих S и S ^ c...
Доказательство Омер Рейнгольда , что дает алгоритм USTCON (В U ndirected граф со специальными вершинами S и т , они Con подсоединены?) , Используя только logspace. Основная идея состоит в том, чтобы построить график расширителя из исходного графика, а затем выполнить обход в графике расширителя....
Скажем, семейство графов имеет длинные индуцированные пути, если существует константа ϵ > 0 такая, что каждый граф G в F содержит индуцированный путь на | V ( G ) | ϵ вершины. Меня интересуют свойства семейств графов, которые обеспечивают существование длинных индуцированных путей. В частности,...
Предположим, что у каждого есть рандомизированный (BPP) алгоритм AAA использующий рrr битов случайности. Естественные способы увеличить вероятность успеха до 1 - δ1−δ1-\delta для любого выбранного δ> 0δ>0\delta>0 : Независимые прогоны + голосование большинством: прогоните AAA независимо T= Θ...
Меня интересуют комбинаторные свойства социальных сетей в виде графиков. Люди смотрели на такие вещи, как распределение степеней, коэффициент кластеризации и сжимаемость этих графиков. Один основной вопрос: действительно ли эти графики являются хорошими графами расширителей? Кто-нибудь проверял,...