Un grafo con pocas aristas en todas partes

Question

Dado un gráfico $G(V,E)$ cuyos bordes están coloreados en dos colores: rojo y azul. Supongamos que se cumplen las dos condiciones siguientes:

• para cualquier $S\subseteq V$ hay como máximo $O(|S|)$ bordes rojos en $G[S]$
• para cualquier $S\subseteq V$ si $G[S]$ no contiene aristas rojas, entonces contiene $O(|S|)$ bordes azules

Mi pregunta es: ¿podemos concluir de esto que el número total de aristas azules es lineal? No tengo ninguna intuición fuerte para esto, pero parece que podría ser posible (¿algún argumento promediador/probabilístico?). Para intentar dar una intuición, podemos reformularlo de la siguiente manera. El gráfico rojo es muy disperso, incluso localmente. El grafo azul también es disperso en todas las regiones libres de aristas rojas. Debido a la escasez del grafo rojo, esas "regiones" son numerosas, por lo que esperamos que esto implique que el grafo azul también es escaso.

Tal vez se pueda considerar primero una versión más sencilla, si suponemos que el grado rojo de cada vértice es $O(1)$ . En este caso tampoco sé la respuesta.

Observe que ya es demasiado débil si sustituimos la primera condición por sólo: el número total de aristas rojas es lineal. Mira el ejemplo: un azul $K_{\sqrt n,n-\sqrt n}$ con un rojo $\sqrt n$ -clique añadida en la parte correspondiente. Este gráfico tiene $\Omega(n^{3/2})$ bordes azules (ejemplo de D. Palvolgyi). Todavía podemos preguntarnos en esta versión si se puede hacer mejor que $n^{3/2}$ .

Answer 1

Creo que se pueden superar los argumentos probabilísticos de Tim Gowers y Fedor Petrov en el caso general, como sigue.

Sea $c$ sea una constante tal que el número de aristas rojas en $G[S]$ es como máximo $c|S|$ para cada $S \subseteq V(G)$ . Se pueden ordenar los vértices de $G$ : $v_1, v_2, \ldots, v_n$ de modo que cada vértice tenga como máximo $2c$ vecinos con índices más bajos. (Defina el orden empezando por el índice más alto. Si $v_n, \ldots,v_{i+1}$ se definen, se establece $v_i$ el vértice de menor grado en el subgrafo inducido por los vértices aún no indexados. Se trata de un truco estándar).

Ahora definimos un subconjunto aleatorio $S$ de $V(G)$ de forma recursiva: si $S \cap$ { $v_1, \ldots, v_i$ } se elige poner $v_{i+1}$ en $S$ con probabilidad $1/2$ si no está unido por una arista roja a ninguno de los vértices que ya están en $S$ si no, no lo pongas $S$ . Entonces $S$ no tiene rojo y, al igual que en la respuesta de Fedor, podemos ver que la probabilidad de que un par de vértices $u$ y $v$ unidas por un borde azul ambas se encuentran en $S$ es como mínimo $2^{-4c-2}$ . Por lo tanto, el número de aristas azules es como máximo

$2^{4c+2}c' \mathbf{E}[|S|] \leq 2^{4c+1}c'|V(G)|,$

donde $c'$ es la constante implícita en la condición sobre la densidad de los bordes azules.

Answer 2

Supongamos que las aristas rojas pueden escribirse como una unión de k emparejamientos, $M_1,\dots,M_k$ . Ahora elige un conjunto aleatorio de vértices de la siguiente manera. Para cada arista en $M_1$ elige uno de sus puntos finales al azar. Pon todos los demás vértices con probabilidad 1/2. A continuación, haga lo mismo para $M_2,\dots,M_k$ . Esto nos da conjuntos $A_1,\dots,A_k$ . Sea $A$ sea la intersección de estos conjuntos. Entonces cada vértice tiene una probabilidad $2^{-k}$ de pertenecer a $A$ . También, $A$ no contiene bordes rojos. Más importante aún, dada una arista no roja, existe una probabilidad $4^{-k}$ que sus dos puntos finales pertenecen a $A$ . Si elegimos un par al azar en $A$ la probabilidad de que sea una arista azul es como máximo $C/n$ para algunos $C$ . Creo (no lo he comprobado lo suficiente para estar seguro) que esto hace el caso de grado limitado, mostrando que tenemos como máximo $4^kCn$ bordes azules. Puede que incluso en el caso general.

Answer 3

No es una respuesta, sino sólo un caso de grado limitado. Si todos los grados rojos no superan $d$ . elija al azar (con distribución uniforme) el conjunto rojo independiente $I$ . Afirmo que para cada arista $uv$ ambos $u$ , $v$ pertenecen a $I$ con probabilidad acotada desde abajo. En efecto, denotemos por $N$ la unión de $u$ , $v$ y sus vecinos rojos. Entonces, si fijamos una intersección de $I$ y $V\setminus N$ entonces la probabilidad condicional de que $u,v$ ambos se encuentran en $I$ es como mínimo $1/2^{n}$ donde $n=|N|\leq 2d+2$ .

Answer 4

He aquí un par de ideas (demasiado largas para caber en una ventana de comentarios). Deje que $R_i$ y $B_i$ son los grados rojo y azul del $i$ -ésimo vértice. Tome su gráfico y elimine todos los vértices con $B_i\le MR_i+M$ . Tome el subgrafo restante y elimine todos los vértices con $B_i\le MR_i+M$ (utilizando los recuentos en el subgrafo restante, por supuesto), y así sucesivamente. No importa cuántas veces vayamos, eliminaremos como máximo $O(Mn)$ bordes azules. Si nos detenemos, tenemos un grafo en el que cada grado azul es al menos $M$ veces el grado rojo correspondiente más $M$ .

Ahora ordena los vértices al azar y selecciona el conjunto independiente del rojo como el conjunto de todos los vértices que preceden a todos sus vecinos en el ordenamiento. Cada vértice $i$ sobrevivirá con probabilidad $(R_i+1)^{-1}$ . Además, si $(i,j)$ no es una arista roja, entonces la probabilidad de que ambas $i,j$ sobrevivir es al menos $\frac12(R_i+1)^{-1}(R_j+1)^{-1}$ . Esto sitúa el número esperado de aristas azules supervivientes en $$\frac 12\sum_{(i,j)\in E_{\text{blue}}}(R_i+1)^{-1}(R_j+1)^{-1}$$ y la expectativa del número de vértices supervivientes en $\sum_{i}(R_i+1)^{-1}$ .

Si todos los grados están limitados por $K$ entonces, claramente, tenemos lo que queremos mucho mejor atado que $4^K$ . Desgraciadamente, si los grados son ilimitados, seguimos teniendo un problema.