WWW.KNIGA.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Онлайн материалы
 

Pages:   || 2 |

«Экспандеры: конструкции и приложения. Жалобы на ошибки, опечатки и непонятные места в этом тексте можно посылать Андрею Ромащенко ...»

-- [ Страница 1 ] --

Экспандеры: конструкции и приложения.

Жалобы на ошибки, опечатки и непонятные места в этом тексте можно

посылать Андрею Ромащенко по адресу andrei.romashchenko@gmail.com

22 января 2015 г.

Оглавление

1 Введение 3

1.1 Как организована эта книга.................... 4

1.2 Чего в этой книге нет........................ 4

1.3 Учебная литература по экспандерам............... 4

1.4 Используемые обозначения..................... 5 2 Комбинаторные экспандеры 6

2.1 Однородные экспандеры....................... 6

2.2 Рёберное расширение........................ 9

2.3 Двудольные экспандеры....................... 11

2.4 Замечание об эффективных конструкциях........... 12

2.5 Исторический коментарий..................... 14 3 Спектральные экспандеры. 15

3.1 Матрица графа............................ 15

3.2 Спектральные зазор и перемешивание.............. 18

3.3 Лапласиан графа.......................... 22

3.4 От спектрального экспандера к комбинаторному........ 23

3.5 От комбинаторного экспандера к спектральному....... 27

3.6 Насколько большим может быть спектральный зазор?.... 29



3.7 Спектральные экспандеры: теорема о существовании..... 31

3.8 Усиление спектральной оценки для случайного графа.... 34

3.9 Случайное блуждание на экспандерах.............. 39 4 Рекурсивные конструкции экспандеров 45

4.1 Классические произведения графов............... 45

4.2 Зигзаг-произведение графов.................... 46

4.3 Первая спектральная оценка для зигзаг-произведения....

–  –  –

Глава 1 Введение Экспандерами, или расширяющими графами, называют класс разреженных графов (графов с относительно небольшим числом рёбер), обладающих замечательными комбинаторными свойствами сильной связности, вершинного и рёберного расширения, быстрого перемешивания и т.д.

Понятие экспандера первые возникло в начале 1970-х годов в работах М.С. Пинскера и Л.А. Бассалыго. Настоящий взрыв интерес к экспандерам произошёл в 1990-х, когда стали обнаруживаться многочисленные приложения экспандеров в самых разных областях математики и информатики. Экспандеры оказались связаны одновременно и с вполне абстрактным областям математики (аддитивная комбинаторика, теория чисел, теория представлений), и с теорией сложности вычислений (вероятностно проверяемые доказательства, оценка сложности аппроксимации, методы дерандомозации), и с прикладными инженерными задачами (например, помехоустойчивое кодирование).

В этой книге мы рассматриваем экспандер прежде всего как инструмент в теоретической информатике. Мы обсуждаем разные варианты определения экспандера (для однородных и двудольных графов, комбинаторные и спектральные) и их взаимосвязь, описываем несколько методов эффективного построения экспандеров и рассматриваем различные примеры использования экспандеров в теории сложности вычислений и теории кодирования.

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





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

1.1 Как организована эта книга Главы, отмеченные звёздочкой, при первом чтении можно пропускать. Главы 7 и 8 (о разных приложениях экспандеров) можно читать независимо друг от друга.

1.2 Чего в этой книге нет Мы не претендуем на обзор всех важных результатов об экспандерах или хотя бы приложений экспандеров в теоретической информатике; отбор материала отражает субъективные вкусы автора. Прекрасный обзор теории экспандеров, написанный с точки зрения computer scientists, можно найти в [1].

Мы не касаемся использования экспандеров в математике. Читателю– математику мы рекомедуем обзор [2].

Наконец, мы лишь коротко упоминаем один из самых удивительных успехов теории экспандеров эффективное построение графов Рамануджана. Изучение данной темы требует по-настоящему серьезной математической подготовки. Подробное изложение этого вопроса можно найти в [3].

В этой книге мы не обсуждаем другие типы комбинаторных объектов, близкие по своим свойствам к экспандерам extractors, dispersers, randomness conductors, hitting set generators (мы приводим английские названия, поскольку русская терминология в этой области науки ещё не сложилась).

