Я ищу несбалансированные расширители, которые "хороши" и "экономичны". В частности, двудольный лево-регулярный граф , , , с левой степенью является -расширителем, если для любого размером не более , число различных соседей в , по крайней мере, Известно, что вероятностный метод дает такой граф с и . Однако нужно| A | = n | Б | = m d ( k , ϵ ) S ⊂ A k S B ( 1 - ϵ ) d | S | d = O ( log ( n / k ) / ϵ ) m = O ( k log ( n)O ( n d )пространство для хранения такого графика. Также необходимо получить доступ к этому хранилищу при выполнении чего-либо с графиком, что также может стоить. В идеале хотелось бы явной конструкции. Однако, насколько я знаю, известные конструкции достигают параметров, которые все еще несколько далеки от вышеупомянутых (по крайней мере, доказуемо так).
Мой вопрос: есть ли другие конструкции, возможно, не явные, которые достигают границ «ближе» к указанным выше, но используют «значительно меньше», чем пространство?
Я ищу ответы в любой из этих трех категорий: (а) теоремы (б) гипотезы (в) наблюдения и «военные истории», такие как «мы сделали это, и это вроде как сработало (вроде)». Т.е. с «промышленными» экспандерами все в порядке. Я предпочитаю (а), чем (б) и (б), чем (в), но нищие не могут быть выбором :)
Вот пример конструкции типа (с). Возьмите случайных линейных хеш-функций (mod ) и соедините каждую вершину с . Я и мой ученик провели некоторые эксперименты на нем, и это, казалось, работало "отлично". Есть ли какие-либо теоремы или предположения об этой или связанных конструкциях?h i : [ n ] → [ m ] m i h 1 ( i ) … h d ( i )
Благодарность!
Ответы:
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, ... , чd v час1( v ) , … , чd( v ) ( к , ϵ ) d= k ( t - 1 ) / ( 2 ϵ ) T n = qT м = дQ Q> д час1, ... , чd T из них линейно независимы.
источник
Я подумал, что, взглянув на обзоры / доклады Ави Вигдерсон, может помочь с вашим вопросом. Вот слайды из недавнего выступления: Учебное пособие по Expander, июнь 2010 . Строительство начинается на стр. 40.
Что касается сложности пространства, я думаю, что это может быть полезно, если вы укажете операции, которые нужно выполнить на графике. Если я не ошибаюсь, некоторые конструкции позволяют работать как вычислительные окрестности в пространстве журналов.
источник