Expander unique-voisin

Question

Je veux résoudre le problème 4.10 du hasard par Salil Vadhan. https://people.seas.harvard.edu/~salil/CS225 / Spring15 / PS3.PDF

considérer un extenseur bipartite $ g $ avec degré gauche $ d $ de sorte que chaque sous-ensemble $ s $ des sommets de gauche avec au plus $ k $ sommets a au moins $ (1- \ epsilon) d | s | $ voisins.Puis $ g $ a également la propriété qu'il a $ (1-2 \ epsilon) d | s | $ voisins uniques.Signification unique qu'il a exactement un sommet correspondant de $ s $ .

Je reconnais que le nouveau facteur d'expansion est $ (1-2 \ epsilon) d= 2 \ cdot (1- \ epsilon) d -d $

Answer 1

let $ s $ soit un sous-ensemble d'au plus $ K $ sommets. Laissez $ a_d $ Soyez le nombre de sommets sur le côté droit qui sont connectés à exactement $ d $ sommets dans $ s $ . Puisque le degré de gauche est $ d $ , $$ \ sum_ {d \ geq 1} da_d= d | s |. $$ Depuis $ s $ a au moins $ (1- \ epsilon) d | s | $ voisins, $$ \ sum_ {d \ geq 1} a_d \ geq (1- \ epsilon) d | s |. $$ Par conséquent $$ \ sum_ {d \ geq 2} a_d \ leq \ somm_ {d \ geq 1} (D-1) a_d=sum_ {d \ geq 1} da_d - \ somm_ {d \ geq 1} a_d \ leq d | s | - (1- \ epsilon) D | S |=epsilon d | s |. $$ Il s'ensuit 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 |. $$