Sobre a conjectura de expansão de conjunto pequeno

Dado um gráfico e a alguém deseja calcular . ( ) A `` expansão em pequenos conjuntos conjectura "afirma que é NP-Difícil determinar se isso está abaixo de ou acima de paraδ > 0 h ( G , δ ) = m i n | S | ≤ δ | V | ϕ ( S ) ϕ ( S ) = E ( S , ˉ S$G=(V,E)$$\delta > 0$$h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$ Ε1-εε=1/O(log($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - \vert S\vert \} }$$\epsilon$$1-\epsilon$$\epsilon = 1/O(log(\frac{1}{\delta} ) )$

No contexto, observa-se que é a constante Cheeger que é conhecida por ser NP-difícil de ligar. Mas parece haver valores de (quais?) Para os quais podem ser computados em tempo polinomial?δϕ(G,δ$h(G,\delta = \frac{1}{2})$$\delta$$\phi(G,\delta)$

Para entender a conjectura de expansão de pequeno conjunto, parece que se prova essa afirmação,

• Se é a extensão dos autovetores laplacianos de modo que seus valores próprios sejam menores que alguns e se cada satisfizer então, para todo conjunto tal que , temosG λ ∈ [ 0 , 1 $W$$G$$\lambda \in [0,1]$E i [ w 4 i ] ≤ C ( E i [ w 2 i ] ) 2 S | S | ≤ δ | V | ϕ ( S ) ≥ λ ( 1 - $w \in W$$\mathbb{E}_i[w_i^4 ] \leq C ( E_i [w_i ^2 ] )^2$$S$$\vert S \vert \leq \delta \vert V \vert$$\phi(S) \geq \lambda(1 - \sqrt{C \delta} )$

[Referência, Lema 8 aqui, http://www.boazbarak.org/sos/files/lec2d.pdf ]

Minhas perguntas são,

• Como o teorema acima ajuda a entender a conjectura declarada no início? Qual é a relação entre os dois?

• Por que tais vetores existem conforme exigido no teorema? Qual é a intuição por trás de olhar para tal ?$w$$w$

• Qual é a intuição por trás da escolha desse valor específico de como na declaração da conjectura?$\epsilon$

Acho que o seguinte deve responder às suas perguntas, mesmo que não esteja exatamente na mesma ordem.

A formulação original da conjectura de expansão de conjunto pequeno afirma que, analogamente à conjectura de jogos exclusivos, para cada existe modo que é NP difícil determinar se em um gráfico é o "SIM" caso em que exista um conjunto de tamanho com expansão menor que ou seja o caso "NÃO" em que todo conjunto de tamanho tenha expansão de pelo menos . O artigo de Raghavendra, Steuerer e Tulsiani https://www.cs.cornell.edu/~dsteurer/papers/ssereductions.pdf mostrou que isso é equivalente ao caso em que$\epsilon >0$$\delta>0$$G$$\delta$$\epsilon$$\delta$$1-\epsilon$$\epsilon = O(\log (1/\delta))$e de fato o caso em que no caso NO, para cada , conjuntos de tamanho têm pelo menos a mesma expansão que teriam no " gráfico gaussiano noisy" (veja o artigo para a declaração precisa). A razão para a relação é porque esta é a relação entre esses parâmetros no gráfico de ruído gaussiano. Esse resultado de Raghavendra et al. Pode ser pensado como o analógico de expansão de pequeno conjunto do artigo de Khot, Kindler, Mossell e O'Donnell, que mostrou um resultado semelhante para jogos únicos, fornecendo uma relação muito precisa entre os parâmetros (que na configuração de jogos exclusivos é conhecido como tamanho do alfabeto) e$\delta' \geq \delta$$\delta'$$\epsilon$$\epsilon = O(\log (1/\delta))$$1/\delta$$\epsilon$.

O resultado que você mencionou discutido em minhas notas de aula é da Seção 8 em meu artigo com Brandao, Harrow, Kelner, Steurer e Zhou ( https://www.cs.cornell.edu/~dsteurer/papers/hypercontract.pdf ). O que mostramos lá, grosso modo, é que um gráfico é um pequeno expansor de conjunto, se e somente se o intervalo de vetores próprios correspondendo a valores próprios baixos do seu Laplaciano não contiver um vetor "analiticamente esparso".

A intuição é a seguinte: considere os dois extremos a seguir:

1) Um vetor aleatório . Nesse caso, a distribuição das entradas de é aproximadamente a distribuição gaussiana e, portanto, isso satisfaz que .$w$$w$$\mathbb{E}_i w_i^4 = O(\mathbb{E}_i w_i^2)^2$

2) Um vetor que é o vetor característico de um conjunto de medidas (ou seja, possui nas coordenadas pertencentes ao conjunto e nas outras). Nesse caso, .$w$$\delta$$1$$0$$\mathbb{E}_i w_i^4 = \delta \gg \delta^2 = (\mathbb{E}_i w_i^2)^2$

Agora, grosso modo, o subespaço correspondente a valores próprios menores que do Laplaciano corresponde a um conjunto que possui expansão no máximo no gráfico. Portanto, se existe um conjunto de tamanho com essa expansão, haveria um vetor (ou seja, a projeção do vetor característico deste conjunto para ) com . A outra direção (que é mais difícil de provar, mas acaba sendo verdadeira) é que, se houver um vetor com essa propriedade, também podemos encontrar um conjunto com medida com expansão não muito boa.£ £ ô W W E i w 4 i » ( E i w 2 i ) 2 w O ( 1 $W$$\epsilon$$\epsilon$$\delta$$w$$W$$\mathbb{E}_i w_i^4 \gg (\mathbb{E}_i w_i^2)^2$$w$$o(1)$