Variação na discrepância envolvendo gráficos aleatórios

Suponha que tenhamos um gráfico em $n$ nós. Gostaríamos de atribuir a cada nó um $+1$ ou um $−1$ . Chame isso de configuração $\sigma \in \{+1,−1\}^n$ . O número de $+1$ s que devemos atribuir é exatamente $s$ (portanto, o número de $−1$ s é $n−s$ .) Dada uma configuração $\sigma$ , examinamos cada nó $i$ e somamos os valores atribuídos a seus vizinhos, chame isso $\xi_i(\sigma)$ $\xi_i(\sigma)$

N (σ) := \sum_{i = 1}^{n} 1 {ξ_{i} (σ) \geq 0} .

$N(\sigma):=\sum_{i=1}^n 1\{\xi_i(\sigma) \ge 0\}.$

σ

$\sigma$

N (σ)

$N(\sigma)$

(max N) / n

$(\max N)/n$

s / n

$s/n$ . Gostaria de saber se esse problema parece familiar para alguém ou se pode ser reduzido a algum problema conhecido na teoria dos grafos. Se ajudar, pode-se supor que o gráfico seja aleatório do tipo Erdős-Renyi (digamos, G (n, p) com probabilidade de aresta

p (\log n) / n

$p ~ (\log n)/n$ , ou seja, grau médio crescendo como

\log n

$\log n$ ). O instrest principal está no caso em que

s / n \in (0, 1 / 2)

$s/n \in (0,1/2)$ .

graph-theory co.combinatorics optimization passerby51
fonte

Mudei o título, porque o que você está perguntando está relacionado a problemas de discrepância nos espaços de intervalo. Não é no entanto relacionada a discrepância nos gráficos (que é mais sobre desvios densidade borda)

Suresh Venkat

limite simples: pegue aleatoriamente; , onde é o grau de vértice e é uma constante. Então, . Se e o gráfico for regular, então existe tal que .

σ

$\sigma$

Pr [ξ_{i} (σ) < 0] \leq \exp (- C δ_{i} (s / n - 1 / 2)^{2})

$\Pr[\xi_i(\sigma) < 0] \leq \exp(-C\delta_i (s/n - 1/2)^2)$

δ_{i}

$\delta_i$

i

$i$

C

$C$

E [N (σ)] \geq \sum_{i} 1 - \exp (- C δ_{i} (s / n - 1 / 2)^{2})

$E[N(\sigma)] \geq \sum_i{1-\exp(-C\delta_i (s/n - 1/2)^2)}$

s = 3 n / 4

$s = 3n/4$

(16 / C) \log n

$(16/C)\log n$

σ

$\sigma$

N (σ) \geq n - O (1)

$N(\sigma) \geq n - O(1)$

Sasho Nikolov

@ Suresh: Obrigado. É disso que eu gosto em perguntar aos cientistas da computação: você aprende algo novo! Então, onde é um bom lugar para aprender sobre problemas de discrepância no espaço de alcance? (Talvez um papel curto concisa?)

passerby51

@ Sasho: Obrigado. Por alguma razão, não consigo ver as equações corretamente (elas colidiram com o texto ao redor). Tentarei ler e retornar a você. Mas devo mencionar que o regime interessante para mim é e o problema parece ficar mais difícil à medida que aproxima de . (Isso se deve à consideração de simetria no problema original de onde isso veio.) Eu não acho que olhar para um aleatório faria isso por .

s / n \in (0, 1 / 2)

$s/n \in (0,1/2)$

s / n

$s/n$

1 / 2

$1/2$

σ

$\sigma$

s / n \in (0, 1 / 2)

$s/n \in (0,1/2)$

Passerby51

O palpite / esperança é que para dizer G (n, p) com ou . Acabei de perceber o erro de digitação no meu post original sobre a . Me desculpe por isso. O grau médio está crescendo como não .

(max N) / n = o (1)

$(\max N)/n = o(1)$

p (\log n) / n

$p ~ (\log n) / n$

p (\log n)^{1 + ϵ} / n

$p ~ (\log n)^{1+\epsilon} /n$

p

$p$

\log n

$\log n$

p

$p$

Passerby51 14/05

Respostas:

Você pode abordar isso com um cálculo do "método do segundo momento", semelhante ao que eu usei em Um limiar agudo para um problema de satisfação de restrição aleatória , Discrete Mathematics 285 / 1-3 (2004), 301-305.

Quando o grau médio cresce como um número constante suficientemente grande , essa abordagem costuma ser suficiente para encontrar com precisão o limiar de satisfação. Também poderia mostrar a fração de cláusulas que podem ser satisfeitas em um caso insatisfatório, embora eu não tenha investigado isso. $\log n$

Para tornar seu problema mais parecido com o meu geral, você pode visualizá-lo como um "MAX-AT-LEAST-MEIO-SAT" com uma estrutura gráfica especial subjacente às cláusulas da fórmula CNF. Não acho que essa estrutura especial ajude na pior das hipóteses, no entanto, e como o tamanho da sua cláusula não é uniforme e o conjunto de atribuições "ruins" é crescente, você terá que passar pelo cálculo e verificar se ainda funciona.

Abraham D Flaxman
fonte

olhando para isso como um CSP parece de fato um ajuste melhor do que olhar para isso como um problema discrepância

Sasho Nikolov

Obrigado. Isso parece muito interessante. Vou dar uma olhada.

