Konstrukcje lepsze niż losowe.

Interesują mnie przykłady konstrukcji teorii złożoności, które są lepsze niż konstrukcje losowe.

Jedyny znany mi przykład takiej konstrukcji dotyczy kodów korygujących błędy. Kody geometrii algebraicznej są lepsze w niektórych zakresach parametrów niż kody losowe.

Można łatwo skonstruować takie sztuczne przykłady. Interesują mnie przykłady takie jak algebraiczne kody geometrii, w których łatwo jest stworzyć losową konstrukcję i nie jest oczywiste, jak zrobić to lepiej.

Wykresy Ramanujana mają drugą wartość własną (zDstopniem wykresu), podczas gdy losowe wykresy osiągają tylkoλ2≤2$\lambda_2\leq \frac{2\sqrt{D-1}}{D}$$D$whp W zasadzie mamyλ2≥2$\lambda_2\leq \frac{2\sqrt{D-1}}{D} + o(1)$, przy czym składniko(1)ma wartość0,aD jestutrzymywane na stałym poziomie (jako liczba wierzchołkówN→∞), więc w pewnym sensie są one optymalne.$\lambda_2\geq \frac{2\sqrt{D-1}}{D} - o(1)$$o(1)$$0$$D$$N\rightarrow \infty$

$\{ 1,\ldots,N \}$$\{ 1,\ldots,N\}$$N^{0.9}$$N^{1-o(1)}$

$n$$n-1$

Ogólnie rzecz biorąc, losowe konstrukcje i chciwe konstrukcje osiągają te same granice (np. Kody korekcji błędów). Kiedyś usłyszałem przemówienie Lovasz'a, w którym powiedział, że chciwe wybory i losowe wybory są zasadniczo takie same. Tak więc każda konstrukcja, która pokonałaby tę chciwą konstrukcję, powinna dać odpowiedź na twoje pytanie. Jako szybki przykład tego rodzaju konstrukcje, które osiągają pojemność Spernera grafów, są tego rodzaju. Jak powiedział Peter Shor, istnieje naprawdę wiele przykładów ekstremalnej kombinatoryki.