Уникальный соседский расширитель

Question

Я хочу решить проблему 4.10 от случайности Салил Вадхан. https://people.seas.harvard.edu/~salil/CS225 / Spring15 / PS3.PDF

Рассмотрим бипартский расширитель $ G $ с левой грамой $ D $ Так что каждое подмножество $ S $ из левых вершин с большинством $ k $ вершины имеют по крайней мере $ (1- \ epsilon) d | s | $ соседи.Тогда $ G $ также имеет свойство, которое имеет $ (1-2 \ Epsilon) D | S | $ Уникальные соседи.Уникальный смысл, что имеет ровно одну соответствующую вершину от $ S $ .

Я узнаю, что новый коэффициент расширения - $ (1-2 \ Epsilon) D= 2 \ CDOT (1- \ Epsilon) d -d $

.

Answer 1

Пусть $ s $ Будьте подмножества на большинстве $ K $ вершины. Пусть $ a_d $ - количество вершин на правой стороне, которые точно подключены к ровно $ d $ вершины в $ s $ . Поскольку левая степень составляет $ D $ , $$ \ sum_ {d \ geq 1} da_d= d | s |. $$ Поскольку $ S $ имеет по крайней мере $ (1- \ EPSILON) D | S | $ Соседи, $$ \ sum_ {d \ geq 1} a_d \ geq (1- \ epsilon) d | s |. $$ Следовательно $$ \ sum_ {d \ geq 2} a_d \ leq \ sum_ {d \ geq 1} (d-1) a_d=sum_ {d \ geq 1} da_d - \ sum_ {d \ geq 1} a_d \ leq d | s |. - (1- \ Epsilon) D | S |=Epsilon d | s |. $$ Следует, что $$ a_1=sum_ {d \ geq 1} a_d - \ sum_ {d \ geq 2} a_d \ geq (1- \ epsilon) d | s | - \ Epsilon d | s |= (1-2 \ epsilon) d | s |. $$