Dispersor - Disperser

Um dispersor é um extrator unilateral . Quando um extrator exige que cada evento tenha a mesma probabilidade sob a distribuição uniforme e a distribuição extraída, apenas a última é necessária para um dispersor. Portanto, para um dispersor, um evento que temos: ${\ displaystyle A \ subseteq \ {0,1 \} ^ {m}}$${\ displaystyle Pr_ {U_ {m}} [A]> 1- \ epsilon}$

Definição (dispersor): um dispersor é uma função${\ displaystyle (k, \ epsilon)}$

${\ displaystyle Dis: \ {0,1 \} ^ {n} \ times \ {0,1 \} ^ {d} \ rightarrow \ {0,1 \} ^ {m}}$

de modo que para cada distribuição ativada com o suporte da distribuição seja de tamanho pelo menos . ${\ displaystyle X}$ ${\ displaystyle \ {0,1 \} ^ {n}}$ ${\ displaystyle H _ {\ infty} (X) \ geq k}$ ${\ displaystyle Dis (X, U_ {d})}$ ${\ displaystyle (1- \ epsilon) 2 ^ {m}}$

Teoria dos grafos

Um ( N , M , D , K , e ) -dispersor é um gráfico bipartido com N vértices no lado esquerdo, cada um com grau D e M vértices no lado direito, de modo que cada subconjunto de K vértices no lado esquerdo está conectado a mais de (1 -  e ) M vértices à direita.

Um extrator é um tipo relacionado de gráfico que garante uma propriedade ainda mais forte; cada ( N , M , D , K , e ) -extrator também é um ( N , M , D , K , e ) -disperser .

Outros significados

Um dispersor é um dispositivo de mistura de alta velocidade usado para dispersar ou dissolver pigmentos e outros sólidos em um líquido.

Veja também

• Gráfico expansor

Referências

Este artigo sobre combinatória é um esboço . Você pode ajudar a Wikipedia expandindo-a . v t e