Número de ramsey para libros

Question

Dado un triangular libro $B_n$ estoy tratando de demostrar que $r(B_n,B_n)\le 4n+2$ donde $r(B_n,B_n)$ se define como el menor número positivo tal que cualquier gráfico de $G$ $r(B_n,B_n)$ vértices tiene un subgrafo (no necesariamente inducida) isomorfo a $B_n$ o su complemento.

Puede alguien de aquí por favor, dame alguna idea o me dicen de algunas de las técnicas que debe ser aplicada para resolver problemas de este tipo. Cualquier tipo de opinión es bienvenida.

Answer 1

Deje $k=r(B_n,B_n)-1$. Entonces podemos color de los bordes de $K_k$ rojo y azul, de tal manera que no es monocromática $B_n$. Deje $E_r$ $E_b$ ser los conjuntos de rojo y azul, respectivamente, deje $V\,$ ser el vértice conjunto de $K_k$, y para $v\in V\,$ deje $\deg_r(v)$ $\deg_b(v)$ el número de rojo y azul, respectivamente, incidente en $v$.

Para cada arista $e=\{u,v\}$ deje $M(e)$ el conjunto de vértices que están conectados a las $u$ $v$ por los bordes del mismo color como $e$, y deje $\mu(e)=|M(e)|$. A continuación, el número de monocromático triángulos en $K_k$$$m=\frac13\sum_{e\in E_r\cup E_n}\mu(e)\;,$$, ya que cada triángulo son contados tres veces.

Supongamos que $e=\{u,v\}\in E_r$. El borde de la $e$ junto con los bordes $\{u,w\}$ $\{v,w\}$ $w\in M(e)$ el rendimiento de una red $B_{\mu(e)}$, por lo que debemos tener $\mu(e)<n$. Del mismo modo, $\mu(e)<n$ por cada $e\in E_b$. Por lo tanto, $$m\le\frac13(n-1)|E_r\cup E_b|=\frac13(n-1)\binom{k}2\;.\tag{1}$$

Deje $v\in V$. Cada par $\langle e_r,e_b\rangle\in E_r\times E_b$ tal que $e_r$ $e_b$ son ambos incidente en $v$ determina que no monocromática triángulo en $K_k$, lo $v$ es un vértice de $\deg_r(v)\deg_b(v)$ no monocromática de triángulos. Cada uno de los monocromática triángulo tiene dos vértices, por lo que el número de no-monocromática triángulos es $K_k$ $$\frac12\sum_{v\in V}\deg_r(v)\deg_b(v)\;,$ $ y

$$\begin{align*}m&=\binom{k}3-\frac12\sum_{v\in V}\deg_r(v)\deg_b(v)\\ &=\binom{k}3-\frac12\sum_{v\in V}\deg_r(v)(k-1-\deg_r(v))\\ &=\binom{k}3-\frac{k-1}2\sum_{v\in V}\deg_r(v)+\frac12\sum_{v\in V}\deg_r(v)^2\\ &=\binom{k}3-(k-1)|E_r|+\frac12\sum_{v\in V}\deg_r(v)^2\;. \end{align*}$$

Por la desigualdad de Cauchy tenemos $$\left(\sum_{v\in V}\deg_r(v)\right)^2\le\sum_{v\in V}\deg_r(v)^2\; \sum_{v\in V}1^2=k\sum_{v\in V}\deg_r(v)^2\;,$$ so $$4|E_r|^2\ge k\sum_{v\in V}\deg_r(v)^2\;,$$ y

$$\begin{align*}m&\ge\binom{k}3-(k-1)|E_r|+\frac{2|E_r|^2}k\\ &=\binom{k}3-|E_r|\left(k-1-\frac{2|E_r|}k\right)\\ &=\binom{k}3-|E_r|\frac2k\left(\frac{k(k-1)}2-|E_r|\right)\\ &=\binom{k}3-|E_r|\frac2k\left(\binom{k}2-|E_r|\right)\\ &=\binom{k}3-|E_r|\frac2k|E_b|\;. \end{align*}$$

Dejando $d=\frac12\big||E_r|-|E_b|\big|$, luego tenemos

$$\begin{align*} m&\ge\binom{k}3-\frac2k\left(\frac12\binom{k}2-d\right)\left(\frac12\binom{k}2+d\right)\\ &=\frac{k(k-1)(k-2)}6-\frac2k\left(\frac14\binom{k}2^2-d^2\right)\\ &=\frac{k(k-1)(k-2)}6-\frac{k(k-1)^2}8+\frac{2d^2}k\\ &=\frac{k(k-1)(k-5)}{24}+\frac{2d^2}k\;, \end{align*}$$

y la combinación de este con $(1)$ rendimientos

$$\begin{align*} \frac{k(k-1)(k-5)}{24}+\frac{2d^2}k&\le\frac13(n-1)\binom{k}2\\ &=\frac{k(k-1)(n-1)}6\;, \end{align*}$$

o

$$\begin{align*} \frac{2d^2}k&\le\frac{k(k-1)(n-1)}6-\frac{k(k-1)(k-5)}{24}\\ &=\frac{k(k-1)(4n+1-k)}{24}\;. \end{align*}$$

A continuación,$4n+1-k\ge 0$, lo $r(B_n,B_n)=k+1\le 4n+2$.

Esto es en realidad un caso especial del Teorema 1.5 de Li & Zang, Introducción a la Gráfica Teoría de Ramsey.