Expansor do vizinho único

Question

Eu quero resolver o problema 4.10 da aleatoriedade por Salil Vadhan. https://people.seas.harvard.edu/~salil/cs225 / spring15 / ps3.pdf

Considere um expansor bipartita $ g $ com grau esquerdo $ D $ para que cada subconjunto $ S $ dos vértices esquerdos com no máximo $ k $ vértices tem pelo menos $ (1- \ epsilon) D | S | $ vizinhos.Então $ g $ também tem a propriedade que tem $ (1-2 \ epsilon) D | S | $ vizinhos únicos.Significado único que tem exatamente um vértice correspondente da $ S $ .

Eu reconheço que o novo fator de expansão é $ (1-2 \ epsilon) d= 2 \ Cdot (1- \ epsilon) d -d $

.

Answer 1

Deixe $ s $ ser um subconjunto do mais $ k $ vértices. Deixe $ a_d $ Seja o número de vértices no lado direito que estão conectados a exatamente $ D $ vértices Na $ S $ . Como o diploma esquerdo é $ D $ , $$ \ sum_ {d \ geq 1} da_d= d | s |. $$ Como $ s $ tem pelo menos $ (1- \ epsilon) d | s | $ vizinhos, $$ \ sum_ {d \ geq 1} a_d \ geq (1- \ epsilon) d | s | s | $$ Portanto $$ \ 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 |. $$ Segue que $$ A_1=sum_ {d \ geq 1} a_d - \ sum_ {d \ geq 2} a_d \ geq (1- \ epsilon) d | s | s | - \ epsilon d | s |= (1-2 \ epsilon) D | S | $$