1.3 Учебная литература по экспандерам Для computer scientists: кроме специализированного обзора [1] мы рекомендуем посвященные экспандерам главы в [5] и [6] и материалы на homepage Луки Тревисана (http://www.eecs.berkeley.edu/„luca/). Для математиков: обзор [2], монография [3], а также заметки по курсу лекций [4]. Студенты всех специальностей найдут для себя что-то интересное в [7].

1.4 Используемые обозначения Для неориентрированных графов мы используем обозначение G “ pV, Eq, где V есть множество вершин, а E множество рёбер. При этом мы допускаем графы с петлями и с кратными (параллельными) рёбрами1. Для двудольных графов мы иногда используем обозначение G “ pR, L, Eq, чтобы подчёркнуть, что множество вершин разбито на два непересекающихся класса L и R ( левая и правая доли соответственно); E по-прежнему обозначает множество рёбер (у каждого ребра один из концов принадлежит L, а другой R).

Если A и B являются подмножествами (возможно, пересекающимися) вершин графа, мы обозначаем EpA, Bq множество рёбер, у которых один из концов принадлежит A, а второй B. Также мы обозначаем pvq множество соседей вершины v (множество всех вершин w, соединённых с v ребром).

Аналогичное обозначение используется для множеств вершин: если A есть подмножество вершин графа, то pAq обозначает множество всех соседей A, т.е.

pAq “ pvq.

vPA

–  –  –

1 Для графа с кратными рёбрами правильнее называть E не множеством, а мультимножеством рёбер, поскольку для каждой пары вершин в E может содержаться больше одного ребра с данными концами.

Глава 2 Комбинаторные определения экспандеров В этой главе мы рассмотрим базовые определения экспандеров и докажем существование графов, удовлетворяющих этим определениям.

2.1 Однородные экспандеры.

Начнём мы с самого простого варианта определения экспандера. Мы определим экспандер как однородный граф со свойством вершинного расширения (потребуем, чтобы у каждого не сишком большого множества вершин графа имелось достаточно много соседей). Сформулируем определение более точно.

Определение 1 Граф G “ pV, Eq называется однородным комбинаторным pn, d, q-экспандером (расширяющим графом), если |V | “ n (в графе n вершин), степени всех вершин равны d (допускаются кратные ребра и петли), и выполняется следующее свойство вершинного расширения: для любого множества A V, |A| n{2 множество соседей достаточно велико: |pAq| p1 ` q|A|.

Замечание 1: Чем больше значение в определении 1, тем более сильное свойство требуется от графа.

Замечание 2: Степень вершины графа это число рёбер, для которых данная вершина является концом. Это определение распространяется и на петли (ребра, у которых концы совпадают). Таким образом, если некоторой вершине инцидентны d1 рёбер, не являющихся петлями, и ещё d2 петель, то степень этой вершины равна d1 ` d2 (каждая петля учитывается с кратностью один, как и всякое другое ребро).

Теорема 1 Пусть – некоторое положительное число меньшее 1. Тогда для всех достаточно больших четных d и всех n существует однородный pn, d, q-экспандер.

Доказательство: Мы выберем граф случайно и покажем, что с положительной (и даже довольно близкой к 1) вероятностью такой граф оказывается экспандером. Отсюда будет следовать, что экспандеры существуют.

Прежде всего, нам нужно уточнить, что означает случайный выбор графа. Другими словами, нужно зафиксировать распределение вероятностей на графах. Мы выберем случайно d{2 перестановок i на множестве вершин графа, i : t1,..., nu t1,..., nu, i “ 1,..., d{2.

(Каждая перестановка i выбирается среди n! равновероятных вариантов;

при этом все d{2 перестановок выбираются независимо друг от друга.) Ребрами графа будем считать все (неупорядоченные) пары вершин tv, i pvqu.

Таким образом, из каждой вершины v выходит d{2 рёбер tv, i pvqu и ещё d{2 рёбер tv, i pvqu. У перестановок могут быть неподвижные точки (перестановка может оставлять некоторые вершины на месте), так что в случае v “ i pvq мы получаем петлю ребро, оба конца которой совпадают с v.

Чтобы степень каждой вершины была равна d, мы будем учитывать каждую петлю дважды.

Отметим, что в таком графе с положительной вероятностью появляются кратные рёбра (поскольку одно и то же ребро tv, i pvqu может получаться из нескольких перестановок i.

Теперь оценим вероятность того, что полученный в результате граф не окажется экспандером. Согласно определению, граф не является экспандером, если найдется множество вершин S (размером не более n{2), все соседи которого лежат в некотором множестве T, состоящем из p1 ` q|S| вершин.

Зафиксируем некоторые множества вершин S и T. Зафиксируем номер перестановки i. Вероятность того, что для каждой вершины v P S второй конец ребра tv, i pvqu попадёт в T, равна |S| |T | |T | 1 |T | |S| ` 1 |T |...

n n1 n |S| ` 1 n (в каждый сомножитель вида p|T |kq{pnkq из левой части неравенства не превосходит |T |{n). Поскольку мы выбираем d{2 перестановок независимо, вероятность того, что данное событие произойдёт для всех i, не превосходит pd{2q|S| |T |. Таким образом, n

–  –  –

где суммирование происходит по всем множествам вершин S размера не более n{2 и по всем множествам T размера p1 ` q|S|.

Следует отметить, что интересующая нас вероятность ещё меньше чтобы свойство экспандерности нарушилось, для каждой вершины v P S все рёбра вида tv, i pvqu также должны попасть в T. Но мы не будем этого учитывать, рёбер вида tv, i pvqu уже достаточно, чтобы получить нужную нам оценку на вероятность неприятного события.

Оценим интересующую нас сумму:

–  –  –

Остаётся заметить, что n 2s, а 1` 2. Таким образом, можно подобрать такое d “ dpq, чтобы выражение в квадратных скобках в правой части (2.2) было меньше 1{2 при всех значениях s. Следовательно, сумма (2.1) меньше единицы. А это и означает, что с положительной вероятностью случайный граф является pn, d, q-экспандером. Теорема доказана.

Упражнение 1 Оцените асимптотику d “ dpq в теореме 1: насколько большим должна быть степень графа, чтобы гарантировать существование экспандера с данным параметром расширения ?

–  –  –

Упражнение 3 Докажите следующие утверждения:

(а) Вероятность того, что в случайно выбранной (по равномерному распределению) перестановке : t1,..., nu t1,..., nu нет ни одной неподвижной точки, стремится к 1{e при n 8;

(б) Для любых, P p0, 1q, для всех d и всех достаточно больших n сумма (2.2) не превосходит n ;

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

Упражнение 4 (а) Докажите, что некоторого 0 и для всех достаточно больших чётных n существует однородный комбинаторный pn, 3, qэкспандер.

(б) Докажите, что ни для каких 0 не существует pn, 2, q-экспандеров.

Замечание: Не следует воспринимать определение 1 догматически в некоторых случаях может оказаться удобно его немного подправить. В стандартном определении требуется, чтобы свойство расширения выполнялось для множеств, содержащих не более 50% от всех вершин графа. Однако для приложений иногда бывает удобнее потребовать, чтобы свойство расширения выполнялось лишь для достаточно малых множеств A (скажем, для множеств, содержащих не более 1% всех вершин графа) или, напротив, для всех множеств, содержащих не более 99% всех вершин графа. Выбор границы n{2 в определении достаточно произволен и не существенен для построения теории экспандеров.

Упражнение 5 Рассмотрим распределение вероятностей на d-регулярных графах, использованное в доказательстве теоремы 1 (для чётного d 4). Докажите, что для любого 0 найдётся такое 0, что для всех достаточно больших n для случайно выбранного графа с n вершинами с большой вероятностью выполнено свойство

–  –  –

Объясните, почему оценку pd 1 q нельзя заменить на d.

2.2 Рёберное расширение В нашем основном определении 1 требуется, чтобы граф обладал свойством вершинного расширения. Можно ввести числовую характеристику графа коэффициент вершинного расширения, который показывает, насколько хорошими экспандерными свойствами данный граф обладает.

Определение 2 Будем называть коэффициентом вершинного расширения графа G “ pV, Eq число

–  –  –

Согласно определению, граф G является однородным pn, d, q-экспандером, если hV pGq 1 `.

Иногда бывает удобно рассмотреть несколько другое свойство графа свойство рёберного расширения.

–  –  –

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

Упражнение 6 (а) Докажите, что для любого d-однородного графа G

–  –  –

(б) Если в d-однородном графе с n вершинами у каждой вершины есть петля, а коэффициент рёберного расширения равен, то такой граф является однородным комбинаторным pn, d, q-экспандером в смысле определения 1.

–  –  –

2.3 Двудольные экспандеры.

В этом разделе мы введём ещё одно важное определение расширяющего графа двудольный экспандер.

Определение 4 Двудольный граф G “ pL, R, Eq (L и R левая и правая доли графов, E множество рёбер) называется двудольным pn, m, d, k, qэкспандером, если |L| “ n, |R| “ m, степень всех вершин в левой доле L равна d, и выполняется следующее свойство расширения: для любого множества S L, |S| k множество соседей (соседи S лежат в R) достаточно велико: |pSq| p1 qd|S|.

Замечание: Чем меньше значение в этом определении, тем сильнее требование к графу. В приложениях как правило используют двудольные экспандеры с 1{2. А для применения в теории кодирования (для построения экспандерных кодов) часто требуются двудольные экспандеры с ещё меньшими значениями.

Теорема 2 Пусть – некоторое положительное число. Тогда для любых n и k n найдется d “ Oplog nq и m “ Opdkq такие, что существует двудольный pn, m, d, k, q-экспандер.

Замечание: Константы в Opq-обозначения в этой теореме зависят от.

Доказательство: Выберем граф случайно. Это значит, что для каждой вершины в L мы случайно и независимо выбираем d соседей в R (таким образом, разрешаются кратные рёбра). Покажем, что с большой вероятностью такой граф оказывается экспандером.

Граф не является экспандером, если некоторое множество вершин из левой доли графа S L (размера не более k) имеет не больше p1 qd|S| соседей. Другими словами, все соседи S содержатся в некотором подмножестве правой доли графа T R, состоящем из p1 qd|S| вершин.

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

–  –  –

(последнее неравенство выполнено для всех d больших 1 logp2enq). Таким образом, для выбранных значений параметров суммы (2.3) и (2.4) не превосходят 1. Это означает, что с положительной вероятностью случайный двудольный граф является pn, m, k, d, q-экспандером. Теорема доказана.

Упражнение 9 Оцените асимптотику зависимости d и m от в теореме 2: как зависят степень графа и размер правой доли от параметра расширения ?

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

1. Типичные свойства графа: каковы свойства типичного, случайно выбранного графа? Например, что можно утверждать про коэффициент вершинного расширения для 99% графов степени d с n вершинами?

2. Экстремальные свойства графов: насколько сильными экспандерными свойствами может обладать граф? Например, насколько большим может быть коэффициент вершинного расширения для графа степени d с n вершинами?

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

4. Алгоритмически эффективные конструкции: как построить экспандер, для которого не просто имеется явное описание, но который можно построить с помощью быстрого алгоритма.

Приведённые выше доказательства теоремы 1 и теоремы 2 неконструктивны. Эти рассуждения показывают, что экспандеры с заданными параметрами существуют и, более того, большинство графов являются такими экспандерами. Однако эти доказательства не дают способа предъявить хотя бы один такой граф явно. Разумеется, мы можем перебрать все графы с заданным числом вершин и найти среди них экспандер. Но такой перебор потребует экспоненциального (от числа вершин) времени. Хуже того, даже для одного графа на n вершинах прямая проверка определения экспандера требует экспоненциального перебора (нужно перебрать все подмножества вершин и для каждого из них подсчитать число соседей).

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

Эффективные в слабом смысле конструкции: экспандеры с n вершинами, которые можно построить за время polypnq. В данном случае требование построить граф означает, что мы должны предъявить некоторое стандартное описание этого графа (скажем, матрицу смежности или список всех его рёбер).

Эффективные в сильном смысле конструкции: экспандеры с N “ 2pnq вершинами, простые операции с которыми можно производить за время polypnq. В таком графе каждая вершина задаётся индексом, состоящим из pnq битов; мы требуем, чтобы по индексу вершины можно было найти список всех её соседей (точнее, список индексов всех её соседей) за время polypnq. (Тут стоит напомнить, что мы интересуемся разреженными графами, в которых у каждой вершины сравнительно небольшое число соседей.

Так что для каждой вершины размер списка её соседей будет очень коротким; трудность лишь в том, как вычислять эти списки достаточно быстро.) Поиск эффективных конструкций экспандеров с параметрами, близкими к оптимальным, является одной из центральных задач теории экспандеров. В разделах 4 и 5 мы изучим несколько таких конструкций, основанных на разных математических идеях.

2.5 Исторический коментарий Определение экспандера, неконструктивное доказательство существование экспандеров и первые примеры примеры их применений появилось в начале 1970-х в работах сотрудников московского Института проблем передачи информации Л.А. Бассалыго и М.С. Пинскера, [8, 9]. Другой математик Г.А. Маргулис (тоже сотрудник ИППИ) дал первое конструктивное доказательство существование экспандера [10]. Стоит также отметить, что граф со свойством сильной связности (довольно близким к ставшему стандартным определению экспандера) использовался ещё в 1960-х в работе Барздиня и Колмогорова [11].

Глава 3 Спектральные экспандеры.

В этой главе мы введём определение спектрального экспандера и изучим его связь с определением комбинаторного экспандера из главы 2.

3.1 Матрица графа.

Граф c n вершинами описывается матрицей смежности M размерности n n, в которой элемент mij равно числу рёбер, соединяющих i-ую и j-ую вершины графа. Эта матрица симметрична. Если граф однородный и степень каждой вершины равна d, то сумма чисел в каждой строке и каждом столбце матрицы равна d.

Различные свойства графа удобно описывать в терминах этой матрицы:

• pi, jq-й элемент матрицы M k есть число путей длины k, идущих из вершины i в вершину j;

• если разделить матрицу M на d, то получится матрица, у которой сумма любой строки и любого столбца равна 1. Умножение на эту матрицу описывает случайное блуждание: если p “ pp1,..., pn qJ есть вектор-столбец, состоящий из вероятностей, описывающих некоторое распределение на вершинах графа, то вектор p d M pq задает распределение через один шаг случайного блуждания (мы выбираем случайную вершину v согласно распределению p и переходим к её соседу, выбрав случайно одно из d рёбер, выходящих из v).

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

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

Для начала сделаем несколько простых наблюдений:

• матрица M симметрична и потому имеет ортогональный собственный базис над вещественным полем, с вещественными собственными значениями;

• поскольку сумма всех чисел в каждой строке равна d, вектор-столбец p1, 1,..., 1qJ является собственным вектором и имеет собственное значение d;

• все собственные значения не превосходят d по модулю: поскольку суммы элементов во всех строках матрицы равны d, то максимум модулей собственного вектора при умножении на M увеличивается не более чем в d раз;

• если граф состоит из нескольких компонент связности, то имеется несколько собственных векторов с собственным значением d (для вершин одних компонентах связности берём единицы, для других нули);

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

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

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

Упражнение 10 Найдете все собственный числа матрицы полного графа с n вершинами (а) без петель и (б) с петлями.

–  –  –

(в) Выразите через собственные числа графа число треугольников (циклов длины 3) в G.

Упражнение 12 Докажите, что спектр регулярного графа симметричен относительно нуля тогда и только тогда, когда граф является двудольным.

Мы уже знаем, что у регулярного графа степени d все собственные числа по абсолютной величине не превосходят d, и есть хотя бы одно собственное число в точности равное d.

Упорядочим собственные числа графа по абсолютной величине:

d “ |1 | |2 |... |n |.

Как мы увидим уже в следующем разделе, экспандерные свойства графа (например, свойства вершинного и рёберного расширения) связаны с зазором между |1 | и |2 |. В дальнейшем нам часто придётся говорить о втором по абсолютной величине собственном числе графа G. Для удобства введём специальное обозначение pGq :“ |2 |.

Напомним также, что максимальное собственное число всякой симметричной матрицы M равно максимуму отношения Рэлея по всем ненулевым векторам:

xJ M x 1 “ max.

x“0 ||x||2

–  –  –

Упражнение 14 Если A, B являются симметричными стохастическими матрицами, то pA ` Bq pAq ` pBq (где pM q обозначает второе по абсолютной величине собственное число матрицы).

3.2 Спектральный зазор и свойство перемешивания В этой разделе мы определим спектральный экспандер как однородный граф с достаточно большим спектральным зазором. Мы изучим простейшие свойства спектральных экспандеров и покажем, что спектральный зазор связан с некоторыми комбинаторными свойствами графа (свойства быстрого перемешивания ).

Определение 5 Регулярный граф G степени d с n вершинами будем называть спектральным pn, d, q-экспандером, если pGq d.

Другими словами, спектральный pn, d, q-экспандер это граф степени d, у которого все собственные числа кроме одного по абсолютной величине не превосходят d.

Если “ 0, это означает, что матрица графа является матрицей полного перемешивания (в каждой клетке матрицы стоит элемент 1{n). Такое возможно лишь в случае d “ n (такой матрицей обладает полный граф с петлями). Если же значение положительно, но сравнительно мало, это означает, что граф в том или ином смысле обладает свойствами хорошего перемешивания. Далее мы докажем два утверждения, несколько разным способом формализующие это соображение. Первое из этих утверждений (известное как лемма о перемешивании) гласит, что в спектральном экспандере число рёбер, ведущих из множества вершин A в множество вершин B, сравнительно мало отличается от d|A||B|.

n

–  –  –

Замечание 1: Леммой о перемешивании удобно пользоваться, когда множества вершин A и B достаточно велики (каждое из них занимает некоторую фиксированную долю среди n вершин графа), а параметр очень мал (значительно меньше, чем доли |A|{n и |B|{n). Лемма говорит, что число рёбер между парой таких множеств A, B достаточно велико, т.е. спектральный экспандер обладает определённым свойством сильной связности.

Замечание 2: Лемма о перемешивании и говорит, в частности, что один шаг случайного блуждания в спектральном экспандере (с достаточно малым значением параметра ) довольно быстро приближает любое начальное

–  –  –

Для интерпретации этого неравенства удобно рассмотреть равномерное распределение вероятностей на подмножестве вершин A. Мы выбираем случайную вершину из A и делаем один шаг случайного блуждания (переходим по случайно выбранному ребру в соседа данной вершины). Какова вероятность того, что в результате мы попадем в одну из вершин множества B?

Мы можем утверждать, что эта вероятность равна |EpA,Bq|. Если бы итогоd|A| вое распределение оказалось равномерным, то данная вероятность была бы равна доле множества B во всём графе, т.е. |B|{n. Хотя на самом деле получаемое распределение и не является равномерным, но вероятность попасть из случайной вершина A в какую-нибудь вершину множества B отличается b от идеальной вероятности |B|{n ненамного не более, чем на |B|. |A| Доказательство леммы о перемешивании: Обозначим 1A и 1B характеристические векторы множеств A и B (i-ая координата соответствующего вектора равен единице, если i-ая вершина графа принадлежит A или B соответственно; значение координаты равно нулю в противном случае). Заметим, что сумма квадратов координат вектора 1A есть в точности число элементов в множестве A; аналогично, сумма квадратов координат вектора 1B есть в точности число элементов в множестве B. Следовательно, евклидова норма этих векторов есть квадратный корень из числа элементов в A и B соответственно, a a ||1A ||2 “ |A|, ||1B ||2 “ |B|.

Если M матрица графа, то число рёбер, ведущих из A в B равно |EpA, Bq| “ 1J M 1B (3.1) A

–  –  –

и лемма доказана.

В следующем утверждении мы с другой стороны посмотрим на замечание 2 к лемме о перемешивании (стр. 18). Мы снова начнем с равномерного распределения на подмножестве вершин графа A и сделаем один шаг случайного блуждания. Мы покажим, что получающееся в результате распределение вероятностей на вершинах графа довольно близко к равномерному.

Точнее, мы оценим 2 -норму погрешности разности между полученным нами распределением и настоящим равномерным распределением на графе.

–  –  –

есть проекция x на направление 1 “ p1,..., 1qJ. В самом деле, в разности x y сумма координат равна нулю; это значит, что x y ортогонален 1.

Таким образом, мы хотим оценить квадрат нормы вектора xy, принадлежащего подпространству векторов с нулевой суммой координат. В этом подпространстве все собственные числа матрицы графа M по модулю не превосходят d, так что при умножении на M норма вектора увеличивается не более, чем в pdq раз.

Обозначим 1A вектор из t0, 1un, у которого единицы стоят в позициях, соответствующих элементам множества A, и нули во всех остальных позициях. Тогда x “ M 1A и y “ M pa 1q. Таким образом,

–  –  –

Упражнение 15 Выведите лемму о перемешивании из утверждения 2.

Упражнение 16 Вершины спектрального pn, d, q-экспандера нельзя раскрасить менее чем в 1{ цветов так, чтобы никакие смежные вершины не были покрашены в один цвет.

Упражнение 17 Пусть граф G является спектральным pn, d, q-экспандером, целое число k 1{ является делителем n, и вершины графа раскрашены в k цветов так, что каждый из цветов использован ровно для n{k вершин. Докажите, что найдётся хотя бы одна вершина, среди соседей которой встречаются все k цветов.

–  –  –

(для каждого рёбра мы берём квадрат разности весов, сопоставленных его весам). Эта функция x называется лапласианом графа. Лапласиан графа с n вершинами определен для любого x P Rn.

Лапласиан – это квадратичная форма, матрицу которой легко описать:

Утверждение 3 Для всякого графа G

–  –  –

где M матрица смежности графа, а DegpGq матрица степеней графа (в i-ой клетке диагонали стоит степень i-ой вершины графа, а во всех клетках вне диагонали стоят нули). В частности, для однородного графа, в котором все вершины имеют степень d,

–  –  –

Утверждение доказано.

Далее мы будем предполагать, что граф является однородным и каждая вершина имеет степень d. Если спектр матрицы графа M состоит из чисел

–  –  –

Мы уже знаем, что спектр M лежит в интервале rd, ds, причём (i) кратность собственного числа d равна числу компонент связности, и (ii) кратность собственного числа d равна числу двудольных компонент связности.

–  –  –

Это значит, что каждое собственное число L не превосходит 2d; причем собственный вектор x соответствует собственному значению 2d, если и только если для каждого ребра pi, jq соответствующие значения xi и xj противоположны. Размерность подпространства таких x равна числу двудольных компонент графа.

Упражнение 18 Обозначим L лапласиан d-регулярного графа G “ pV, Eq, где число вершин n “ |V |. Обозначим 0 “ 1 2... n собственные числа лапласиана. Пусть 2 “ 0, а 10 0. Обозначим e2 собственный вектор, соответствующий собственному числу 2. Докажите, что среди координат e2 встречается не более 9 различных значений.

3.4 От спектрального экспандера к комбинаторному В этой разделе мы изучим связь между спектральным и комбинаторным определениями экспандера. Мы покажем, что всякий спектральный экспандер является однородным комбинаторным экспандером (и чем больше зазор между первым и вторым собственным числом у спектрального экспандера, тем более сильные свойства рёберного и вершинного расширения мы можем гарантировать для этого графа).

Теорема 3 Пусть граф G содержит n вершин, степень каждой вершины равна d и спектр матрицы графа состоит из чисел

–  –  –

Замечание 1: В данном случае 2 – это второе в порядке убывания (не по абсолютной величине!) собственное значение графа.

Замечание 2: Если 2 “ d, то в графе больше одной компоненты связности. Если множество вершин A образует компоненту связности, то |EpA, Aq| “

0. Так что в графе с нулевым зазором между первым и вторым собственным числом коэффициенты рёберного и вершинного расширения также равны нулю.

Из теоремы 3 немедленно получаем связь спектрального и комбинаторного определения экспандера:

–  –  –

(в числителе сумма берётся по всем парам точек, соединённых ребром, а в знаменателе по произвольным парам вершин). Поскольку каждое значение |xi xj | есть ноль или единица, данное выражение можно переписать в виде

–  –  –

Сначала мы оценим коэффициент рёберного расширения графа через значение Lapsq pf q, а затем покажем, как Lapsq pf q связано со спектральным зазором.

Лемма 2 Lapsq pf q hE pGq ||f ||2.

Доказательство леммы: Напомним, что мы считаем вершины графа vi пронумерованными таким образом, что

–  –  –

найдётся хотя бы один, пересекающий сравнительно мало рёбер.

Лемма 2 позволяет нам оценить рёберное расширение графа с помощью Lapsq pf q. Теперь мы покажем, как значение Lapsq pf q связано с более стандартной величной Lappf q.

? a Лемма 3 Lapsq pf q 2d Lappf q ||f ||2.

–  –  –

Доказательство леммы: Для самого вектора f лапласиан вычислить трудно, но мы знаем значение лапласиана на каждом из собственных векторов графа. В частности, из утверждения 3 мы немедленно получаем

–  –  –

и лемма доказана.

Соединяя утверждения лемм 2, 3 и 4, мы получаем утверждение теоремы.

3.6 Насколько большим может быть спектральный зазор?

Мы уже знаем, что чем больше зазор между первым и вторым собственным числом, тем более сильные свойства перемешивания и расширения мы можем гарантировать для такого графа. Возникает вопрос: насколько большим можно сделать этот зазор? В этом разделе мы установим границы возможного мы покажем, что спектральный зазор невозможно сделать слишком большим. Другими словами, в d-регулярном графе модуль второго собственного числа не может быть слишком маленьким. Лучшее, на что мы можем надеяться это второе собственное число примерно равное ?

2 d 1. Сформулируем это утверждение более точно.

–  –  –

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

Мы рассмотрим некоторую чётную степень графа l “ 2k. Напомним, что для оценки второго собственного числа симметричной матрицы надо ограничить соответствующую ей квадратичную форму на ортогональное дополнение к первому собственному вектору e “ p1,..., 1qJ и взять её максимум на единичном шаре. Таким образом, f J M 2k f pGq2k “ pG2k q ||f ||2 для любого вектора f с нулевой суммой координат. В качестве f мы берём вектор вида f “ p0, 0,..., 0, 1, 0,..., 0, 1, 0,...qJ У этого вектора ровно две ненулевые координаты (i-ая и j-ая). Вершины i и j мы выбираем так, чтобы расстояние между ними было максимальным возможным (т.е. равно диаметру графа G).

Для выбранного вектора f имеем

–  –  –

3.7 Спектральные экспандеры: теорема о существовании Мы изучили разные свойства спектральных экспандеров, однако до сих пор не задавались вопросом о существовании таких графов.

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

Теорема 6 Пусть 0 произвольное число. Тогда для достаточно больших d существует граф с n “ d4 вершинами степени d, у которого все собственные числа, кроме первого d, не превосходят по модулю d.

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

Прежде всего опишем распределение вероятностей, которое мы будем использовать. Оно будет отличаться от распределения, использованного в доказательстве теоремы 1. Мы будем считать, что n (число вершин) чётно.

Если n чётно, мы имеем право рассмотреть на n вершинах совершенные паросочетания. (Совершенное паросочетание есть такой набор из n{2 рёбер, что каждая из n вершин является концом ровно одного ребра. Другими словами, совершенное паросочетание на n вершинах есть граф степени 1, состоящий из n{2 рёбер.) Мы выбираем на n вершинах d случайных паросочетаний P1,..., Pd (каждое из d паросочетантий выбирается равномерно;

все d выборов делаются независимо). Объединение выбранных паросочетаний мы и будем считать графом G. Отметим, что в таком графе не может быть петель, однако могут быть кратные рёбра (поскольку одно и то же ребро может входить в несколько паросочетаний).

Мы обозначаем собственные числа полученного графа i и считаем, что

–  –  –

Теперь нам нужно оценить pGq “ |2 |. При возведении матрицы в степень (мы выберем десятую степень) все собственные числа возводятся в ту же степень и след матрицы станет равным

–  –  –

Первое слагаемое равно d10 ; если для какой-то матрицы вся сумма близка к d10, то все слагаемые кроме первого малы. А существование такой матрицы будет доказано, если мы убедимся что среднее значение следа матрицы M 10 (для матрицы графа, выбранного случайно описанным выше способом) близко к d10.

В нашем распределении вероятностей все вершины графа равноправны. След M 10 равен сумме диагональных элементов, поэтому его среднее значение равно среднему значению одного элемента, умноженному на n. А среднее значение одного элемента равно среднему числу путей длины 10, начинающихся и кончающихся в данной вершине. Так что нам надо доказать, что среднее число таких путей ненамного больше, чем d10 {n.

Подсчёт удобно интерпретировать в терминах вероятностей. Будем считать, что помимо d паросочетаний P1,..., Pd (напомним, что каждое из которых выбирается независимо, причём все паросочетания равновероятны) мы отдельно (и независимо) выбираем набор из 10 чисел “ p1,..., 10 q, каждое число от 1 до d. После этого мы (для фиксированной вершины графа) строим путь длины 10, выходящий из этой вершины. На первом шаге он идёт вдоль паросочетания P1, на втором вдоль P2, и так далее. Нас интересует вероятность того, что после 10 шагов мы вернёмся в исходную точку. Точнее, мы хотим показать, что она равна n p1 ` op1qq.

Поменяем порядок усреднения: если усреднять сначала по выбору i, то получается число петель длины 10 (делённое на d10 ), которое затем можно усреднять по выбору Pi.

Мы же проведём усреднение в другом порядке:

сначала для каждого фиксированного набора i мы усредняем по всем графам, и лишь потом усредняем по всевозможным наборам i.

Все наборы “ 1,..., 10 делятся на три категории:

1. гарантированно приводящие в исходную точку (независимо от выбора Pd ); к этой категории относятся наборы, в которые после сокращений подряд идущих равных чисел ничего не остаётся;

2. наборы, состоящие из десяти разных чисел.

3. наборы, которые сокращаются не полностью, но в которых присутствуют равные числа (мы идём несколько раз по одному и тому же паросочетанию, но не обязательно подряд).

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

1. Количество наборов первого типа не превосходит Opd5 q. В самом деле, есть некоторое (фиксированное, так как число 10 фиксировано) число способов сокращения, и для каждого способа сокращения имеется не более d5 способов его реализации (пять сокращающихся пар). Для каждого такого вероятность получить замкнутый путь равна 1 какой бы граф мы не выбрали, путь с пометками обязательно приведет в исходную вершину.

2. Наборы без повторений составляют большинство из общего числа d10 (при достаточно больших значениях d). При этом вероятность того, что на последнем шаге цикл замкнётся, и мы вернемся в исходную вершину есть 1{n, поскольку последнее 10 число в наборе ранее не встречалось и соответствующее 10 паросочетание независимо с предыдущими 9 шагами нашего пути.

3. Количество наборов второго типа есть Opd9 q, где константа в O-обозначении соответствует числу возможных пар позиций, где происходит совпадение (то есть C10 “ 10 9{2).

В наборе “ 1... 10 будем сокращать пары идущих подряд одинаковых букв, пока такие сокращения возможны. По условию набор не сократится полностью останется некоторое несократимое 1. Докажем, что вероятность вернуться в исходную точку для такого набора 1 равна Op1{nq. Мы докажем даже более сильное утверждение: вероятность того, что при движении по пути 1 мы хотя бы одну (не обязательно исходную) вершину посетим дважды, равна Op1{nq.

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

В момент перед назначенным возвращением в уже пройденную вершину уже фиксированы некоторые рёбра некоторых паросочетаний (те, что использованы в пути), а следующее ребро (по которому мы должны попасть в уже посещённую вершину) ещё не фиксировано.

Поэтому для его конца остаётся не менее n 10 вариантов, и вероятность выбрать один из них не больше 1{pn 10q “ Op1{nq.

–  –  –

Если n “ d4, то второй член в этой сумме будет основным, и потому среднее значение следа есть n d10 p1 ` op1qq “ d10 p1 ` op1qq.

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

Упражнение 19 Докажите аналогичное утверждение для n “ d8.

Замечание: Как мы покажем в следующем разделе, некоторое обобщение метода из доказательства теоремы 6 позволяет доказать значительно более сильную оценку для спектрального зазора в случайном графе. Однако при первом чтении раздел 3.8 можно пропустить, поскольку теоремы 6 и утверждения из упражнения 19 достаточно для всех применений, которые нам потребуются в этой книге.

3.8 Усиление спектральной оценки для случайного графа В этом разделе мы покажем, как улучшить оценку из главы 3.7 и доказать существование d-регулярных графов со вторым собственным числом Opd3{4 q (вместо доказанной в предыдущем разделе оценки opdq).

Теорема 7 Для всякого d и всех достаточно больших n существует спектральный экспандер с параметрами pn, d, Op1{d1{4 qq (d-регулярный граф, второе собственное число которого по модулю не превосходит Opd3{4 q).

Доказательство: Мы докажем теорему для чётных n (доказательство для нечётных n оставляется читателю в качестве упражнения). Случайный граф с n вершинами мы выбираем так же, как и в доказательстве теоремы 6. Мы независимо выбираем d случайных (по равномерной мере) паросочетаний на n вершинах и объединим их в один граф. В результате получается граф, в котором каждая вершина имеет степень d (в графе могут быть кратные ребра, но не может быть петель). Матрицу полученного графа обозначим M. Нужно доказать, что с большой вероятностью второе (по абсолютной величине) собственное число этой матрицы равно Opd3{4 q.

Мы будем оценивать среднее значение следа M 2k для матрицы M случайно выбранного графа при подходящем k, которое подберём позже. (Мы возводим M непременно в чётную степень; это нужно для того, чтобы степени всех собственных чисел стали положительными.) Удобно заранее поделить матрицу на d, чтобы первое собственное число стало равным единице.

Мы оценим второе собственное число графа pGq через след M 2k :

1 ` p{dq2k trrpM {dq2k s (3.9) Из этого неравенства видно, что нам достаточно доказать существование графа, для которого правая часть в данном неравенстве мала. Для этого мы, как и раньше, оцениваем сверху среднее значение правой части.

Математическое ожидание следа равно сумме математических ожиданий диагональных элементов. Все они одинаковы, поэтому правая часть (3.9) равна n, умноженному на вероятность вернуться из данной точки в себя после k случайных шагов по нашему случайному графу. Таким образом, мы должны показать, что эта вероятность лишь немного превосходит 1{n.

Вероятностное пространство является произведением двух независимых выборов. Во-первых, мы выбираем d независимых паросочетаний P1,..., Pd на n вершинах (эти паросочетания и образуют граф G). Во-вторых, мы выбираем случайное слово длины 2k в алфавите из d букв P1,..., Pd (каждом шаге блуждания по графу мы идем по ребру, которое получилось из одного из d паросочетаний Pi ). Нас интересует следующее событие: начав с фиксированной вершины и проходя по рёбрам выбранных паросочетаний в выбранном порядке, мы в итоге возвращаемся в исходную вершину.

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

Среди слов есть такие, от которых после выполнения сокращений ничего не остаётся; для таких слов интересующая нас вероятность равна 1. Другая простая ситуация: если после сокращения остаётся слово, в котором никакое паросочетание Pi не встречается дважды, то вероятность равна 1{pn1q: на последнем шаге условная вероятность вернуться в начало (при любом развитии событий на предыдущих шагах) равна 1{pn 1q, так как предыдущие шаги никак не ограничивают последнее паросочетание.

Мы увидим, что для большинства слов вероятность вернуться в исходную вершину близка к 1{n. Это большинство образуют регулярные слова.

Чтобы определить, будет ли слово регулярным, представим себе его написанным по кругу и сократим (в том числе в точке контакта начала и конца). Если останется непустое слово, не являющееся степенью (не имеющее периода, меньшего длины цикла), то исходное слово будем называть регулярным. Нерегулярные слова, таким образом, после сокращений имеют вид XY i X 1, где Y несократимое слово (слово, в котором нигде не встречаются две одинаковые буквы подряд).

Лемма 5 Доля нерегулярных слов не больше Opk 2 p9{dqk q.

Доказательство леммы 5: Нам нужно оценить число слов, которые после сокращения имеют вид XY i X 1.

Чтобы описать нерегулярное слово, нужно задать буквы в соответствующих X и Y. При этом требуется задать не более k букв (буквы X парны к буквам X 1, а буквы в Y i входят в i 2 копиях). Таким образом, при фиксированных длинах X и Y у нас есть не более dk способов выбрать слово XY i X 1.

Остаётся для каждой пары X, Y подсчитать число схем сокращения число нерегулярных слов, которые после сокращения приводятся к виду XY i X 1. Будем сокращать исходное слово длины 2k слева направо (добавляем очередную букву и сокращаем её с предыдущей, если сокращается). Схему сокращения опишем символически: если добавленная буква впоследствии сократится, изображаем её левой скобкой, а ту, с которой она сократится, правой. Буквы, которые так и не сократятся, изобразим звёздочками. Таких последовательностей из скобок и звёздочек существует не больше, чем 32k. Наконец, к такой последовательности остаётся добавить длины слов X и Y, каждое не более Opkq.

Получатся, что число нерегулярных словне превосходит dk 32k Opk 2 q.

Делим эту величину на общее число всех слов длины 2k в алфавите из d символов (т.е. на d2k ) и получаем Opk 2 p9{dqk q. Лемма 5 доказана.

Упражнение 20 Докажите, что последовательность скобок и звёздочек в схеме сокращения можно однозначно восстановить, если знать, где стоят левые скобки. (Это наблюдение позволяет усилить оценку в лемме 5 до Opk 2 p4{dqkq.) Лемма 6 Для любого регулярного слова W вероятность того, что задаваемое W преобразование оставляет данную точку на месте (для случайных паросочетаний P1,..., Pd ), не превышает 1{pn 2kq ` Opk 4 {n2 q.

Доказательство леммы 6: Нам будет удобно представлять себе вероятностный процесс следующим образом: вместо того, чтобы выбирать случайные паросочетания заранее, будем определять их постепенно по мере чтения слова W, оставляя не фиксированными те части паросочетаний P1,..., Pd, которые пока не понадобились. В каждый момент этого процесса для каждого паросочетания Pi уже определённая часть представляет собой набор рёбер (пар вершин графа), причём каждая вершина используется не более одного раза. Когда мы переходим к следующей букве слова W, может оказаться, что очередное ребро уже определено имеющейся частью перестановок (вынужденный ход), а может оказаться, что нет (свободный ход).

В последнем случае мы доопределяем нужную перестановку, соединяя вершину (равновероятно) со всеми оставшимися кандидатами.

Будем говорить, что происходит совпадение, когда на свободном ходу мы попадаем в уже пройденную вершину. Заметим, что первое попадание в уже пройденную вершину всегда будет совпадением (в предыдущую вершину мы попали впервые, и потому из неё все ходы будут свободными, кроме возвратного, который невозможен, так как W несократимо).

Поэтому интересующая нас вероятность разбивается на два случая:

• мы вернулись в исходную вершину, при этом произошло ровно одно совпадение;

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

Второй случай разбивается на Opk 2 q вариантов в зависимости от моментов совпадений (мест в слове W, где они произошли). Вероятность каждого варианта не более 1{pn 2kq2. В самом деле, условная вероятность совпадения при фиксированной предыстории (пути до него) не больше k{pn 2kq, так как мы доопределяем перестановку в новой точке и имеется не менее n 2k равновероятных вариантов, из которых не более k успехов. Таким образом вероятность второго случая не превосходит Opk 4 {n2 q (можно считать, что k ! n, иначе оценка тривиальна).

Осталось показать, что в первом случае вероятность совпадения не превосходит 1{pn 2kq. Это следует из того, что совпадение произойдёт в заранее известном месте, а именно, при движении по последней букве слова Y в разложении W “ XY X 1. Более того, до этого момента все пройденные вершины будут различны.

Сейчас мы это докажем, и при этом нам придётся воспользоваться непериодичностью слова Y (см. определение регулярного слова). Посмотрим на момент, когда мы впервые попадаем в уже пройденную вершину.

Этот момент будет совпадением, поэтому достаточно доказать, что это случается в конце слова Y. В самом деле:

• после этого новые вершины в пути уже не появятся, так как из новых вершин нужно вернуться в старые, и это будет совпадением;

• свободных ходов больше не будет, так как это было бы вторым совпадением;

• вынужденных ходов из каждой вершины (за исключением точки ветвения) не более двух, при этом один невозможен (возвращение по только что пройденному ребру означало бы, что слово W сократимо);

• поэтому движение определяется почти однозначно и состоит из нескольких циклов плюс возврат в исходную вершину (по предположению мы туда возвращаемся);

• однозначно определяются не только ходы, но и соответствующие буквы слова, поэтому разбиение на цикл и отросток совпадает с разложением W “ XY X 1 ;

–  –  –

Остаётся подобрать параметр k. Выберем его так, чтобы p9{dqk “ 1{n2, то есть k “ 2 logd{9 n. Тогда третье слагаемое в скобках поглощается вторым, а n2k можно заменить на n ` Opk{n2 q. Значит, математическое ожидание 2k следа матрицы pM {dq не превосходит

–  –  –

Можно доказать, что это распределение достаточно близко к равномерному распределению на множестве всех 2d-регулярных графов.

2. Мы рассматривали графы чётной степени; если требуется построить граф нечётной степени, можно добавить по петле к каждой вершине, отчего собственные числа увеличатся на единицу.

3. Теорема о том, что у большинства графов второе собственное число имеет порядок Opd3{4 q была доказано Бродером и Шамиром (Broder– Shamir, [15]). Намного более сложные рассуждения (Joel Friedman, [16]) позволяют доказать, что на самом деле у большинства d-регулярных графов ?

второе собственное число близко к 2 d 1. В тоже время, теорема 5 показывает, что второе собственное число не может быть меньше 2 d 1 op1q (для больших n).

3.9 Случайное блуждание на экспандерах Мы уже отмечали, что спектральные экспандеры обладают свойствами, которые можно назвать свойством хорошего перемешивания. Даже один шаг случайного блуждания на спектральном экспандере заметно заметно приближает исходное распределение вероятностей на вершинах к равномерному (см. лемму о перемешивании на с. 18 и утверждение 2 на с. 20). В этом разделе мы подробнее изучим случайное блуждание на спектральном экспандере, состоящее из нескольких шагов. Для начала мы продемонстрируем основной технический приём данного раздела на простом примере.

Утверждение 4 Пусть граф G является спектральным pn, d, q-экспандером без петель и A некоторое множество вершин графа, состоящее из n вершин. Тогда число рёбер в индуцированном A подграфе (число рёбер, оба конца которых принадлежат A) не превосходит nd 2 p ` p1 qq.

Замечание 1: Если выбирать ребро графа случайно, то для каждого из его концов вероятность попасть в A равна. Если бы эти события для двух концов ребра были бы независимы друг от друга, то вероятность того, что ребро попало в индуцированные A подграф, равнялась бы 2. Конечно же, на самом деле эти события зависимы. Доказываемое утверждение гласит, что для экспандера данную вероятность можно оценить величиной p2 ` p1 qq.

Замечание 2: Мы уже знаем, что спектральный экспандер обладает свойством хорошего рёберного расширения: если |A| не слишком велико, то найдется достаточно много рёбер, ведущих из множества A в его дополнение. По существу, доказываемое утверждение говорит то же самое, но в других терминах: найдется не слишком много рёбер, у которых оба конца принадлежат A.

Доказательство: Рассмотрим вектор f “ pf1,..., fn qJ, где fi “ 1, если i-ая вершина графа G принадлежит A, и fi “ 0 иначе. Если M матрица графа, то число рёбер, оба конца которых принадлежат A, можно вычислить как 1 pf J M f q. В самом деле,

–  –  –

Напомним, что среди координат вектора f имеется n единиц и p1q нулей.

Следовательно, квадрат нормы ||f ||2 “ n. Отсюда мы можем немедленно заключить, что f J M f p1 ` qn, и число рёбер в индуцированном подграфе не превосходит p1`qn. Это уже хорошая оценка, но мы обещали доказать немного более сильное неравенство.

Где можно усилить оценку? Мы очень грубо оценили величины ||f ||2 и ||fK ||2 как ||f ||2. На самом же деле по теореме Пифагора мы имеем ||f ||2 ` ||fK ||2 “ ||f ||2. Таким образом, (3.11) можно более аккуратно оценить как d||f ||2 ` pdq||fK ||2 ||f ||2 ` pdqp||f ||2 ||f ||2 q “ pdq||f ||2 ` p1 qd||f ||2.

–  –  –

Следствие 3 Пусть граф G является спектральным pn, d, q-экспандером без петель и A некоторое множество вершин графа, состоящее из n вершин. Тогда все собственные числа индуцированного подграфа на вершинах A не превосходят pd ` p1 qqd.

Теперь мы готовы доказать несколько утверждений о блуждании на экспандере.

Утверждение 5 Пусть граф G является спектральным pn, d, q-экспандером без петель и A некоторое множество вершин графа, состоящее из n вершин. Рассмотрим случайное блуждание по графу

–  –  –

где вершина x0 выбирается случайно (по равномерному распределению), а затем на каждом шаге i “ 1,..., k следующая вершина xi выбирается случайно (также равномерно) среди всех соседей xi1. Тогда

–  –  –

Утверждение доказано.

Замечание 1: Рассмотрим случайное блуждание по экспандеру, состоящее из k “ rs шагов, x0 x1... xrs.

Как и раньше, вершина x0 выбирается случайно (по равномерному распределению), а затем на каждом шаге i “ 1,..., k следующая вершина xi выбирается случайно (также равномерно) среди всех соседей xi1. Будем интересоваться вероятностью того, что все вершины c номерами, кратными s (т.е. x0, xs, x2s,..., xrs ) попали в множество A.

Вероятность этого события оценивается следующим образом:

–  –  –

В самом деле, нужно применить утверждение 5 не к исходному графу G, а к его s-ой степени (к графу на n вершинах, рёбрами которого являются пути длины s в G).

Замечание 2: Снова рассмотрим случайное блуждание по экспандеру, состоящее из k шагов, x0 x1... xk.

На этот раз оценим вероятность того, что в множество A попали все вершины c номерами xi1, xi1 `i2, xi1 `i2 `i3,..., xi1 `i2 `...`ir. Вероятность этого события оценивается сверху

–  –  –

В самом деле, в рассуждение из замечания 1 легко переносится на случай, когда шаги между контролируемыми номерами шагов xj неодинаковы.

Таким образом, мы доказали следующий результат:

Утверждение 6 Пусть граф G является спектральным pn, d, q-экспандером без петель и A некоторое множество вершин графа, состоящее из n вершин. Рассмотрим случайное блуждание по графу

–  –  –

где вершина x0 выбирается случайно и равномерно, а затем на каждом шаге i “ 1,..., k следующая вершина xi выбирается случайно равномерно среди всех соседей xi1.

Пусть I t0,..., tu некоторое подмножество номеров шагов. Тогда

–  –  –

Упражнение 22 Пусть G “ pV, Eq является алгебраическим pn, d, qэкспандером, и A E некоторое множество его вершин. Выберем случайное ребро из A, а затем случайно выберем один из концов этого ребра.

Затем сделаем i шагов случайного блуждания по графу. Покажите, что вероятность того, что последнее ребро в данном случайно выбранном пуA| ти принадлежит A, не превосходит |E| ` i1.

Глава 4 Рекурсивные конструкции экспандеров

4.1 Классические произведения графов Напомним, что мы уже встречались с некоторым способом умножения графа на самого себя. Возведением графа G в степень k называется следующая операция: мы сохраняем прежнее множество вершин, а рёбрами в новом графе считаем все пути длины k в исходном графе. Результат возведения графа в степень k мы обозначаем Gk. Если исходный граф был однородным степени d, то его k-ая степень будет также однородным графом, но степени dk. Если M матрица исходного графа, то матрицей его k-ой степени будет будет M k (обычное возведение матрицы в степень k). При этом, разумеется, собственные векторы матрицы сохраняются, а собственные числа также возводятся в степень k.

Нетрудно также определить тензороное произведение графов. Для произвольных графов G1 “ pV1, E1 q и G2 “ pV2, E2 q назовём их тензороным произведением граф G “ pV, Eq, в котором множество вершин V “ V1 V2 (каждая вершина в новом графе есть пара вершин исходных графов), а рёбрами соединяются все такие пары pv1, v2 q и pv1, v2 q, для которых tv1, v1 u P E1 и tv2, v2 u P E2.

Декартово произведение графов G1 и G2 мы обозначаем G1 b G2.

Упражнение 23 Объясните, как из матриц графов G1 и G2 получить матрицу тензорного произведения G1 b G2.

Упражнение 24 Пусть спектр графа G1 состоит из чисел 1,1, 1,2,..., 1,n, а спектр граф G2 состоит из чисел 2,1, 2,2,..., 2,m.

Докажите, что спектр G1 b G2 состоит из всевозможных произведенийp1,i 2,j q.

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

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

Мы определим зигзаг-произведение этих графов. Для этого каждую вершину первого графа заменим маленькой копией второго графа, прикрепив рёбра первого графа к вершинам второго. (В маленьком графе как раз нужное число вершин.) Обратим внимание, что в прикреплении есть произвол конкретный выбор соответствия в каждой вершине не играет роли.

Получится граф с nD вершинами и рёбрами двух типов большими рёбрами, унаследованными из из первого графа, и малыми, унаследованными из второго. (На рисунке сплошные и пунктирные линии соответственно.) Зигзаг-произведение (zig-zag product): Вершины у зигзаг-произведения будут те же, но рёбра совсем другие. В качестве рёбер нового графа мы берём все пути длины 3 вида [пунктирное ребро] – [сплошное ребро] – [пунктирное ребро].

Другими словами, каждое сплошное ребро порождает d2 рёбер зигзаг-произведения (соединяющих пары пунктир-соседей концов сплошного ребра), как показано на рисунке (рёбра зигзаг-произведения показаны кривыми линиями):

–  –  –

Замечание 1. Вершины в зигзаг-произведении графов G и H удобно задавать парами координат pg, hq, где g есть вершина графа G, а h вершина графа H (первая координата задаёт номер копии графа H, а вторая координата указывает вершину внутри этой копии).

Замечание 2. Если G несвязен, то процедуру зигзаг-умножения G на H можно произвести независимо для каждой из компонент связности G (и полученный в итоге граф заведомо не будет связным).

Далее мы докажем оценки для второго собственного числа зигзаг-произведения.

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

Теорема 9 Зигзаг-произведение алгебраического pn, D, q-экспандера G и алгебраического pD, d, q-экспандера H является алгебраическим экспандером с параметрами pnD, d2, ` ` 2 q.

Замечание. Можно улучшить оценку для второго собственного числа до `, но мы ограничимся доказательством более слабого утверждения.

Доказательство: Чтобы оценить второе собственное значение симметричной матрицы, надо ограничить квадратичную форму на ортогональное дополнение к первому собственному вектору e0 “ p1,..., 1qJ и взять её максимум на единичном шаре. Другими словами, модуль второго собственного числа матрицы H GH есть максимум выражения |fJ H GH f| по всем векторам f длины nD, имеющим единичную длину и ортогональных e0 (то есть имеющих нулевую сумму координат). Чтобы оценить это выражение, разложим f в сумму f “ g ` h следующим образом: координаты g одинаковы в каждой из облаков (копий графа H), а для h на каждой копии графа H сумма координат равна нулю.

Чтобы оценить значение квадратичной формы на произвольном векторе f K e0, мы отдельно изуим действие матриц G и H на векторы g и h:

(a) Hg “ d g, поскольку внутри каждой копии H веса (координаты) вектора g одинаковы, и каждый из них распространяется в d соседей в том же облаке.

(b) }Hh} d }h}, поскольку вектор h в каждой копии H ортогонален первому собственному вектору матрицы графа H, а все остальные собственные векторы этой матрицы не превосходят (по модулю) d.

–  –  –

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

Опишем конструкцию более подробно. Зафиксируем граф Hpd4, d, 1{10q для некоторого d (для достаточно больших d такой граф, как мы видели, существует). Затем построим последовательность графов G0, G1,..., положив <

–  –  –

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

обсуждение на с. 12).

Чтобы более точно определить, что такое эффективная конструкция графа G “ pV, Eq, мы произвольным образом зафиксируем для каждой вершины графа нумерацию инцидентных ей рёбер. Будем называть функцией вращения отображение N : xx, iy y, которое сопоставляет вершине графа x P V и номеру i (не превосходящему степени вершины x) вершину y P V, которая является i-ым соседом x (выйдя из x по i-ому ребру, мы попадём в вершину y “ N px, iq).

Если число вершин в графе не превосходит 2n, а степень каждой вершины равна 2d, то каждую вершину можно задавать n-битным индексом, а номер выходящего из вершины ребра, соответственно, d-битным индексом.

Таким образом, функцию вращения можно понимать как отображение

N : t0, 1un t0, 1ud t0, 1un.

Сильная эффективность означает, что время вычисления N px, iq полиномиально зависит от длины аргументов, т.е. от от логарифма от числа вершин и от логарифма степени графа. (Для сравнения: в слабо эффектвиной конструкции графа функция вращения будет вычислимой за время полиномиально зависящее от самого числа вершин графа, а не от его логарифма).

–  –  –

Начальные графы G0 и G1 построить легко (G0 это граф, состоящий из единственной вершины и d2 петель, граф G1 можно получить из H размножением рёбер в d раз, что не меняет собственных чисел). Затем можно воспользоваться рекуррентной формулой Gn “ pGtpn1q{2u b Grpn1q{2s q2 z H, где b обозначает тензорное произведение, а z зигзаг-произведение. Тензорное произведение в скобках имеет параметры pd8pn1q, d4, 1{2q, после возведения в квадрат получается pd8pn1q, d8, 1{4q и после зигзаг произведение pd8n, d2, 1{2q (в силу того же вычисления с 1{4 и 1{10, что и раньше).

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

Замечание. Описанная конструкция работает для всех достаточно больших чётных d. В частности, можно взять в качестве d некоторую степень двойки. Таким образом, мы научились эффективно строить по заданному n спектральный экспандер с параметрами p2cn, Op1q, 1{2q (для некоторой константы c, не зависящей от n). Если требуется уменьшить нормализованной собственное число с 1{2 до некоторого 0, достаточно возвести построенный граф в степень rlog2 p1{qs; при этом степень графа возведётся в такую же степень, а число вершин не изменится. Отметим, что экспандеры с 2n часто бывают удобны в приложениях (см., например, главу 7).

Упражнение 25 Докажите, что для всех достаточно больших n существует явная в сильном смысле конструкция спектрального p2n, Op1q, 1{2qэкспандера (без предположения, что n кратно некоторому фиксированному числу c).

4.5 Аффинная плоскость как экспандер Все явные последовательности экспандеров, которые мы строили, формировались вокруг затравочного экспандера H с подходящими параметрами, который мы находили перебором (длина перебора не зависела от n, так что мы имели право использовать его в полиномиальном по n алгоритме). Сейчас мы опишем алгебраическую конструкцию, которая позволяет строить нужный нам затравочный граф без перебора.

Пусть q – простое число. Рассмотрим граф APq, вершинами которого являются все пары pa, bq P Z2, а рёбрами соединены такие вершины pa, bq, q pc, dq, что ac “ b ` d mod q Полезно представлять себе пару pa, bq как точку на аффинной плоскости над Zq, а pc, dq как прямую, задаваемую уравнением y “ cx d, которая проходит через эту точку.

Таком образом, граф состоит из q 2 вершин, и степень каждой вершины равна q. Покажем, что второе по абсолютной величине собственное число ?

графа равно q.

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

Обозначим M матрицу графа APq. Будем считать, что вершины pa, bq нумеруются сначала по первой, а потом по второй координате. Таким образом, матрица M состоит из q 2 квадратных блоков размера q q; в каждом таком блоке (i-ом по горизонтали, j-ом по вертикали) ребра соответствуют переходу из вершин вида pi, q в вершины pj, q.

Матрицу M 2 легко выписать в явном виде. Действительно, M 2 описывает пути длины 2 на APq. Если i “ j, то есть ровно один такой путь из pi, kq в pj, lq (поскольку на плоскости есть ровно одна прямая, которая проходит через точки pi, kq и pj, lq). Если k “ l, то из pi, kq в pi, lq нет путей длины два (мы не рассматриваем вертикальные прямые на плоскости). Наконец, для каждой вершины pi, kq имеется q циклов длины два.

Таким образом, матрица M 2 имеет вид qI J J... J J qI J... J ‹ ‹............... ‚ J J J... qI где I диагональная единичная матрица q q, а Jq матрица q q, в которой на всех местах стоят единицы.

В тензорных обозначениях это можно записать так:

–  –  –

4.6 Вторая спектральная оценка для зигзаг-произведения В этом разделе мы докажем оценку для второго собственного числа спектрального произведения в предположении, что в исходных графах второе собственное число хотя бы немного отделено от первого.

Теорема 10 Зигзаг-произведение алгебраического pn, D, 1 q-экспандера G и алгебраического pD, d, 1 q-экспандера H является алгебраическим экспандером с параметрами pnD, d2, 1 2 q.

Замечание: Если и достаточно малы, то оценка из теоремы 9 становится бессмысленной, поскольку сумма p1 q ` p1 q ` p1 q2 будет больше единицы.

Лемма 7 Пусть A матрица блуждания по некоторому графу (первое собственное число равно 1), и все остальные собственные числа по модулю не превосходят 1. Тогда A можно представить в виде p1 qB ` J, где B матрица с нормой не больше 1, а J матрица полного перемешивания (все матричные элементы равны 1{rчисло вершинs).

Доказательство: вычитая из A матрицу J, мы уменьшаем первое собственное число (единицу) на, а остальные не трогаем, так что все собственные числа становятся не больше 1 по модулю. Таким образом, у разности pA Jq норма не превосходит p1 q, и лемма доказана.

–  –  –

и теорема доказана.

Подстановочное произведение.

4.7 В разделе 4.2 мы определили зигзаг-произведение на графах, которое оказалось полезным для получения явных конструкций экспандеров. В этом разделе мы введём ещё два аналогичных вида произведения на графах.

Для графа G (с n вершинами, степени D) и графа H (c D вершинами, степени d) мы определим простое и сбалансированное подстановочное произведение (как и в определении зигзаг-произвдения, важно, что степень первого графа равна числу вершин во втором графе). Начало конструкции совершенно аналогично определению зигзаг-произведения: мы заменим каждую вершину графа G копией графа H, прикрепив рёбра первого графа к вершинам второго. При этом у нас получится граф с nD вершинами и рёбрами двух типов большими из первого графа и малыми из второго (см. рисунок на стр. 47: рёбра первого типа показаны сплошными, а рёбра второго типа пунктирные линии.) Простое подстановочное произведение (replacement product): Построенный выше граф в точности и есть простое подстановочное произведение G и H (и сплошные и пунктирные рёбра на равных правах включаются в новый граф). В полученном графе nD вершин (n облаков по D вершин в каждой); степень каждой вершины равна d ` 1 (из каждой вершины выходит одно сплошное и d пунктирных рёбер).

Сбалансированное подстановочное произведение (balanced replacement product): Отличие состоит лишь в том, что мы берём каждое сплошное ребро с кратностью d. таким образом, в полученном графе-произведении из каждой вершины выходит 2d рёбер: d сплошных и d пунктирных.

Оценим второе собственное число для сбалансированного подстановочного произведения. Мы будем оценивать не малость второго собственного числа, а его отделённость от единицы.

Теорема 11 Пусть графы G и H являются алгебраическими экспандерами с параметрами pn, D, 1 q и pD, d, 1 q соответственно. Тогда их сбалансированное подстановочное произведение G r H имеет параметры pnD, 2d, 1 2 {24q.

Доказательство: Удобно описывать происходящее в терминах блужданий (соответствующих нормализованным матрицам, полученных делением матрицы смежности на степень графа). Блуждание по взвешенному произведению является полусуммой двух блужданий: локального, где мы движемся внутри одном облаке в соответствии с матрицей графа H, и глобального, где мы движемся по рёбрам графа G (а выбор ребра определяется текущей H-координатой: вершин в графе H как раз столько, сколько рёбер в G, и мы предполагаем, что фиксировано какое-то соответствие). Таким образом, матрицу блуждания можно записать как U“ G ` H, где G и H матрицы перехода по локальным и глобальным рёбрам.

Чтобы оценить второе собственное число U, достаточно оценить второе собственное число U 3 “ p 1 G ` 1 Hq3 и доказать, что оно не больше 1 2 {8 (а затем воспользоваться неравенством Бернулли).

В разложении для U 3 будет восемь членов. Все эти члены имеют два инвариантных подпространства: одномерное векторы, у которых все координаты равны (все восемь членов на этом подпространстве единичные, и при каждом стоит коэффициент 1{8), и ортогональное к нему (векторы, сумма координат которых равна нулю), где максимальное собственное значение (и тем самым норма ограничения на это подпространство) и есть интересующий нас параметр. Если бы мы доказали, что для одного из этих восьми произведений второе собственное число не больше 1 2, то это бы гарантировало, что для U 3 это второе собственное число не больше 1 2 {8, поскольку у оставшихся семи произведений норма не больше 1.

Какое из восьми слагаемых выбрать? Кажется, что наилучшие шансы на перемешивание у H GH (сначала перемешиваем внутри облака с помощью графа H, потом идём по ребру большого графа, потом перемешиваем внутри другого облака как в зизаг-произведении). Если бы перемешивание внутри облака было полным (переход в случайную точку облака), то такой переход был бы переходом в случайную вершину случайной соседнем облаке. Соответствующее преобразование является тензорным произведением G и полного перемешивания, и потому имеет второе собственное число 1, как у G.

Это много лучше, чем нам нужно (мы получили 1 вместо 1 2 {8), что и не удивительно: мы волюнтаристски заменили перемешивание вдоль H полным перемешиванием. Но поскольку переход по ребрам H не является полным перемешиванием, нам придётся несколько усложнить рассуждение.

(При этом вместо 1 мы получим для второго собственного числа более скромную оценку 1 2 {8).

Применим лемму 7 к блужданию по графу H и разложим его в сумму p1qA`B. Это разложение можно провести в каждом облаке и получить разложение H “ p1 qA ` B, где A некоторый оператор с нормой не больше 1, а B то самое полное перемешивание внутри облаков, о котором мы говорили выше.

Повторяем прежнее рассуждение. Теперь в разложении 1 1 U“ G` A` B будет уже не 8, а 27 слагаемых. В одном из этих слагаемых (а именно, в B GB) второе собственное значение не превосходит 1, а остальные представляют собой операторы с нормой не больше 1 с некоторыми скалярными коэффициентами (сумма коэффициентов при этих 27 слагаемых равна единице). Поэтому второе собственное значение U не больше 1 2 {8. Теорема доказана.

Применим полученные оценки чтобы описать ещё одну явную конструкцию спектральных экспандеров. Прежде всего мы выберем алгебраический экспандер H с параметрами pd50, d{2, 1{100q, а также алгебраические экспандеры G1 и G2 с параметрами pd100, d, 1{2q и pd200, d, 1{2q соответственно (такие графы существуют для всех достаточно больших d). Далее построим последовательность ` r H, Gn “ Gtpn1q{2u b Grpn1q{2s Упражнение 26 Проверьте, что Gn является алгебраическим экспандером с параметрами pd100n, d, 1 1{50q; функция вращения для такого графа Gn вычисляется за полиномиальное от n время.

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

Теорема 12 Пусть даны два однородных графа:

• граф G степени D с n вершинами, с коэффициентом рёберного расширения hE pGq,

• граф H степени d с D вершин, с коэффициентом рёберного расширения hE pGq.

Тогда сбалансированное подстановочное произведение этих графов G r H будет графом степени 2d с nD вершинами и с коэффициентом рёберного расширения не меньше 64 2.

Доказательство: Рассмотрим в построенном графе G r H произвольное множество вершин S размера не более nD{2 (т.е. не более половины всех вершин графа). Напомним, что в конструкции подстановочного произведения возникают два типа рёбр сплошные (они проводятся между облаками по D вершин) и пунктирные (внутри каждого облака). Мы хотим показать, что из множества S в его дополнение S “ V zS ведёт не менее 64 p2dq|S| рёбер. Мы докажем даже немного более сильное утверждение: нужное нам число рёбер из S в S можно набрать, рассматривая либо только сплошные рёбра, либо только пунктирные рёбер.

По определению подстановочного произведение множество всех вершин G r H состоит из n облаков по D вершин в каждом. Обозначим эти облака V1,..., V n, и Si :“ S X Vi.

Назовём облако Vi насыщенным для S, если |Si | p1 qD; в противном случае назовём облако ненасыщенным. Разделим S на две части: множество Sнасыщ (вершины, лежашие в насыщенных облаках) и Sненасыщ (вершины, лежашие в ненасыщенных облаках).

Первый случай: предположим, что |Sненасыщ | |S| и оценим число рёбер в EpS, Sq в этом предположении. В этом случае мы подсчитаем число

–  –  –

и, соответственно, rчисло ненасыщенных облаковs n.

Это значит, что rчисло ненасыщенных облаковs rчисло насыщенных облаковs.

Теперь воспользуемся тем, что в исходном графе G коэффициент рёберного расширения равен. Заключаем, что число сплошных рёбер (с учётом кратности), ведущих из насыщенных облаков в ненасыщенные, не меньше

–  –  –

• во-вторых, вычтем число сплошных рёбер, у которых один из концов лежит в ненасыщенном облаке Vi, но при этом попадает в множество Si Vi ; таких рёбер заведомо не больше

–  –  –

Глава 5 Экспандеры на группах

5.1 Графы Кэли: определение и примеры В этом разделе мы определим графы Кэли и приведём примеры спектрального анализа таких графов.

Пусть H произвольная группа, а S H симметричное множество элементов группы (если h P S, то h1 P S). Графом Кэли CpH, Sq называется граф, вершинами которого являются все элементы группы H; вершины v и w соединяются (неориентированным) ребром, если v “ wh для некоторого h P S. Поскольку множество S симметрично, данное определение корректно (если v “ wh для некоторого h P S, то w “ vh1 ).

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

Петли в графе Кэли имеются (причем одновременно у всех вершин), если единичный элемент группы принадлежит S.

Пример 1. H произвольная группа, S “ H.

Графом Кэли CpH, Sq будет полный граф с |H| вершинами (с петлями).

Пример 2. H “ Zn (группа вычетов по модулю n с операцией сложения), S “ t1, 1u.

Графом Кэли CpH, Sq будет цикл длины n.

Пример 3. H “ Zk ; S состоит из естественных образующих группы:

S “ tei “ p0, 0,..., 0, 1, 0,..., 0q, i “ 1,..., nu (у ei единица стоит в позиции номер i; остальные координаты нулевые). Графом Кэли CpH, Sq будет граф рёбер n-мерного гиперкуба.

Для спектрального анализа графа Кэли полезно рассмотреть неприводимые представления группы H. Для конечных абелевых групп нужно изучить характеры H.

Определение 6 Характерами группы H называют гомомомерфизмы в мультипликативную группу комплексных чисел : H C.

Напоминание из курса алгебры (свойств характеров):

• У каждой группы есть тривиальный характер, тождественно равный единице.

• Если 1, 2 характеры абелевой группы H, то их покомпонентное произведение 1 phq2 phq тоже является характером; комплексное сопряжения характера также будет характером.

–  –  –

Замечание: В данном случае мы рассматриваем матрицу графа как линейный оператор над полем комплексных чисел. Так что координаты собственных векторов, которые мы вычислим, могу быть, вообще говоря, комплексными. Однако все собственные числа окажутся действительными числами.

Нам это известно заранее собственные числа всякой матрицы графа обязаны быть действительными числами, поскольку такая матрица симметрична. Для графов Кэли данный факт можно независимо доказать с помощью теоремы 13. В самом деле, поскольку множество S симметрично, для каждого характера сумма phq является сопряженной к самой себе, т.е.

hPS будет действительным числом.

–  –  –

Тем самым, теорема доказана.

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

Ещё раз о Примере 2. Рассмотрим более подробно граф из Примера 2 на с. 60. Характер группы Zn однозначно определяется его значением на элементе 1 (при этом характер должен отобразить элементы группы в корни из единицы степени n). Таким образом, мы получаем n характеров k, определяемых условием k p1q “ e2ki{n Соответственно, собственные числа графа равны

–  –  –

Cобственные числа этого графа Кэли равны b1...bn “ rчисло нулей в строке b1... bn s rчисло единиц в строке b1... bn s т.е. собственными числами будут значения n, n 2, n 4,..., n (кратности собственных чисел будут равны соответствующему биномиальному коэффициенту).

Мы видим, что максимальное собственное число данного графа равно степени графа n (степень каждой вершины равна n); имеется собственное число n (граф двудольный); следующее по абсолютной величине собственное число равно n p1 2{nq.

Упражнение 27 Опишите графы Кэли для следующих групп:

(а) H “ Z6, S “ t3u;

(б) H “ Z6, S “ t2, 2u;

(в) H есть группа симметрий квадрата, а S состоит из двух элементов: симметрии относительно вертикальной оси квадрата и симметрией относительно главной диагонали.

Упражнение 28 Покажите, что оценка коэффициента вершинного расширения для спектрального экспандера hV pHq dpHq из следствия 2 на стр. 24 является точной (в общем случае константу 2 в правой части неравенства нельзя уменьшить).

Указание: рассмотрите граф рёбер n-мерного гиперкуба.

Далее в этой главе мы рассмотрим несколько примеров применения описанной техники мы рассмотрим графы Кэли, являющиеся спектральным экспандерами с хорошим соотношением параметров. Более глубокое обсуждение данной техники можно найти в [2, 19]. Отметим также, что экспандеры, полученные из графов Кэли, обладают дополительными свойствами симметрии, которые могут оказаться полезными в приложениях (см., например, [37]).

Линейное пространство как экспандер 5.2 В этом разделе мы пишем конструкцию, напоминающую экспандер на плоскости из раздела 4.5. Мы покажем, как построить экспандер из конечномерного линейного пространства над конечным полем.

Пусть F есть поле из q “ 2t элементов. Рассмотрим d-мерное линейное пространство Fd над этим полем. Точки этого пространства будут вершинами графа. Нам будет удобно представлять эти точки в координатном виде, как pa0, a1,..., ad1 q P Fd.

Мы соединяем рёбрами каждую вершину pa0, a1,..., ad1 q со всеми вершинами вида

pa0, a1,..., ad1 q ` py, xy, x2 y,..., xd1 yq.

Таким образом, степень каждой вершина равна q 2, и выходящие из каждой вершины рёбра естественным образом индексируются парами px, yq P F2.

Заметим, что определение симметрично (не нужно отдельно учитывать рёбра обратные к уже описанным). Обозначим описанный граф LSpq, dq.

Теорема 14 Граф LSpq, dq является спектральным pq d, q 2, pd 1q{qq-экспандером.

Доказательство: Заметим, что описанный граф является графом Кэли.

Группой в данном случае будет линейное пространство Fd с обычной операцией сложения, а в качестве S мы возьмём множество всех векторов

–  –  –

Если pc pxq “ 0, то значение p1qLpypc pxqq “ 1 для всех y, так что каждое такое значение x даёт вклад в сумму, равный q. Если же pc pxq “ 0, то произведение y pc pxq пробегает все q элементов поля, и среди соответствующих p1qLpypc pxqq встречается равное число `1 и 1. Таким образом, общий вклад этих слагаемых в сумму (5.2) равен нулю.

Таким образом, c0,...,cd1 “ q rчисло нулей многочлена pc pxqs. Тривиальный многочлен (все коэффициенты которого равны нулю) тождественно равен нулю во всех точках поля; это соответствует тому, что 0,...,0 “ q 2.

У всех остальных многочленов pc pxq число нулей не превосходит d 1.

Следовательно, все собственные числа кроме одного не превосходят pd1qq.

Теорема доказана.

Упражнение 29 Дайте прямое доказательство того, что векторы (5.1) попарно ортогональны и являются собственными векторами матрицы графа.

Упражнение 30 Докажите, что для любого 0, для всякого целого r и всех достаточно больших q “ 2t граф LSpq, rq имеет коэффициент рёберного расширения не меньше 2.

Граф LSpq “ 2t, dq даёт пример простой и алгоритмически эффективной конструкции экспандера с хорошей оценкой для второго собственного числа. К сожалению, у этого графа степень не ограничена: если мы хотим поддерживать для второго собственного числа оценку pr 1q{q (для некоторой константы ), то с ростом числа вершин приходится увеличивать значение q, а значит и степень графа q 2.

Однако из графов LSpq, dq можно построить экспандеры с ограниченной степенью, если воспользоваться подстановочным произведением. При этом не требуется сложная рекурсивная конструкция подстановочное произведение достаточно применить лишь дважды! Ниже мы опишем данную конструкцию.

Пусть q “ 2t, r “ pq 4 q, и n “ q 4r (обратим внимание, что для выбранных параметров q “ Op nq). Мы опишем явную (в сильном смысле) конструкцию экспандера с n вершинами, со степенью Op1q и коэффициентом рёберного расширения не меньше некоторого 0.

Конструкция будет использовать в качестве строительных блоков следующую тройку графов:

• G1 : граф степени 3 с q 2 вершинами, с коэффициентом рёберного расширения 1 для некоторой абсолютной константы 1 0 (мы знаем, что такой экспандер существует, см. упражнение 4 на с. 9, и найти такой граф можно перебором за время q Opq q “ polypnq),

• G2 : граф LSpq, 6q; в этом графе q 6 вершин, степень равна q 2, коэффициент рёберного расширения не меньше 1{4,

• G3 : граф LSpq 4, r 8q; в этом графе q 4r8 вершин, степень равна q 8, коэффициент рёберного расширения не меньше 1{4.

Теперь рассмотрим граф

–  –  –

Из определения сбалансированного подстановочного произведения следует, что мы получили граф с n “ q 4r вершинами степени 12. Теорема 12 гарантирует, что коэффициентом рёберного расширения полученного графа не меньше некоторого числа 0 (не зависящего от n).

Упражнение 31 Докажите, что построенный граф является спектральным pn “ q 4r, 12, q-экспандером для некоторой константы 0, не зависящей от n.

Графы Рамануджана 5.3 Напомним, что в любом регулярном графе степени d второе по абсолютной величине собственное число не может быть меньше 2 d 1 op1q, см.

раздел 3.6.

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

величине собственное число ниже границы 2 d 1, заслуживают особого внимания это экспандеры с максимальным возможным спектральным зазаором. Такие графы называют графами Рамануджана.

Любоцкий, Сарнак, Филлипс [12] и Маргулис [13] независимо указали явную (и алгоритмически эффективную) конструкцию графов Кэли, являющихся графами Рамануджана. Таким образом, была получена эффективная конструкция спектрального экспандера практически с наилучшими возможными параметрами. Ниже мы опишем эту конструкцию (без доказательства оценки для второго собственного числа).

Пусть p и q простые числа, p “ 1 mod 4 и q “ 1 mod 4. В качестве группы G возьмём P GLp2, Zq q, т.е. невырожденные матрицы 2 2 над полем вычетов по модулю q, профакторизованные по отношению пропорциональности (с обычной операцией матричного умножения).

Далее мы зададим в этой группе симметричное множество S. Зафиксируем такое целое i, что i2 “ 1 mod q.

Упражнение 32 Докажите, что такое число i существует.

Можно доказать (с помощью теоремы Якоби о представлении числа в виде суммы четырёх квадратов), что имеется ровно pp ` 1q целочисленное решение уравнения a2 ` a2 ` a2 ` a2 “ p такое, что a0 положительно и нечётно, а a1, a2, a3 чётны. Каждой такой четвёрке сопоставим матрицу a0 ` ia1 a2 ` ia3 A“.

a2 ` ia3 a0 ia1 Эти матрицы и образуют множество S.

Упражнение 33 Проверьте, что все матрицы указанного вида невырождены (их определитель не сравним с нулём по модулю q) и никакие две из них не пропорциональны друг другу, т.е. все эти матрицы задают разные элементы группы P GLp2, Zq q.

Нетрудно понять, что граф Кэли CpG, Sq состоит из pq 3 q вершин, и степень каждой вершины равна pp ` 1q. Свойства данного графа зависят от соотношения p и q. Рассмотрим случай, когда p является квадратичным вычетом по модулю q. Тогда полученный граф Кэли состоит из двух связных компонент (в одной компоненте лежат матрицы, определитель которых является квадратичным вычетом, а в другой матрицы с определителем, являющимся квадратичным невычетом по модулю q). Обозначим X p,q компоненту связности полученного графа. Можно доказать, что у X p,q ?

второе по абсолютной величине собственное число не превосходит 2 p, т.е.

это граф Рамануджана. Однако доказательство этого факта непросто и использует нетривиальную алгебраическую технику. Полное доказательство этой теоремы можно найти в [3].

Экспандер Маргулиса 5.4 В этом разделе мы изложим ещё одну явную конструкцию однородного экспандера. Граф в этой конструкции определяется чрезвычайно просто, и его удобно использовать на практике. Данная конструкция является незначительной модификацией исторически первой явной конструкции экспандера, предложенной Г.А. Маргулисом в начале 1970-х, [10]. Однако доказательство оценки второго собственного числа значительно отличается от оригинального доказательства Маргулиса.

Предлагаемая техника доказательства представляет самостоятельный интерес. Она использует преобразование Фурье. Идея доказательства была предложена Габбером и Галилом [17], а затем упрощена в [18]. Мы следуем изложению доказательства из [1]. К сожалению, несмотря на все упрощения, доказательство содержит некоторый магический трюк, который затрудняет перенос этого рассуждения на другие конструкции экспандеров.

5.4.1 Метод преобразования Фурье Напомним, что характерами группы называют гомоморфизмы из этой группы в мультипликативную группу комплексных чисел. В этом разделе нас будут интересовать характеры группы Z2, т.е. отображения n

–  –  –

Упражнение 34 Докажите свойства преобразования Фурье (а-д) самостоятельно (либо вспомните эти доказательства, если вы изучали преобразование Фурье в курсе анализа).

–  –  –

Это неравенство очевидно верно при “ 8 (неравенство Коши–Буняковского).

Но нам нужно доказать (5.3) для некоторого 8. Это значит, что замена модуля косинусов на единицу была слишком грубой ценкой. Нам нужно существенно использовать то, что значения косинусов в некоторых точках намного меньше единицы.

Идея доказательства основана на элементарном арифметическом неравенстве: для любых действительных чисел A, B, выполнено неравенство 2AB A2 ` B. (5.4) Мы будем применять это неравенство для каждого произведения вида Gpzq GpT2 zq или Gpzq GpT1 zq из левой части (5.3). Полагая в (5.4) A “ Gpvq и B “ Gpwq мы будем получать

–  –  –

2, которая в свою очередь меньше 4).

В данном случае удобно представлять набор остатков по модулю n в виде Zn “ tn{2 ` 1,..., 1, 0, 1,..., n{2u (для нечётных n нужно добавить округление для концов интервала). Таким образом, каждый из двух аргументов есть целочисленная точка в квадрате со стороной длины n и с центром в точке p0, 0q.

Для точек z “ pz1, z2 q, достаточно далёких от начала координат, хотя бы одно из значений | cos z1 |, | cos z1 | будет отделено от нуля, и беспокоиться n n не о чем (если хотя бы одна из компонет v, w достаточно далека от точки p0, 0q, можно положить pv, wq “ 1). Но для точек z в окрестности нуля значения обоих косинусов становятся близки к единице. Поэтому для того, чтобы сумма (5.5) была отделена от 4, нужно удачно подобрать функцию.

Мы переходим к ключевому моменту доказательства.

Определение А: Будем называть близкой окрестностью нуля множество всех таких v “ pv1, v2 q, что

–  –  –

и хотя бы одно их этих двух неравенств является строгим.

Теперь мы готовы определить функцию pv, wq:

• если v лежит в близкой окрестности нуля и w v, то положим pv, wq “ 0,

• если w лежит в близкой окрестности нуля и v w, то положим pv, wq “ 1{0,

• во всех остальных случаях положим pv, wq “ 1.

Какими могут быть значения в сумме (5.5) в случае, когда pz1, z2 q лежит в близкой окрестности нуля? Нетрудно проверить, что в этом случае из четырёх значений либо два равны 0, а два других равны 1{0, либо три равны 1{0, и только одно равно 0. Положив 0 “ 5{4, мы получаем в обоих случаях сумму меньше 4. Лемма доказана.

Глава 6 Эффективные конструкции двудольных экспандеров Напомним, что в теореме 2 мы неконструктивно доказали существование двудольных экспандеров. При этом для любого 0, любых целых N и K N мы получали экспандер с параметрами pN, M, D, K, q, где

–  –  –

(константы в Opq зависят от ).

Известные методы не позволяют строить экспандеры с такими параметрами эффективно. Однако существует несколько явных конструкций, которые позволяют за полиномиальное получить двудольные экспандеры с параметрами, довольно близкими к оценке (6.1). В этом разделе мы подробно рассмотрим одну из таких конструкций и коротко упомянем ещё одну.

–  –  –

(константа в обозначении Opq здесь зависит от ). Видно, что в (6.2) и степень графа, и число вершин в правой доле несколько избыточно по сравнению с (6.1). Варьируя значение параметра, мы можем по своему желанию перераспределять эту избыточность между значениями D и M.

Приведём пример. Если мы хотим, чтобы свойство расширения выполнялось для множеств размера до K “ N 0.1, то неконструктивное доказательство гарантирует существование экспандера с D “ Oplog N q и M “ OpN 0.1 log N q, а предлагаемая эффективная конструкция позволяет получить экспандер с D “ Oppolyplog N qq и, скажем, M “ OpN 0.10001 polyplog N qq.

Подчеркнём ещё раз, что предлагаемая конструкция работает для любых (сколь угодно малых) 0.

Конструкция экспандера, которую мы сейчас опишем, задаётся следующим набором параметров:

• конечное поле Fq (число q “ |Fq | есть степень простого числа),

• натуральное число n, неприводимый многочлен hpyq степени n над полем Fq,

• натуральные числа m и t.

Ниже мы обсудим, как именно следует выбирать эти параметры, чтобы получить граф с нужными нам свойствами. Теперь перейдем к описанию конструкции объясним, как будет устроен граф.

Левая доля графа: Будем отождествлять вершины левой доли графа с многочленами ppxq степени не выше n над полем Fq. (Не обязательно считать вершинами все такие многочлены можно взять только некоторые из них.) Понятно, что число вершин в левой доле графа не превосходит q n.

Правая доля графа: Будем отождествлять вершины правой доли графа с Fm`1. Таким образом, число вершин в правой доле графа равно q m`1.

q Рёбра графа: Из каждой вершине левой доли графа будет выходить q рёбер; рёбра каждой вершины будет удобно индексировать элементами поля Fq. Правый конец каждого такого ребра мы будем вычислять с помощью отображения F : Fn Fq Fq, m`1 q

–  –  –

(мы находим степени многочлена ppyq, приводим их по модулю h, а затем вычисляем все эти многочлены в точке y).

Замечание: Отображение F полезно представлять себе как кодирование.

При этом коэффициенты многочлена ppyq играют роль сообщения, а набор значений F pp, yq для всевозможных y играет роль кодового слова.

Данная конструкция возникла в работе Варди и Парвареша [21] как обобщение классического кода Рида–Соломона. В [22] было замечено, что взяв код Варди–Парвареша с необычными значениями параметров, мы получим экспандер. Дело в том, что код Варди–Парвареша обладает некоторыми замечательными свойствами этот код допускает эффективное декодирование списком (см. [26]). По существу, именно возможность декодирования списком и гарантирует, что построенный граф окажется хорошим экспандером. Но формально мы не будем опираться на какие-либо свойства кода Варди–Парвареша мы дадим прямое доказательство нужных нам комбинаторных свойств отображения F.

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

Утверждение 8 Если A некоторое множество вершин левой доли построенного графа, состоящее из не более, чем tm вершин, то множество его соседей достаточно велико:

–  –  –

Доказательство: Обозначим B :“ pAq множество вершин левой доли графа, являющихся соседями A, и K “ |A|. Нам нужно доказать, что B состоит не менее, чем из K вершин, где

–  –  –

(Здесь qj и Sj некоторые многочлены одной и m переменных соответственно.) Заметим, что хотя бы один из многочленов qj не делится на hpyq (в противном случае можно было бы поделить Q на h и понизить степень многочлена по переменной y).

Теперь возьмём произвольную вершину из множества A; ей соответствует некоторый многочлен ppyq. Подставим в Q вместо y1,..., ym многочлены pj pyq, определённые равенствами (6.3). Заметим, что полученный в результате многочлен одной переменной y

–  –  –

делится на многочлен hpyq.

Теперь посмотрим на это утверждение как на уравнение в поле Fq {hpyq (в поле разложения многочлена hpyq, т.е. в поле размера q n, элементами которых являются многочлены над Fq, приведённые по модулю hpyq). Рас

–  –  –

(последнее равенство вытекает из определения многочлена Rj, в котором мы использовали разложение j по степеням t). Важно, что этот многочлен не является тривиальным (не все его коэффициенты равны нулю в в поле Fq {hpyq), и степень этого многочлена строго меньше K.

Наше замечание о том, что многочлен (6.6) делится на hpyq, можно переформулировать так: для каждого из многочленов ppyq, соответствующих вершинам графа из множества A, в поле Fq {hpyq выполнено равенство Q ppq “ 0. Таким образом, Q имеет не меньше |A| нулей. Но число нулей многочлена не может быть больше его степени. Получаем |A| K, что противоречит выбору K. Теорема доказана.

Теперь, подбирая подходящие значения параметров, мы получим требуемый экспандер.

Теорема 16 Для любого 0 и 0 существует алгоритм, который для любого N и любого K N находит за полиномиальное по N время некоторый двудольный экспандер с параметрами pN, M, D, K, q, где 1 ` D “ O pplog N qplog Kqq1` и M “ O D2 K 1`.

–  –  –

Таким образом, мы построили экспандер с требуемым свойством расширения.

Описанная конструкция эффективна (матрицу графа можно выписать за время polypN q) поскольку все арифметические операции в поле и поиск неприводимого многочлена h можно произвести за полиномиальное по n время.

–  –  –

6.2 Конструкция с зигзаг-произведением Параметры двудольного экспандера из конструкции их раздела 6 далеки от оптимальных в случае, когда значения параметров N и K (размер левой доли графа и максимальный размер множества, для которого должно быть выполнено свойство расширения) близки (скажем, N {K “ const). Но как раз для таких значений параметров хорошие оценки даёт конструкция из работы [23]. Эта конструкция использует зигзаг-произведение, перенесённое на (неоднородные) двудольные граф. Она позволяет для любых фиксированных 0 и t 1 и для всех натуральных n эффективно строить двудольный экспандер с параметрами

–  –  –

где d “ O plog tq и k “ n t d Op1q. Мы не приводим доказательства этого результата и отсылаем заинтересованного читателя к оригинальной статье [23].

Глава 7

Применение экспандеров:

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

Предположим, что для решения некоторой задачи имеется полиномиальный вероятностный алгоритм, который на любом входе x с вероятностью не менее 1 возвращает правильный ответ. (Мы предполагаем, что 1{2.) Чтобы уменьшить вероятность ошибки алгоритма, можно параллельно запустить имеющийся алгоритм t раз на независимых значениях датчика случайных битов, а затем из полученных t результатов выбрать наиболее часто случающийся. У нового алгоритма вероятностью ошибки не будет превосходить ct для некоторого c 1. Таким образом, сделав число итераций t достаточно большим, можно сделать вероятность ошибки меньше любого наперёд заданного числа. Можно даже сделать вероятность ошибки экспоненциально убывающей (с ростом длины входа). При этом время работы алгоритма будет оставаться полиномиальным. Очевидным недостатком этого подхода является рост числа используемых случайных битов их число умножается на t.

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

7.1 Уменьшение вероятности ошибки алгоритма без увеличения числа случайных битов В этом разделе мы рассмотрим самый простой способ получения из экспандера псевдослучайных битов. Мы покажем, как уменьшить вероятности ошибки вероятностного алгоритма без увеличения числа используемых случайных битов. Мы ограничимся рассмотрением алгоритмов с односторонней ошибкой. Напомним стандартное определение класса задач, для которых существует полиномиальный вероятностный алгоритм с односторонней ошибкой.

Определение 7 Язык L принадлежит сложностному классу RP, если существует полиномиальный алгоритм A такой что

1. если x P L, то для всех r P t0, 1upolypnq Apx, rq “ 1

2. если x R L, то Apx, rq “ 1 может выполняться не более чем для 50% от числа всех r P t0, 1upolypnq Покажем, что для любого 0 всякий полиномиальный вероятностный алгоритм A можно переделать в другой полиномиальный вероятностный алгоритм A1 так, чтобы вероятность ошибки уменьшилась с 1{2 до, а число используемых случайных битов при этом не изменится.

Пусть исходный алгоритм использует k “ kpnq случайных битов для вычислений на входах длины n. Зафиксируем однородный p2k, d, q-экспандер1 G для некоторого 0. Индекс (номер) каждой вершины в этом графе записывается последовательностью из k нулей и единиц. Таким образом, мы можем отождествить вершины G и наборы из k битов.

Новый алгоритм действует следующим образом: выбирается случайная вершина v графа (для этого требуется k случайных битов); затем исходный алгоритм A последовательно запускается на всех d наборах случайных битов, соответствующих соседям вершины v в графе. Если все полученные ответы равны 1, новый алгоритм также возвращает единицу; в противном случае возвращается ноль.

Покажем, что у нового алгоритма вероятность ошибки не превосходит 2p1`q. Обозначим B “ Bpxq множество всех плохих (для данного x) вершин графа множество таких вершин w из правой доли графа, которые соответствуют неверному ответу старого алгоритма на входе x. Поскольку вероятность ошибки старого алгоритма не превсходит 1{2, число вершин в Bpxq не превосходит половины от числа всех вершин графа, т.е., |B| 2k1.

1 Напомним, что у нас есть эффективные конструкции экспандеров с 2k вершинами для всех достаточно больших k, см. упражнение 25 на стр. 52 и замечание перед ним.) Без ограничений общности мы предполагаем, что для интересующего нас числа k. Для чётных k экспандеры с 2k вершинами также можно строить с помощью конструкции из раздела 5.4.

Аналогично, обозначим C “ Cpxq множество таких вершин v графа, которые для которых новый алгоритм даёт неверный ответ на входе x. Очевидно, C состоит из вершин, все соседи которых лежат в B.

2k Предположим, что C содержит не менее 2p1`q вершин. Произвольным образом выберем из множества C некоторое подмножество, состоящее ровно 2k из 2p1`q вершин и назовём его C 1. Из определения экспандера следует, что |pCq| p1 ` q|C 1 | “ 2k {2.

Это противоречит тому, что все соседи C 1 лежат в B.

Таким образом, мы построили алгоритм, в котором ошибка снизилась с 2 до 2p1`q. Покажем, как понизить вероятность ошибки ещё больше.

Зададимся некоторым числом t и построим алгоритм, вероятность ошибки которого меньше 2p1`qt. В новом алгоритме мы выбираем случайную вершину v графа (для этого по-прежнему требуется k случайных битов);

затем запускаем исходный алгоритм A на всех наборах случайных битов, соответствующих вершинам w графа, в которые можно попасть из v за t шагов (таких вершин заведомо не более dt ). Если все полученные ответы равны 1, новый алгоритм также возвращает единицу; в противном случае возвращается ноль.

Оценим вероятность ошибки нового алгоритма. Снова обозначим C “ Cpxq множество таких вершин v графа, для которых новый алгоритм даёт неверный ответ на входе x. Предположим, что C содержит не менее 2p1`qt вершин. Выберем среди них подмножество, состоящее из ровно 2p1`qt вершин и назовём его C 1. Из определения экспандера следует, что | ppp... p C 1 q...qqq| p1 ` qt |C 1 | “ n{2 loooooomoooooon t итераций Это противоречит тому, что все цепочки из t рёбер, начинающиеся вершиной из C 1, обязаны заканчиваться вершиной из B.

Выбирая параметр t достаточно большим, мы получим алгоритм с вероятностью ошибки менее 2p1`qt. При этом значение t зависит от желаемой вероятности ошибки, но не зависит от размера входа n.

Остаётся обсудить время работы построенного алгоритма. Мы используем старый алгоритм как чёрный ящик и вызываем его (на разных наборах случайных битов) dt раз. Поскольку d и t – некоторые константы (не зависящие от входа алгоритма), и исходный алгоритм A работал за полиномиальное время, можно заключить, что все требуемые вызовы требуют лишь полиномиального времени.

Однако кроме нескольких вызовов старого алгоритма нам требуется производить некоторые манипуляции с графом G. Чтобы иметь возможность делать это за полиномиальное время, нам нужна явная конструкция экспандера.

Более того, нам нужен экспандер явный в сильном смысле:

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

7.2 Блуждание на экспандере как генератор псевдослучайных битов: вероятностные алгоритмы с односторонней ошибкой.

Мы в этом разделе мы рассмотрим другой подход у улучшению качества работы вероятностного алгоритма. Здесь мы по-прежнему рассматриваем только алгоритмы с односторонней ошибкой. Мы предполагаем, что если алгоритм выдает ответ 1, то он заведомо правильный, а выдаваемый ответ 0 может быть ошибочным. При этом для любого входа вероятность ошибки ограничена некоторым 1.

Чтобы уменьшить вероятность ошибки алгоритма, достаточно последовательно запустить данный алгоритм t раз на независимых значениях датчика случайных битов. Если в произведенных параллельных вычислениях хотя бы один из полученных результатов окажется раным 1, то в качестве ответа нужно выдать 1. Если же все t результатов равны 0, то в качестве ответа нужно выдать 0. Нетрудно видеть, что вероятность ошибки после t-кратного повторения уменьшилась с до J. Однако и число используемых случайных битов выросло в t раз. Далее мы покажем, как добиться экспоненциального уменьшения вероятности ошибки, используя значительно меньше случайных битов.

Построим спектральный p2n, d, q-экспандер (здесь n число случайных битов, которое требовалось исходному вероятностному алгоритму). Выберем случайно вершину графа x0, а затем сделаем t шагов случайного блуждания по графу, x0 x1... xt. Затем запустим t ` 1 копию старого алгоритма, используя индексы вершин x0, x1,..., xt как наборы случайных битов. Как и прежде, если в произведенных параллельных вычислениях хотя бы один из полученных результатов окажется раным 1, то в качестве ответа нужно выдать 1; если же все t результатов равны 0, то в качестве ответа нужно выдать 0.

Если исходный алгоритм был полиномиальным, то и новый алгоритм будет работать за полиномиальное время. Разумеется, нужно, чтобы конструкция используемого p2n, d, q-экспандера была явной в сильном смысле (по номеру вершины можно эффективно найти номера её соседей).

Сколько же случайных битов использует новый алгоритм? Чтобы задать на графе путь длины t, нам нужно n ` Optq случайных битов. Это много лучше, чем tn случайных битов, которые были нужны для наивного t-кратного повторения исходного алгоритма. При этом согласно утверждению 5 вероятность ошибки нового алгоритма будет не больше p ` qt.

Если взять достаточно малым (напомним, что мы умеем строить спектральные экспандеры для сколь угодно малого параметра 0), то вероятность ошибки будет меньше ct для некоторого c 1, т.е. вероятность ошибки экспоненциально убывает с ростом t.

7.3 Блуждание на экспандере как генератор псевдослучайных битов: вероятностные алгоритмы с двусторонней ошибкой.

Рассмотрим теперь более общий случай будем считать, что исходный вероятностный алгоритм может выдавать как положительные, так и отрицательные ложные ответы. При этом для любого входа вероятность ошибки ограничена некоторым 1{2.

Как и раньше, чтобы уменьшить вероятность ошибки, можно последовательно запустить исходные алгоритм t раз на независимых значениях датчика случайных битов, а затем выбрать из t полученных экземпляров ответа самый часто встречающийся. С ростом t вероятность ошибки будет экспоненциально убывать. Однако число используемых случайных битов также увеличивается в t раз.

Как и в случае алгоритма с односторонней ошибкой, мы можем добиться экспоненциального убывания вероятности ошибки, более экономно расходовать случайные биты. Снова рассмотрим спектральный p2n, d, q-экспандер (где n число случайных битов, которое требовалось исходному вероятностному алгоритму). Сделаем t шагов случайного блуждания по графу, x0 x1... xt. Затем запустим t ` 1 копию старого алгоритма, используя индексы вершин x0, x1,..., xt как наборы случайных битов. Среди полученных ответов нужно выбрать самый часто встречающийся; его-то мы и объявим результатом работы нового алгоритма.

Как и раньше, случайное блуждание задается n ` Optq случайными битами. А утверждение 6 позволяет оценить вероятность ошибки нового алгоритма. Она не превосходит p ` q|I|1 2t`1 p ` qpt1q{2, It0,...,tu, |I|t{2 т.е. для достаточно малых вероятность ошибки будет экспоненциально убывать с ростом t.

7.4 Алгоритм проверки связности графа с использованием логарифмической памятью Мы уже видели, что зигзаг-произведение позволяет собирать из маленьких экспандеров сколь угодно большие экспандеры с ограниченной степенью и достаточно малым вторым собственным числом. Теперь мы рассмотрим ещё одно замечательное одно применение этих операций. Мы докажем теорему о дерандомизации одного из самых знаменитых вероятностных алгоритмов алгоритма проверки s-t-связности в неориентированном графе (задача UPATH) с логарифмической памятью.

Задача UPATH: Задан неориентированный граф G “ pV, Eq, в котором выделены две вершины s, t P V. Требуется выяснить, есть ли в графе путь из вершины s в вершину t.

Теорема 17 Задача UPATH может быть решена вероятностным алгоритмом с логарифмической памятью.

Вероятностный алгоритм для решения задачи UPATH устроен очень просто: нужно сделать N “ polyp|V |q (выбор полинома мы уточним чуть позже) шагов случайного блуждания по графу, начав с вершины s. Если за N шагов нам удастся побывать в вершине t, мы точно знаем, что в графе есть путь из s в t. В противном случае мы полагаем, что такого пути нет.

В каждый момент работы алгоритма нам требуется помнить номер текущего шага блуждания (от 1 до N ) и номер вершины, в которой мы в данным момент находимся. Для хранения этой информации достаточно памяти размера Oplog |V |q.

Ясно, что если пути из s в t нет, то алгоритм выдаст правильный ответ.

Остаётся оценить вероятность другой ошибки: путь из s в t существует, но за N шагов блуждания мы его не обнаружим. Без ограничения общности можно считать, что граф регулярен и недвудолен (мы всегда можем добиться этого, добавив в граф некоторое количество петель). Далее покажем, что при случайном блуждании по связному однородному и недвудольному графу распределение вероятностей на вершинах быстро приближается к однородному.

Ключевое свойство графа:

Лемма 9 В d-регулярном связном и недвудольном графе с n вершинами щель между первым и вторым по абсолютной величине собственными числами не может быть меньше 1{ polypnq, т.е.

–  –  –

для некоторой константы c (не зависящей ни от n, ни от d).

Доказательство леммы: По условию граф является связным, так что собственное число d имеет кратность 1. Далее, если у графа есть отрицательные собственные числа, мы перейдём от исходного графа G к его квадрату G2. При возведении в квадрат все собственные числа также возведутся в квадрат и станут положительными (щель между первым и вторым по модулю собственным числом также измениться в полином раз умножится на Opdq). Важно отметить, что поскольку исходный граф G не был двудольным, в его квадрате максимальное собственное число имеет кратность 1 (связный недвудольный граф при возведении в квадрат остаётся связным).

–  –  –

если s и t принадлежат одной компоненте связности, то вероятность попасть через polypnq шагов в вершину t будет близка к 1{n. Если же увеличить число шагов ещё в полином раз, то вероятность хотя бы раз побывать в t станет близка к единице. Теорема доказана.

Далее мы покажем, как дерандомизовать алгоритм случайного блуждание на графе без значительного увеличения используемой памяти. Более формально, мы докажем следующую теорему.

Теорема 18 Задача UPATH может быть решена детерминированным алгоритмом с логарифмической памятью.

Прежде чем доказывать теорему, заметим, что мы уже умеем решать на логарифмической памяти задачу UPATH для pn, d, 0.99q-экспандеров. В самом деле, мы знаем, что диаметр такого экспандера равен Oplog nq. Мы можем перебрать все пути длины C log n с началом в вершине s и проверить, ведёт ли хотя бы один из них в t; такая проверка очевидно требует лишь логарифмической памяти (и полиномиального времени).

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

Доказательство теоремы: Мы предполагаем, что нам задан (в виде оракула) неориентированный граф G с n вершинами, без петель и параллельных рёбер. Далее мы построим на основе G несколько воображаемых графов; мы сможем моделировать блуждание по каждому из этих воображаемых графов с помощью исходного оракула и дополнительной памяти размера Oplog nq.

Воображаемый граф G1 : заменим в исходном графе каждую вершину vi степени di 3 на цикл длины di ; рёбра, входившие ранее в данную вершину мы по одному присоединим к вершинам этого цикла. Таким образом, в графе G1 степень каждой вершины не превосходит 3. Обозначим через n1 число вершин в G1 (это число не превосходит polypnq).

Воображаемый граф G2 : Добавим к каждой из вершин G1 нужное число петель так, чтобы получился D-регулярный граф для некоторого D “ d4 ;

целое число d мы выберем так, чтобы существовал спектральный экспандер H с параметрами pD “ d4, d, 0.01q.



Pages:   || 2 |
Похожие работы:

«С.С. Сурин В.Н. Семенов ДИЗЕЛЬ ЗиЛ 645 И ЕГО МОДИФИКАЦИИ ЭКСПЛУАТАЦИЯ, РЕГУЛИРОВКА, РЕМОНТ маленькие тайны большого завода Москва Легион-Автодата УДК 629.314.6 ББК 39.335.52 Т ISBN 5-88850-178-6 С.С. Сурин, В.Н. Семенов Д...»

«АО ЦЕНТРАЛЬНЫЙ ДЕПОЗИТАРИЙ ЦЕННЫХ БУМАГ ПРОТОКОЛ об итогах голосования на годовом общем собрании акционеров АО Центральный депозитарий ценных бумаг г. Алматы 14 июля 2011 года В настоящем протоколе используются следующие обозначения: Центральный депозитарий – акц...»

«Татьяна Мищенко, Ольга Белугина, Светлана Куркина, БГУ им. академика И. Г. Петровского, Брянск СИМВОЛИКА ЖЕНСКОЙ "ПОЧЕСТНОСТИ" В СВАДЕБНОМ ОБРЯДЕ ЖИТЕЛЕЙ ВОСТОЧНОГО ПОЛЕСЬЯ: АКЦИОНАЛЬНЫЙ И ВЕРБАЛЬНЫЙ АСПЕКТЫ Символика морально-нравственных устоев покол...»

«" " 170F. Hartmann (. ). (. ). : 72 170:.– :, 2014. – 180. ISBN 978-5-9795-1229-7 170.,,. :,.,,,,,,,.,,,.. 141.1(082) ©, 2014 ISBN 978-5-9795-1229-7 ©., 2014 Бог, который есть истина, познается нами в этой его истине, т.е. как...»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования "Нижневартовский государственный унив...»

«О. Мошников. Библиография произведений автора Поэзия Мошников, О.Э. Птица-ночь : стихи / О.Э Мошников; худож. Т.Г. Юфа. Петрозаводск : Файн Лайн, 1995. – 24 с. Мошников, О.Э. Духов камень / О.Э. Мошников. Петрозаводск : б.и., 1999. – 136 с. Мошников, О.Э. Солнечные...»

«Приложение № 1 Анализ и оценка мировых тенденций развития радиотехнологий и систем связи Анализ и оценка мировых тенденций развития радиотехнологий и систем связи Развитие радиотехнологий неразрывно связано с развитием систем радиосвязи и услуг связи. Совокупность РЭС, функционирующих на некоторой выбранной территории на...»

«Программа мероприятий Высокоширотной полярной экспедиции на Шпицберген в рамках проекта "Арктика – 2015" 3 АПРЕЛЯ ВНИМАНИЕ! Пароль на въезд через пост охраны – "АРКТИКА_2015" (автостоянка у Центрального музея ВОВ) 09-45 – Парк Победы, Поклон...»

«ПРИТЧИ ЧИТАТЕЛЮ ПЕРВОЙ КНИГИ Если мудрое слово услышит разумный, то он похвалит его и приложит к себе. Книга премудрости Иисуса сына Сирахова 21:18 Не думаете ли еще, что мы только оправдываемся перед вами? Второе послание Павла к Коринфянам 12:19 Приходилось ли нашему читателю хоть раз заблудиться в лесу? В какой момент ты, чи...»

«Четыре сезона КАЛЕНДАРЬ СОВРЕМЕННОГО САДОВОДА ЗАЩИТА сада и огорода от болезней и вредителей БИОМЕТОД Составитель С. О. Ермакова Москва, 2011 УДК 634 ББК 42.3 К17 Составитель С. О. Ермакова К17 Календарь современного садовода и огоро...»

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

«Должностная инструкция плотника жэу 25-03-2016 1 Пихты помогают перебеситься с аномалии. Общеизвестно, что пасечники неприменно не опыляются. Хаотичная всепластичность это обдуманно не меркнущее выжигание. Своекорыстная оборотистость тускнеет. Бодрствование это, по сути, неузнаваемая п...»

«Любимый Плата за подключение 0 Ежемесячная абонентская плата (включает 3 "любимых номера") 9 50.80 Международный доступ, Международный/национальный роуминг, Переадресация вызова, Ожидание/удержание Бесплатно вызова, конференц-связь...»

«36 Liberal Arts in Russia 2012. Vol. 1. No. 1 УДК 161 "СХОДНОЕ" И "ОБЩЕЕ". ПСЕВДОПОНЯТИЕ И ПОНЯТИЕ © В. В. Ильин Московский государственный университет им. М. В. Ломоносова Россия, 119991, ГСП-1, Ленинские горы, д.1, стр. 52, 2-ой учебный корпус Телефон: +7 (495) 939 21...»

«". И МУЗЫКА" Шульдишова А. А. (Донецк) УДК 821.161.1:7.037.2 А. БЛОК: ЖИЗНЕННЫЕ И ЛИТЕРАТУРНОМУЗЫКАЛЬНЫЕ РЕМИНИСЦЕНЦИИ КАК  МОТИВАТОРЫ ПОЭТИЧЕСКОГО ЦИКЛА "КАРМЕН" “. Недаром все его стихи поют”. Л. Дельмас [5, с. 68] Реферат.  Полемическое  острие  статьи  направлено  на  развенчание  неточных  пр...»

«Annotation Не ожидали, а в переплет попали. Две верные подруги отправились в туристический поход, а в итоге едва живыми оказались на инопланетном корабле! И кто о чем, а они сразу подумали: "Раз домой не отпустят, надо тут обживаться, а лучше — сразу замуж выходить!" А за кого выходить-то? Кругом о...»

«УРОВНЕМЕР УЛЬТРАЗВУКОВОЙ ВЗЛЕТ УР ИСПОЛНЕНИЯ УР-2хх РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ Часть I В17.00-00.00-20 РЭ Россия, Санкт-Петербург Система менеджмента качества ЗАО "ВЗЛЕТ" соответствует требованиям ГОСТ Р ИСО 9001-2008 (сертификат соответствия № РОСС RU.ИС09.К00816) и международному стандарту ISO 9001:2008 (се...»

«51065_HGN_RU.qxd:Blutdruckmessgert 09.02.2010 9:36 Uhr Seite 1 Измеритель артериального давления, автоматический на запястье Medisana HGN РУ № ФСЗ 2009/05332 Art. 51065 ИМ 24 Инструкция по применению Внимательно ознакомиться! 51065_HGN_RU.qxd:Blutdruckmessgert 09.02.2010 9:36 Uhr Seite 2...»

«Вісник ОНУ. Сер.: Географічні та геологічні науки. 2013. Т. 18, вип. 3(19) ISSN 2303-9914 УДК 631.4:631.459 СветличныйА.А., доктор геогр. наук, проф., ПятковаА.В., канд. геогр. наук, ПлотницкийС.В., доцент, ГолосовВ.Н., доктор геогр. наук, проф., ЖидкинА.П., канд. геогр. наук Одесский национальный...»

«/ УТВЕРЖДАЮ: Вице-губернатор председатель Правительства Самарской области Протокол № 46 заседания комиссии при Правительстве Самарской области по ведомственным целевым программам (далее комиссия) от 18 марта 2013 года Председательствовал: Нефёдов А.П. вице-губернатор председатель Правительства Самарской обл...»

«ГРАММАТИКОН – 2016 МОРФЕМИКА И МОРФОЛОГИЯ Задание №1 Определите суффикс в выделенном слове. Как по суффиксу можно догадаться, что означает выделенное слово? Назовите другие слова (5-6) с тем же суффиксом. У стены сарая стояла старая кабарга, а рядом с ней маленький ка...»

«УПОЛНОМОЧЕННЫЙ ГОСУДАРСТВОМ Акция "Один день с участковым"Наверное, никого из наших читателей не надо убеждать: – в том, что участковый – это самый близкий к населению представитель государственной власти в лице полиции;– в том, что указанные в контракте служебные...»

«ОБЪЕДИНЕННЫЙ ИНСТИТУТ ЯДЕРНЫХ ИССЛЕДОВАНИЙ ДУБНА ШШ1Ш1Ш1Ш1 13 8828 В.М.Гребенюк, В.Г.Зинов БЛОКИ ДЛЯ ВРЕМЕННОЙ СЕЛЕКЦИИ СИГНАЛОВ i Ранг публикаций Объединенного института ядерных исследований Препринты и сообщения Объединенного инстит...»








 
2017 www.kniga.lib-i.ru - «Бесплатная электронная библиотека - онлайн материалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.