Expander unica-vicino

Question

Voglio risolvere il problema 4.10 dalla casualità di Salil Vadhan. https://people.seas.harvard.edu/~salil/CS225 / Spring15 / PS3.pdf

Considera un expander bipartite $ G $ con laurea a sinistra $ d $ in modo da ogni sottoinsieme $ s $ dei vertici sinistro con la maggior parte dei $ k $ i vertici hanno almeno $ (1- \ Epsilon) D | S | $ vicini.Quindi $ G $ ha anche la proprietà che ha $ (1-2 \ epsilon) d | s | $ vicini unici.Significato unico che ha esattamente un vertice corrispondente da $ s $ .

Io riconosco che il nuovo fattore di espansione è $ (1-2 \ epsilon) d= 2 \ cdot (1- \ epsilon) D $

.

Answer 1

Let $ s $ essere un sottoinsieme del massimo $ k $ vertici. Let $ a_d $ Sii il numero di vertici sul lato destro che sono collegati a esattamente $ d $ vertici In $ s $ . Dal momento che il grado sinistro è $ d $ , $$ \ sum_ {d \ geq 1} da_d= d | s |. $$ Dal momento che $ s $ ha almeno $ (1- \ epsilon) d | s | $ vicini $$ \ sum_ {d \ geq 1} a_d \ geq (1- \ epsilon) d | s |. $$ Perciò $$ \ 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 |. $$ Ne consegue che $$ 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 |. $$