Colección de Gráficos

Question

Deje $n \in \mathbb{N}$$r \in \mathbb{R}$. Decimos que $(V, G_{1}, G_{2}, ..., G_{t})$ $(r,n)$- colección si $V$ es un conjunto de $n$ vértices, y $G_{1}, G_{2}, ..., G_{t}$ $t = n^{20}$ gráficos en $V$ tal que $\chi(G_{i}) \ge r$ por cada $i$.

Decimos que un $(r,n)$-colección de $(V, G_{1}, G_{2}, ..., G_{t})$ es especial si no existe $U \subseteq V$ tal que $|U| \le 2n/3$ $\chi(G_{i}[U]) \ge r/3$ por cada $i$.

Es cierto que para suficientemente grande $n$ cada $(r,n)$-de la colección es especial: (i) cuando $r = 3n^{0.1}$? (ii) cuando $r = 3\log_{2}(n)$?

Ahora, yo realmente no sé cómo abordar esta pregunta. Traté de usar martingales pero no entiendo cómo usarlo aquí. También no sé cómo hacer gráficos con cromática de los números.

Answer 1

Para la parte (i) de la cuestión, la declaración es verdadera, y, de hecho, un (uniformemente) elegido al azar de $U \subseteq V$ va a satisfacer todos los requisitos, con alta probabilidad. Para ello, necesitamos saber que el si $G$ es un gráfico con $\chi(G) \ge r$, entonces hay una alta probabilidad de que $\chi(G[U]) \ge \frac r3$.

Primero de todo, la expectativa $\mathbb E[\chi(G[U])]$ no se puede ser demasiado baja. Deje $\chi(G) = s$, para algunas de las $s \ge r$. A continuación, $\mathbb E[\chi(G[U])] \ge \frac s2$ por una simetría de mis argumentos elaborados en respuesta a esta pregunta.

Esto nos ayuda a comenzar una martingala argumento: vamos a $V_1, V_2, \dots, V_s$ $s$ clases de color de un colorante de $G$, y considerar la Doob martingala donde nos revelan $U \cap V_i$ a $i^{\text{th}}$ paso. (Esto es de Lipschitz, ya que el cambio de $U \cap V_i$ cambio $\chi(G[U])$ a la mayoría de los $1$.) Después de $s$ pasos, hemos revelado todos los de $U$, y por Azuma la desigualdad, $$\Pr[\chi(G[U)] \le \mathbb E[\chi(G[U])] - T] \le \exp\left(-\frac{T^2}{2s}\right).$$ Take $T = \frac s6$, and we conclude that $\Pr[\chi(G[U)] \le de s/3] \le \exp(-s/72)$, which implies also the weaker claim that $\Pr[\chi(G[U)] \le r/3] \le \exp(-r/72)$.

Al $r = 3n^{0.1}$, o en general cuando se $r \gg \log n$, esta probabilidad es menor que $n^{-20}$ o cualquier otro polinomio de probabilidad, siempre $n$ es lo suficientemente grande. También, $|U| \le \frac23n$, con una probabilidad muy alta, por lo que la unión obligado en todas nuestras limitaciones termina el argumento.

---

Para la parte (ii) de la pregunta, esta no va a volar, porque $r$ es demasiado pequeño. De hecho, es mucho más cierto en este caso: se puede recoger $G_1, \dots, G_t$, de modo que para cada $U$, algunos $G_i[U]$ no tienen bordes.

Deje que cada una de las $G_i$ consta de una sola copia de $K_r$ en un uniforme random $r$-subconjunto de $V$; elija $n^{20}$ de estos de forma totalmente independiente. Para una fija $U$ del tamaño en la mayoría de los $\frac23 n$, hay una probabilidad de $(\frac13)^r$ que $G_i$ misses $U$ completamente, y $(\frac13)^r = 3^{-3\log_2 n} \approx n^{-4.75}$. Este es pequeño, pero no demasiado pequeño: con $n^{20}$ diferentes $G_i$, el promedio de número de $G_i$ que no tienen bordes en $U$ es mayor que $n^{15}$.

Por otra parte, debido a que estos son independientes, la distribución del número de $G_i$ enfoques de la distribución de Poisson muy rápidamente, de modo que la probabilidad de que no $G_i$ miss $U$ enfoques $e^{-n^{15}}$. Esto es fácilmente lo suficientemente pequeño como para que nos tomemos un sindicato vinculado sobre todo a $< 2^n$ opciones de $U$.