Как практически построить регулярные графы расширителей?

Мне нужно построить d-регулярный граф экспандера для некоторого небольшого фиксированного d (например, 3 или 4) из n вершин.

Какой самый простой способ сделать это на практике? Построение случайного d-регулярного графа, который оказался расширителем?

Я также читал о конструкциях Маргулиса и графах Рамануджана, которые являются расширителями и конструкцией, использующей зигзагообразный продукт. Википедия дает хороший, но очень краткий обзор: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Но какой метод выбрать на практике?

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

Может быть, проще построить d-регулярные двудольные графы расширителей?

У меня также есть другой вопрос: как насчет семей плохих d-регулярных расширителей? Имеет ли такое понятие смысл? Можно ли построить семейство d-регулярных графов (которые, конечно, связаны), которые настолько плохи, насколько это возможно в смысле расширителя?

Заранее спасибо.

graph-theory combinatorics cryptography discrete-mathematics expanders user2145167
источник

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

Юваль Фильмус

Можете ли вы дать имена или ссылки на конструкции? Под лучшими параметрами вы подразумеваете лучшее (граничное) расширение, я полагаю?

user2145167

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

Юваль Фильмус

Хорошо, для степени 3 пример Андра или случайные графики кажутся достаточно хорошими для моего приложения. Было бы интересно, в частности, в отношении случайных графов, построить семейство 3-рег графов, которое не является расширителем. Но это наверное очень сложно или не возможно?

user2145167

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

K_{4}

$K_4$

K_{4}

$K_4$

Юваль Фильмус

Ответы:

Если вы не возражаете против графиков с самоконтролями, вероятно, это «простейшее» семейство экспандеров, дающее экспандеры, которые являются 3-регулярными.

Начните с некоторого простого числа и постройте вершины с номерами от до . Для каждой вершины соедините с и по модулю . Также соедините с уникальной вершиной такой что . $p$ $0$ $p-1$ $u \ne 0$ $u$ $u-1$ $u+1$ $p$ $u$ $v$ $uv \equiv 1 \mod p$

Например, 7-вершинный граф в семействе представляет собой 7-цикл с вершинами, пронумерованными последовательно вокруг цикла; есть самопетли на , и ; наконец, есть аккорды, соединяющие и , и и . $6$ $0$ $1$ $3$ $5$ $2$ $4$

См. Https://mathoverflow.net/questions/124708/an-expander-graph для дальнейшего обсуждения и ссылок. Есть много более подробных указателей , выполнив поиск по " expander " в CSTheory , Math.SE и MO .

Как указывает Ювал Фильмус, случайная конструкция, скорее всего, даст лучшие результаты в целом, но, конечно, может не дать расширителя (особенно для небольших графиков).

Андраш Саламон
источник

Спасибо за замечание. Я уже искал расширители ранее на других сайтах, но не на МО, действительно, кажется, результатов больше.

user2145167

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

http://www.mathworks.com/matlabcentral/fileexchange/29786-random-regular-generator/content/randRegGraph/createRandRegGraph.m

Хода
источник