passerby51

Deixe-me elaborar meu comentário. Primeiro, isso é semelhante à discrepância, mas é claro que é diferente de várias maneiras. Dado um sistema de conjuntos , a discrepância do sistema é . Vamos denotar. Sua definição difere na medida em que você deseja saber quantos conjuntos são positivos e a discrepância pergunta quão grande é em magnitude no pior caso. Para uma introdução rápida, talvez minhas anotações de escriba possam ajudar. Chazelle tem um bom livro que entra em muitos detalhes. $m$ $S_1, \ldots, S_m \subseteq \{1, \ldots n\} = [n]$ $\min_{\sigma:[n] \rightarrow \{\pm 1\}}{\max_{j}{|\sum_{i \in S_j}{\sigma(i)}|}}$ $\sigma(S_j) = |\sum_{i \in S_j}{\sigma(i)}|$ $\sigma(S_j)$ $\sigma(S_j)$

Para um limite inferior probabilístico fácil quando , como no meu comentário, dado um gráfico com sequência de graus , você pode escolher uniformemente aleatoriamente de todas as seqüências com (os não são independentes, mas também deve ser possível provar um Chernoff vinculado neste caso). Temos , por um limite de Chernoff, para alguma constante . Então . Então existe algum $s > n/2$ $G = ([n], E)$ $\delta_1, \ldots, \delta_n$ $\sigma$ $s$ $1$ $\sigma_i$ $E[\xi_i(\sigma)] = \delta_i s/n$ $\Pr[\xi_i(\sigma) < 0] \leq \exp(-C\delta_i (s/n - 1/2)^2)$ $C$ $E[N(\sigma)] \geq n - \sum_i{\exp(-C\delta_i (s/n - 1/2)^2)}$ $\sigma$ que alcança esse limite.

EDIT: Parece que você está interessado no caso . Vamos escolher aleatoriamente da mesma maneira que no parágrafo anterior. Usando uma versão do teorema do limite central para amostragem sem substituição ( é uma amostra do tamanho sem substituição dos vértices do gráfico), você deve poder mostrar que se comporta como um gaussiano com média e variação sobre , então para alguns C e um parâmetro de erro do teorema do limite central. Deveríamos ter $s < n/2$ $\sigma$ $\sigma$ $s$ $\xi_i(\sigma)$ $\delta_i (2s/n - 1)$ $\delta_i$ $\Pr[\xi_i(\sigma) \geq 0] =\exp(-C\delta_i(2s/n - 1)^2) \pm \eta(n)$ $\eta(n)$ $n\eta(n) = o(n)$ , então você pode . $N(\sigma) \geq \sum_{i}{\exp(-C\delta_i(2s/n - 1)^2)} - o(n)$

Isenções de responsabilidade: isso só é significativo se for constante / pequeno ou estiver muito próximo de . Além disso, os cálculos são um pouco heurísticos e não são feitos com muito cuidado. $\delta_i$ $s/n$ $n/2$

Sasho Nikolov
fonte

Obrigado pelos bons links e pela discussão. Gosto do argumento probabilístico, mas acho que há algo errado com o seu limite. Você pode ver isso, definindo , para o qual devemos ter . Parece que foi isso que deu errado: se você escolher uniformemente aleatoriamente no conjunto especificado no problema, cada prob. de ser e prob. de de ser . Portanto, que é negativo para ...

s = 0

$s = 0$

P r [ξ_{i} (σ) < 0] = 1

$Pr[\xi_i(\sigma) < 0] = 1$

σ

$\sigma$

σ_{j}

$\sigma_j$

γ := s / n

$\gamma := s/n$

+ 1

$+1$

1 - γ

$1-\gamma$

- 1

$-1$

E [ξ_{i} (σ)] = (2 γ - 1) δ_{i}

$E[ \xi_i(\sigma)] = (2\gamma-1) \delta_i$

γ \in (0, 1 / 2)

$\gamma \in (0,1/2)$

passerby51

O não será independente e, estritamente falando, não podemos usar a desigualdade de Hoeffding. Mas vamos ignorar esses pequenos detalhes e assumi-los iid. Então, o limite seria que vale para . Não podemos definir para obter .

{σ_{j}}

$\{\sigma_j\}$

P r [\frac{1}{δ_{i}} ξ_{i} (σ) < - t + 2 γ - 1) \leq \exp (- δ_{i} t^{2} / 2)

$Pr[ \frac{1}{\delta_i} \xi_i(\sigma) < -t + 2\gamma - 1) \le \exp ( -\delta_i t^2/2)$

t \geq 0

$t \ge 0$

t = 2 γ - 1 < 0

$t = 2\gamma - 1 < 0$

P r [ξ_{i} (σ) < 0]

$Pr[\xi_i(\sigma) <0]$

passerby51

desculpe, eu deveria ter especificado isso: a suposição aqui era que . caso contrário, isso não faz sentido e você precisa de algo mais forte como o Berry-Esseen. eu acho que o pode ser assumido como sendo essencialmente independente

s > n / 2

$s > n/2$

σ_{j}

$\sigma_j$

Sasho Nikolov

@ passerby51 adicionou um esboço de como você pode tentar usar uma versão quantitativa do teorema do limite central para estender o limite probabilístico para .

s / n < 1 / 2

$s/n < 1/2$

Sasho Nikolov 15/05