График расширителя - Expander graph

В комбинаторика, график расширителя это разреженный граф что имеет сильный возможность подключения свойства, количественно оцениваемые с использованием вершина, край или спектральное расширение. Конструкции расширителей породили исследования в чистой и прикладной математике с несколькими приложениями для теория сложности, конструкция прочной компьютерная сеть, и теория коды с исправлением ошибок.^[1]

Определения

Интуитивно понятно, что граф-расширитель - это конечный неориентированный мультиграф в котором каждое подмножество вершин, которое не является «слишком большим», имеет «большую» границу. Разные формализации этих понятий порождают разные представления о расширителях: расширители края, вершинные расширители, и спектральные расширители, как определено ниже.

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

Расширение края

В расширение края (также изопериметрическое число или же Постоянная Чигера ) час(грамм) графа грамм на п вершины определяется как

${displaystyle h(G)=min _{0<|S|leq {frac {n}{2}}}{frac {|partial S|}{|S|}},}$

куда ${displaystyle partial S:={{u,v}in E(G) : uin S,vin V(G)setminus S}.}$

В уравнении минимум идет по всем непустым множествам S не более п/ 2 вершины и ∂S это граница края из S, т.е. множество ребер с одним концом в S.^[2]

Вершинное расширение

В изопериметрический номер вершины ${displaystyle h_{ ext{out}}(G)}$ (также расширение вершины или же увеличение) графа грамм определяется как

${displaystyle h_{ ext{out}}(G)=min _{0<|S|leq {frac {n}{2}}}{frac {|partial _{ ext{out}}(S)|}{|S|}},}$

куда ${displaystyle partial _{ ext{out}}(S)}$ это внешняя граница из S, т.е. множество вершин в ${displaystyle V(G)setminus S}$ хотя бы с одним соседом в S.^[3] В варианте этого определения (называемом уникальное расширение соседа) ${displaystyle partial _{ ext{out}}(S)}$ заменяется множеством вершин в V с точно один сосед в S.^[4]

В изопериметрический номер вершины ${displaystyle h_{ ext{in}}(G)}$ графа грамм определяется как

${displaystyle h_{ ext{in}}(G)=min _{0<|S|leq {frac {n}{2}}}{frac {|partial _{ ext{in}}(S)|}{|S|}},}$

куда ${displaystyle partial _{ ext{in}}(S)}$ это внутренняя граница из S, т.е. множество вершин в S хотя бы с одним соседом в ${displaystyle V(G)setminus S}$.^[3]

Спектральное расширение

Когда грамм является d-обычный, а линейная алгебраическая определение расширения возможно на основе собственные значения из матрица смежности А = А(грамм) из грамм, куда ${displaystyle A_{ij}}$ это количество ребер между вершинами я и j.^[5] Потому что А является симметричный, то спектральная теорема подразумевает, что А имеет п действительные собственные значения ${displaystyle lambda _{1}geq lambda _{2}geq cdots geq lambda _{n}}$. Известно, что все эти собственные значения находятся в [-d, d].

Потому что грамм регулярно, равномерное распределение ${displaystyle uin mathbb {R} ^{n}}$ с ${displaystyle u_{i}=1/n}$ для всех я = 1, ..., п это стационарное распределение из грамм. То есть у нас есть Au = ду, и ты является собственным вектором А с собственным значением λ₁ = d, куда d это степень вершин грамм. В спектральный промежуток из грамм определяется как d - λ₂, и он измеряет спектральное расширение графа грамм.^[6]

Известно, что λ_п = −d если и только если грамм двудольный. Во многих контекстах, например, в лемма о перемешивании расширителей, оценка λ₂ недостаточно, но действительно необходимо ограничить абсолютное значение все собственные значения вдали от d:

${displaystyle lambda =max{|lambda _{2}|,|lambda _{n}|}.}$

Поскольку это наибольшее собственное значение, соответствующее собственному вектору, ортогональному ты, его можно эквивалентно определить с помощью Фактор Рэлея:

${displaystyle lambda =max _{vperp u,veq 0}{frac {|Av|_{2}}{|v|_{2}}},}$

куда

${displaystyle |v|_{2}=left(sum _{i=1}^{n}v_{i}^{2}ight)^{1/2}}$

это 2-норма вектора ${displaystyle vin mathbb {R} ^{n}}$.

Нормализованные версии этих определений также широко используются и более удобны для формулирования некоторых результатов. Здесь рассматривается матрица ${displaystyle { frac {1}{d}}A}$, какой Матрица марковского перехода графика грамм. Его собственные значения находятся в диапазоне от -1 до 1. Для не обязательно регулярных графов спектр графа может быть определен аналогичным образом, используя собственные значения Матрица лапласа. Для ориентированных графов рассматривается сингулярные значения матрицы смежности А, которые равны корням собственных значений симметричной матрицы А^ТА.

