Una variación en la discrepancia que involucra gráficos aleatorios

Supongamos que tenemos un gráfico en nodos. Nos gustaría asignar a cada nodo un o un . Llame a esto una configuración . El número de s que tenemos que asignar es exactamente (por lo tanto, el número de s es ). Dada una configuración , observamos cada nodo y sumamos los valores asignados a sus vecinos, llame esto . Luego contamos el número de nodos para los cuales no es negativo: $n$ $+1$ $−1$ $\sigma \in \{+1,−1\}^n$ $+1$ $s$ $−1$ $n−s$ $\sigma$ $i$ $\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\}.$ La pregunta es: ¿cuál es la configuración que maximiza ? Más importante aún, ¿podemos dar un límite en en términos de

. Me pregunto si este problema le resulta familiar a alguien, o si se puede reducir a algún problema conocido en la teoría de grafos. Si ayuda, se puede suponer que el gráfico es aleatorio del tipo Erdős-Renyi (digamos, G (n, p) con probabilidad de borde

, es decir, un grado promedio de crecimiento como

). El interés principal es en el caso donde

σ

$\sigma$

N (σ)

$N(\sigma)$

(max N) / n

$(\max N)/n$

s / n

$s/n$

p (\log n) / n

$p ~ (\log n)/n$

\log n

$\log n$

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

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

graph-theory co.combinatorics optimization transeúnte51
fuente

Cambié el título, porque lo que estás preguntando está relacionado con problemas de discrepancia en espacios de rango. Sin embargo, NO está relacionado con la discrepancia en los gráficos (que trata más sobre las desviaciones de la densidad del borde)

Suresh Venkat

enlace simple: tomar al azar; , donde es el grado de vértice y es algo constante. Entonces, . Si dice y el gráfico es -regular, entonces 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: Gracias. Eso es lo que me gusta de preguntarle a los informáticos, ¡aprendes algo nuevo! Entonces, ¿dónde es un buen lugar para aprender sobre problemas de discrepancia en el espacio de rango? (¿Quizás un documento breve y conciso?)

transeúnte51

@ Sasho: Gracias. Por alguna razón, no puedo ver las ecuaciones correctamente (han chocado con el texto circundante). Intentaré leerlo y responderle. Pero debo mencionar que el régimen interesante para mí es y el problema parece ser más difícil a medida que acerca a . (Esto se debe a la consideración de la simetría en el problema original de donde vino esto). No creo que mirar un aleatorio lo haga para .

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

La conjetura / esperanza es que para decir G (n, p) con o . Acabo de darme cuenta del error tipográfico en mi publicación original con respecto a la . Lo siento por eso. El grado de avarage está creciendo a medida que no .

(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

Respuestas:

Podría abordar esto con un cálculo del "método del segundo momento", similar al que usé en Un umbral agudo para un problema de satisfacción de restricción aleatoria , Discrete Mathematics 285 / 1-3 (2004), 301-305.

Cuando el grado promedio crece como tiempos constantes suficientemente grandes , este enfoque a menudo ha sido suficiente para encontrar con precisión el umbral de satisfacción. Posiblemente también podría mostrar la fracción de cláusulas que pueden cumplirse en una instancia insatisfactoria, aunque no he investigado eso. $\log n$

Para que su problema se parezca más al mío general, puede verlo como un "MAX-AT-LEAST-HALF-SAT" con una estructura gráfica especial subyacente a las cláusulas de la fórmula CNF. Sin embargo, no creo que esta estructura especial ayude en el análisis del peor de los casos, y dado que el tamaño de su cláusula no es uniforme y su conjunto de asignaciones "malas" está creciendo, tendrá que pasar por el cálculo y ver si todavía funciona.

Abraham D Flaxman
fuente

mirar esto como un CSP parece realmente mejor que mirarlo como un problema de discrepancia

Sasho Nikolov

Gracias. Esto se ve muy interesante. Lo investigaré.

passerby51

Permítanme detallar mi comentario. Primero, esto es similar a la discrepancia, pero por supuesto diferente en varias formas. Dado un sistema de conjuntos , la discrepancia del sistema es . Denotemos. Su definición difiere en que desea saber cuántos conjuntos son positivos y la discrepancia le pregunta qué tan grande es en magnitud en el peor de los casos. Para una introducción rápida, tal vez mis notas de escriba puedan ayudar. Chazelle tiene un buen libro que entra en muchos detalles. $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 un límite inferior probabilístico fácil cuando , como en mi comentario, dado un gráfico con secuencia de grados , puede elegir uniforme al azar de todas las secuencias con 's ( no son independientes, pero también debería ser posible probar un límite de Chernoff en este caso). Tenemos , por un límite de Chernoff, para alguna constante . Entonces . Entonces existe alguna $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 logra este límite.

EDITAR: Parece que está interesado en el caso . Seleccionemos al azar de la misma manera que en el párrafo anterior. Usando una versión del teorema del límite central para el muestreo sin reemplazo ( es una muestra de tamaño sin reemplazo de los vértices del gráfico), debería poder mostrar que comporta como un gaussiano con media y varianza sobre , entonces para algunos C y un parámetro de error del teorema del límite central. Deberíamos tener $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)$ , para que pueda tomar . $N(\sigma) \geq \sum_{i}{\exp(-C\delta_i(2s/n - 1)^2)} - o(n)$

Descargos de responsabilidad: esto solo tiene sentido si son constantes / pequeños o si está muy cerca de . Además, los cálculos son algo heurísticos y no se realizan con mucho cuidado. $\delta_i$ $s/n$ $n/2$

Sasho Nikolov
fuente

Gracias por los lindos enlaces y el argumento. Me gusta el argumento probabilístico, pero creo que hay algo mal con tu límite. Puede ver esto, estableciendo , para lo cual deberíamos tener . Parece que esto fue lo que salió mal: si elige uniforme al azar del conjunto especificado en el problema, cada tiene un problema. de ser y prob. de de ser . Por lo tanto, que es 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

El no será independiente y, estrictamente hablando, no podemos usar la desigualdad de Hoeffding. Pero ignoremos este pequeño detalle y asumámoslo iid. Entonces, el límite sería que se cumple para . No podemos establecer para obtener .

{σ_{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

lo siento, debería haber especificado eso: la suposición aquí era que . de lo contrario, esto no tiene sentido y necesitas algo más fuerte como Berry-Esseen. Creo que se puede suponer que es esencialmente independiente

s > n / 2

$s > n/2$

σ_{j}

$\sigma_j$

Sasho Nikolov

@ passerby51 agregó un bosquejo de cómo podría intentar usar una versión cuantitativa del teorema del límite central para extender el límite probabilístico a .

s / n < 1 / 2

$s/n < 1/2$

Sasho Nikolov