Expansor vecino único

Question

Quiero resolver el problema 4.10 de la aleatoriedad por Salil Vadhan. https://people.seas.harvard.edu/~salil/CS225 / Spring15 / PS3.PDF

Considerar un expansor bipartito $ g $ con grado izquierdo $ d $ para que cada subconjunto $ s $ de los vértices izquierdos con la mayoría de $ k $ vértices tiene al menos $ (1- \ Epsilon) D | S | $ vecinos.Luego, $ g $ también tiene la propiedad que tiene $ (1-2 \ epsilon) d | s | $ Vecinos únicos.Significado único que tiene exactamente un vértice correspondiente de $ s $ .

Reconozco que el nuevo factor de expansión es $ (1-2 \ epsilon) D= 2 \ CDOT (1- \ EPSILON) D -D $

Answer 1

Permitir $ s $ Sé un subconjunto de más $ k $ vértices. Deje que $ A_D $ sea el número de vértices en el lado derecho que están conectados a exactamente $ d $ vértices en $ s $ . Dado que el grado izquierdo es $ d $ , $$ \ sum_ {d \ geq 1} da_d= d | s |. $$ Desde $ s $ tiene al menos $ (1- \ epsilon) d | s | $ vecinos, $$ \ sum_ {d \ geq 1} A_D \ GEQ (1- \ Epsilon) D | S |. $$ Por lo tanto $$ \ 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 |. $$ Resulta que $$ 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 |. $$