Отношения между различными свойствами расширения

Определенные выше параметры расширения связаны друг с другом. В частности, для любых d-регулярный график грамм,

${displaystyle h_{ ext{out}}(G)leq h(G)leq dcdot h_{ ext{out}}(G).}$

Следовательно, для графов постоянной степени расширение вершин и ребер качественно одинаково.

Неравенства Чигера

Когда грамм является d-регулярно, существует связь между изопериметрической постоянной час(грамм) и разрыв d - λ₂ в спектре оператора смежности грамм. Согласно стандартной спектральной теории графов, тривиальное собственное значение оператора смежности d-регулярный граф λ₁=d а первое нетривиальное собственное значение - λ₂. Если грамм связно, то λ₂ < d. Неравенство Додзюка^[7] и независимо Алон и Milman^[8] утверждает, что^[9]

${displaystyle { frac {1}{2}}(d-lambda _{2})leq h(G)leq {sqrt {2d(d-lambda _{2})}}.}$

Это неравенство тесно связано с Чигер связан за Цепи Маркова и может рассматриваться как дискретная версия Неравенство Чигера в Риманова геометрия.

Также были изучены аналогичные связи между изопериметрическими числами вершин и спектральной щелью:^[10]

${displaystyle h_{ ext{out}}(G)leq left({sqrt {4(d-lambda _{2})}}+1ight)^{2}-1}$

${displaystyle h_{ ext{in}}(G)leq {sqrt {8(d-lambda _{2})}}.}$

Асимптотически говоря, величины ${displaystyle {frac {h^{2}}{d}}}$, ${displaystyle h_{ ext{out}}}$, и ${displaystyle h_{ ext{in}}^{2}}$ все ограничены сверху спектральной щелью ${displaystyle O(d-lambda _{2})}$.

Конструкции

Существует три основных стратегии построения семейств расширительных графов.^[11] Первая стратегия - алгебраическая и теоретико-групповая, вторая - аналитическая и использует аддитивная комбинаторика, а третья стратегия комбинаторная и использует зигзаг и связанные графические продукты. Нога Алон показал, что некоторые графы, построенные из конечная геометрия являются самыми редкими примерами сильно расширяющихся графов.^[12]

Маргулис – Габбер – Галил

Алгебраический конструкции на основе Графики Кэли известны различные варианты графов-расширителей. Следующая конструкция принадлежит Маргулису и была проанализирована Габбером и Галилом.^[13] Для каждого натурального числа п, рассматривается граф грамм_п с множеством вершин ${displaystyle mathbb {Z} _{n} imes mathbb {Z} _{n}}$, куда ${displaystyle mathbb {Z} _{n}=mathbb {Z} /nmathbb {Z} }$: Для каждой вершины ${displaystyle (x,y)in mathbb {Z} _{n} imes mathbb {Z} _{n}}$, его восемь соседних вершин равны

${displaystyle (xpm 2y,y),(xpm (2y+1),y),(x,ypm 2x),(x,ypm (2x+1)).}$

Тогда имеет место следующее:

Теорема. Для всех п, график грамм_п имеет второе по величине собственное значение ${displaystyle lambda (G)leq 5{sqrt {2}}}$.

Графики Рамануджана

Основная статья: График Рамануджана

Автор Теорема Алона и Боппана, все достаточно большие d-регулярные графы удовлетворяют ${displaystyle lambda _{2}geq 2{sqrt {d-1}}-o(1)}$, куда ${displaystyle lambda _{2}}$ является вторым по величине собственным значением по модулю.^[14] Графики Рамануджана находятся d-регулярные графы, для которых эта оценка точна, удовлетворяющие ${displaystyle lambda =max _{|lambda _{i}|<d}|lambda _{i}|leq 2{sqrt {d-1}}}$.^[15] Следовательно, графы Рамануджана имеют асимптотически наименьшее возможное значение ${displaystyle lambda _{2}}$. Это делает их отличными расширителями спектра.

Любоцкий, Филлипс и Сарнак (1988), Маргулис (1988) и Моргенштерн (1994) показывают, как можно явно построить графы Рамануджана.^[16] По теореме Фридмана (2003), случайный d-регулярные графики на п вершины почти рамануджановские, то есть удовлетворяют

${displaystyle lambda leq 2{sqrt {d-1}}+varepsilon }$

для каждого ${displaystyle varepsilon >0}$ с вероятностью ${displaystyle 1-o(1)}$ в качестве п стремится к бесконечности.^[17]

