92
правки
Изменения
м
→Однородный (комбинаторный) экспандер
<tex>\sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}} \leq \sum\limits_{s = 1}^{\tfrac{n}{2}} \dbinom{s}{n} \cdot \dbinom{(1 + \epsilon)s}{n} \cdot \bigg(\cfrac{(1 + \epsilon)s}{n}\bigg)^{\tfrac{sd}{2}}</tex>. <tex>(1)</tex>
Каждый биномиальный коэффициент <tex>\dbinom{k}{n}</tex> можно оценить сверху величиной <tex>\bigg(\cfrac{ne}{k}\bigg)^{k}</tex>. Тогда
<tex>
\bigg(\cfrac{(1 + \epsilon)s}{n}\bigg)^{\tfrac{sd}{2}} =</tex>
<tex>\sum\limits_{s = 1}^{\tfrac{n}{2}} \bigg[\bigg(\tfraccfrac{s}{n}\bigg)^{\tfrac{d}{2} - 2 - \epsilon} \cdot (1 + \epsilon)^{\tfrac{d}{2}} \cdot \cfrac{e^{1 + \epsilon} }{(1 + \epsilon)^{1 + \epsilon} }\bigg]^s</tex>. <tex>(2)</tex>
Заметим, что <tex>s \leq \tfrac{n}{2}</tex>, а <tex>1 + \epsilon < 2</tex>. Таким образом, можно подобрать такое
