Космические «промышленные» несбалансированные экспандеры

24

Я ищу несбалансированные расширители, которые "хороши" и "экономичны". В частности, двудольный лево-регулярный граф , , , с левой степенью является -расширителем, если для любого размером не более , число различных соседей в , по крайней мере, Известно, что вероятностный метод дает такой граф с и . Однако нужно| A | = n | Б | = m d ( k , ϵ ) S A k S B ( 1 - ϵ ) d | S | d = O ( log ( n / k ) / ϵ ) m = O ( k log ( n)гзнак равно(A,В,Е)|A|знак равноN|В|знак равномd(К,ε)SAКSВ(1-ε)d|S|dзнак равноО(журнал(N/К)/ε)O ( n d )мзнак равноО(Кжурнал(N/К)/ε2)О(Nd)пространство для хранения такого графика. Также необходимо получить доступ к этому хранилищу при выполнении чего-либо с графиком, что также может стоить. В идеале хотелось бы явной конструкции. Однако, насколько я знаю, известные конструкции достигают параметров, которые все еще несколько далеки от вышеупомянутых (по крайней мере, доказуемо так).

Мой вопрос: есть ли другие конструкции, возможно, не явные, которые достигают границ «ближе» к указанным выше, но используют «значительно меньше», чем пространство?О(Nd)

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

Вот пример конструкции типа (с). Возьмите случайных линейных хеш-функций (mod ) и соедините каждую вершину с . Я и мой ученик провели некоторые эксперименты на нем, и это, казалось, работало "отлично". Есть ли какие-либо теоремы или предположения об этой или связанных конструкциях?h i : [ n ] [ m ] m i h 1 ( i ) h d ( i )dчася:[N][м]мяh1(i)hd(i)

Благодарность!

Петр
источник
2
Это отличный вопрос, но, похоже, нет ответов! Никто не использует расширители, кроме как в качестве волшебной палочки, чтобы заставить доказательства работать? Я думал, что некоторые типы графов Рамануджана довольно просто построить.
Андрас Саламон
2
Рамануджановские графы действительно относительно легко построить, но они сбалансированы , т. Е. M = n.
Петр
Вы смотрели на конструкцию Гурусвами-Умань-Вадхан? Мне интересно, почему он не удовлетворяет вашим требованиям.
Zeyu

Ответы:

10

Eickmeyer и Grohe (2010) доказывают, что конструкция вашего кандидата может быть сделана явной: возьмите несколько линейно независимых линейных хеш-функций и соедините левые вершины с правыми вершинами , Эйкмейер и Гроэ показывают, что эта конструкция дает -экспандеры с левой степенью , всякий раз, когда является целым числом, множество левых вершин имеет размер , правый набор вершин имеет размер , а - простая степень. Хеш-функции выбираются таким образом, чтобы любойh 1 , , h d v h 1 ( v ) , , h d ( v ) ( k , ϵ ) d = k ( t - 1 ) / ( 2 ϵ ) t n = q t m = d q q > д ч 1 , , ч д тdчас1,...,часdvчас1(v),...,часd(v)(К,ε)dзнак равноК(T-1)/(2ε)TNзнак равноQTмзнак равноdQQ>dчас1,...,часdT из них линейно независимы.

Holger
источник
5

Я подумал, что, взглянув на обзоры / доклады Ави Вигдерсон, может помочь с вашим вопросом. Вот слайды из недавнего выступления: Учебное пособие по Expander, июнь 2010 . Строительство начинается на стр. 40.

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

Кава
источник