Приложения и полезные свойства

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

Графики-расширители нашли широкое применение в Информатика, при проектировании алгоритмы, коды исправления ошибок, экстракторы, псевдослучайные генераторы, сортировочные сети (Айти, Комлос и Семереди (1983) ) и надежный компьютерная сеть. Они также использовались при доказательстве многих важных результатов в теория сложности вычислений, Такие как SL  = L (Рейнгольд (2008) ) и Теорема PCP (Динур (2007) ). В криптография, графики-расширители используются для построения хэш-функции.

Лемма о перемешивании расширителей

Основная статья: Лемма о перемешивании расширителей

Лемма о перемешивании расширителей утверждает, что для любых двух подмножеств вершин S, Т ⊆ V, количество ребер между S и Т примерно то, что вы ожидаете от случайного d-регулярный граф. Приближение тем лучше, чем меньше ${displaystyle lambda =max{|lambda _{2}|,|lambda _{n}|}}$ является. В случайном d-регулярный граф, а также в Случайный граф Эрдеша – Реньи с вероятностью края d/п, мы ожидаем ${displaystyle { frac {d}{n}}cdot |S|cdot |T|}$ края между S и Т.

Более формально, пусть E(S, Т) обозначают количество ребер между S и Т. Если два набора не пересекаются, ребра в их пересечении учитываются дважды, то есть

${displaystyle E(S,T)=2|E(G[Scap T])|+E(Ssetminus T,T)+E(S,Tsetminus S).}$

Тогда лемма о перемешивании расширителей утверждает, что выполняется следующее неравенство:

${displaystyle left|E(S,T)-{frac {dcdot |S|cdot |T|}{n}}ight|leq lambda {sqrt {|S|cdot |T|}}.}$

Отбор проб на эспандере

Основная статья: Отбор проб на эспандере

В Граница Чернова утверждает, что при отборе множества независимых выборок из случайных величин в диапазоне [-1, 1] с высокой вероятностью среднее значение наших выборок близко к математическому ожиданию случайной величины. Лемма об обходе расширителя в силу Айтай, Комлос и Семереди (1987) и Гиллман (1998), утверждает, что это также верно при выборке из обхода по расширенному графу. Это особенно полезно в теории дерандомизация, поскольку выборка в соответствии с обходом расширителя использует намного меньше случайных битов, чем независимая выборка.

Свойство расширителя брайнграфов

С использованием магнитно-резонансная томография (МРТ) данные Национальные институты здравоохранения США -финансируемый большой Проект Human Connectome, это было показано Szalkai et al.^[18][19] что график, описывающий анатомические связи мозга между 1015 церебральными областями, значительно лучше у женщин, чем у мужчин.

Смотрите также

• Алгебраическая связность
• Зигзагообразный продукт
• Сверхсильное приближение
• Теория спектральных графов

Примечания

1. Хори, Линиал и Вигдерсон (2006)
2. Определение 2.1 в Хори, Линиал и Вигдерсон (2006)
3. Бобков, Houdré & Tetali (2000)
4. Алон и Капалбо (2002)
5. ср. Раздел 2.3 в Хори, Линиал и Вигдерсон (2006)
6. Это определение спектральной щели взято из раздела 2.3 в Хори, Линиал и Вигдерсон (2006)
7. Додзюк 1984.
8. Алон и Спенсер 2011.
9. Теорема 2.4 в Хори, Линиал и Вигдерсон (2006)
10. См. Теорему 1 и стр. 156, л. 1 в Бобков, Houdré & Tetali (2000). Отметим, что λ₂ соответствует 2 (d - λ₂) текущей статьи (см. с.153, л.5)
11. см., например, Иегудаофф (2012)
12. Алон, Нога (1986). «Собственные значения, геометрические расширители, сортировка по раундам и теория Рэмси». Комбинаторика. 6 (3): 207–219. CiteSeerX  10.1.1.300.5945. Дои:10.1007 / BF02579382.
13. см., например, стр.9 Голдрайх (2011)
14. Теорема 2.7 из Хори, Линиал и Вигдерсон (2006)
15. Определение 5.11 из Хори, Линиал и Вигдерсон (2006)
16. Теорема 5.12 из Хори, Линиал и Вигдерсон (2006)
17. Теорема 7.10 из Хори, Линиал и Вигдерсон (2006)
18. Салкаи, Балаж; Варга, Балинт; Гролмуш, Винс (2015). «Теоретический анализ графов показывает: женский мозг связан лучше, чем мужской». PLoS ONE. 10 (7): e0130045. Дои:10.1371 / journal.pone.0130045. ЧВК  4488527. PMID  26132764.
19. Салкаи, Балаж; Варга, Балинт; Гролмуш, Винс (2017). «Теоретико-графические параметры с компенсацией смещения размера мозга также лучше в женских структурных коннектомах». Визуализация мозга и поведение. 12 (3): 663–673. Дои:10.1007 / s11682-017-9720-0. ISSN  1931-7565. PMID  28447246.

