Зигзагообразный продукт

В теории графов зигзагообразное произведение регулярных графов , обозначаемое как , является бинарной операцией , которая берет большой граф ( ) и малый граф ( ) и производит граф, который приблизительно наследует размер большого, но степень малого. Важным свойством зигзагообразного произведения является то, что если является хорошим расширителем , то расширение полученного графа лишь немного хуже расширения .${\displaystyle Г,Н}$${\displaystyle G\circ H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle H}$${\displaystyle G}$

Грубо говоря, зигзагообразное произведение заменяет каждую вершину копией (облаком) и соединяет вершины, перемещаясь на небольшой шаг (зигзаг) внутри облака, затем на большой шаг (заг) между двумя облаками и, наконец, выполняет еще один небольшой шаг внутри целевого облака.${\displaystyle G\circ H}$${\displaystyle G}$${\displaystyle H}$

Произведение зигзага было введено Рейнгольдом, Вадханом и Вигдерсоном (2000). Когда произведение зигзага было впервые введено, оно использовалось для явного построения экспандеров и экстракторов постоянной степени. Позднее произведение зигзага использовалось в теории вычислительной сложности для доказательства того, что симметричное логпространство и логпространство равны (Рейнгольд 2008).

Пусть будет -регулярным графом на с отображением вращения и пусть будет -регулярным графом на с отображением вращения . Зигзагообразное произведение определяется как -регулярный граф на , отображение вращения которого выглядит следующим образом: :${\displaystyle G}$${\displaystyle D}$${\displaystyle [Н]}$ ${\displaystyle \mathrm {Rot} _{G}}$${\displaystyle H}$${\displaystyle д}$${\displaystyle [D]}$${\displaystyle \mathrm {Rot} _{H}}$${\displaystyle G\circ H}$${\displaystyle d^{2}}$${\displaystyle [N]\times [D]}$${\displaystyle \mathrm {Rot} _{G\circ H}}$
${\ displaystyle \ mathrm {Rot} _ {G \ circ H} ((v, a), (i, j))}$

1. Позволять .${\displaystyle (a',i')=\mathrm {Rot} _{H}(a,i)}$
2. Позволять .${\displaystyle (w,b')=\mathrm {Rot} _{G}(v,a')}$
3. Позволять .${\displaystyle (b,j')=\mathrm {Rot} _{H}(b',j)}$
4. Выход .${\displaystyle ((w,b),(j',i'))}$

Из определения зигзагообразного произведения сразу следует, что оно преобразует граф в новый граф, который является -регулярным. Таким образом, если значительно больше , зигзагообразное произведение уменьшит степень . Грубо говоря, усиливая каждую вершину в облако размера произведения, фактически разделяет ребра каждой исходной вершины между вершинами облака, которые ее заменяют.${\displaystyle G}$${\displaystyle d^{2}}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle G}$${\displaystyle H}$

Расширение графа можно измерить его спектральной щелью , при этом важным свойством зигзагообразного произведения является сохранение спектральной щели. То есть, если является «достаточно хорошим» расширителем (имеет большую спектральную щель), то расширение зигзагообразного произведения близко к исходному расширению . ${\displaystyle H}$${\displaystyle G}$

Формально: Определим -граф как любой -регулярный граф на вершинах, второе по величине собственное значение (соответствующего случайного блуждания) которого имеет абсолютное значение не более .${\displaystyle (Н,Д,\лямбда)}$${\displaystyle D}$${\displaystyle N}$${\displaystyle \лямбда}$

Пусть будет -графом и -графом , тогда будет -графом, где .${\displaystyle G_{1}}$${\displaystyle (N_{1},D_{1},\лямбда _{1})}$${\displaystyle G_{2}}$${\displaystyle (D_{1},D_{2},\lambda _{2})}$${\displaystyle G_{1}\circ G_{2}}$${\displaystyle (N_{1}\cdot D_{1},D_{2}^{2},f(\lambda _{1},\lambda _{2}))}$${\displaystyle f(\lambda _{1},\lambda _{2})<\lambda _{1}+\lambda _{2}+\lambda _{2}^{2}}$

Зигзагообразное произведение действует отдельно на каждый связанный компонент .${\displaystyle G\circ H}$${\displaystyle G}$

Формально говоря, даны два графа: , -регулярный граф на и , -регулярный граф на - если является связной компонентой , то , где является подграфом , индуцированным (т.е. графом на , который содержит все ребра между вершинами в ).${\displaystyle G}$${\displaystyle D}$${\displaystyle [Н]}$${\displaystyle H}$${\displaystyle д}$${\displaystyle [D]}$${\displaystyle S\subseteq [N]}$${\displaystyle G}$${\displaystyle G|_{S}\circ H=G\circ H|_{S\times D}}$${\displaystyle G|_{S}}$${\displaystyle G}$${\displaystyle S}$${\displaystyle S}$${\displaystyle G}$${\displaystyle S}$

В 2002 году Омер Рейнгольд, Салил Вадхан и Ави Вигдерсон дали простую, явную комбинаторную конструкцию графов-расширителей постоянной степени. Конструкция итеративная и требует в качестве базового строительного блока один расширитель постоянного размера. В каждой итерации зигзагообразное произведение используется для генерации другого графа, размер которого увеличивается, но его степень и расширение остаются неизменными. Этот процесс продолжается, давая произвольно большие расширители.

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

В 2005 году Омер Рейнгольд представил алгоритм, который решает проблему ненаправленной st-связности , проблему проверки существования пути между двумя заданными вершинами в ненаправленном графе, используя только логарифмическое пространство. Алгоритм в значительной степени опирается на зигзагообразное произведение.

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

• Графические операции

• Рейнгольд, О.; Вадхан , С.; Вигдерсон , А. (2000), «Волны энтропии, произведение зигзагообразных графов и новые расширители и экстракторы постоянной степени», Труды 41-го симпозиума IEEE по основам компьютерной науки (FOCS) , стр. 3–13, arXiv : math/0406038 , doi :10.1109/SFCS.2000.892006.
• Рейнгольд, О. (2008), «Ненаправленная связность в лог-пространстве», Журнал ACM , 55 (4): Статья 17, 24 страницы, doi : 10.1145/1391289.1391291.
• Рейнгольд, О.; Тревизан , Л.; Вадхан , С. (2006), «Псевдослучайные блуждания на регулярных орграфах и проблема RL против L», Труды 38-го симпозиума ACM по теории вычислений (STOC) , стр. 457–466, doi :10.1145/1132516.1132583.