Рекомендации

Учебники и обзоры

• Алон, Н.; Спенсер, Джоэл Х. (2011). «9.2. Собственные значения и расширители». Вероятностный метод (3-е изд.). Джон Вили и сыновья.
• Чунг, Фань Р. К. (1997), Теория спектральных графов, Серия региональных конференций CBMS по математике, 92, Американское математическое общество, ISBN  978-0-8218-0315-8
• Давыдов, Гилиана; Сарнак, Питер; Валетт, Ален (2003), Элементарная теория чисел, теория групп и графы Рамануджана, Студенческие тексты LMS, 55, Издательство Кембриджского университета, ISBN  978-0-521-53143-6
• Хори, Шломо; Линиал, Натан; Вигдерсон, Ави (2006), «Графики-расширители и их приложения» (PDF), Бюллетень (новая серия) Американского математического общества, 43 (4): 439–561, Дои:10.1090 / S0273-0979-06-01126-8
• Кребс, Майк; Шахин, Энтони (2011), Семейства расширителей и графы Кэли: руководство для начинающих, Издательство Оксфордского университета, ISBN  978-0-19-976711-3

Исследовательские статьи

• Айтай, М.; Комлос, Я.; Семереди, Э. (1983), "Сортировочная сеть O (n log n)", Материалы 15-го ежегодного симпозиума ACM по теории вычислений, стр. 1–9, Дои:10.1145/800061.808726, ISBN  978-0-89791-099-6
• Ajtai, M .; Komlós, J .; Семереди, Э. (1987), "Детерминированное моделирование в LOGSPACE", Материалы 19-го ежегодного симпозиума ACM по теории вычислений, ACM, pp. 132–140, Дои:10.1145/28395.28410, ISBN  978-0-89791-221-1
• Alon, N .; Капальбо, М. (2002), "Явные расширители уникального соседа", 43-й ежегодный симпозиум IEEE по основам информатики, 2002 г. Материалы, п. 73, CiteSeerX  10.1.1.103.967, Дои:10.1109 / SFCS.2002.1181884, ISBN  978-0-7695-1822-0
• Бобков, С .; Houdré, C .; Тетали, П. (2000), "λ_∞, вершинная изопериметрия и концентрация », Комбинаторика, 20 (2): 153–172, Дои:10.1007 / s004930070018.
• Динур, Ирит (2007), «Теорема PCP по усилению разрыва» (PDF), Журнал ACM, 54 (3): 12 – es, CiteSeerX  10.1.1.103.2644, Дои:10.1145/1236457.1236459.
• Додзюк, Юзеф (1984), «Разностные уравнения, изопериметрическое неравенство и быстротечность некоторых случайных блужданий», Пер. Амер. Математика. Soc., 284 (2): 787–794, Дои:10.2307/1999107, JSTOR  1999107.
• Гиллман, Д. (1998), "Граница Чернова для случайных блужданий на расширительных графах", SIAM Журнал по вычислениям, 27 (4): 1203–1220, Дои:10.1137 / S0097539794268765
• Гольдрайх, Одед (2011), "Основные факты о графах-расширителях" (PDF), Исследования сложности и криптографии, Конспект лекций по информатике, 6650: 451–464, CiteSeerX  10.1.1.231.1388, Дои:10.1007/978-3-642-22670-0_30, ISBN  978-3-642-22669-4
• Рейнгольд, Омер (2008), «Ненаправленное подключение в лог-пространстве», Журнал ACM, 55 (4): 1–24, Дои:10.1145/1391289.1391291
• Иегудаофф, Амир (2012), «Доказательство расширения в три этапа», Новости ACM SIGACT, 43 (3): 67–84, Дои:10.1145/2421096.2421115

Недавние приложения

• Хартнетт, Кевин (2018), «Универсальный метод сортировки найденной сложной информации», Журнал Quanta (опубликовано 13 августа 2018 г.)

внешняя ссылка

• Краткое введение в Уведомлениях Американского математического общества
• Вступительный доклад Майкла Нильсена
• Конспекты лекций из курса экспандеров (Нати Линиал и Ави Вигдерсон)
• Конспекты лекций из курса экспандеров (Прахлада Харши)
• Определение и применение спектральной щели