4
$\begingroup$

Given a triangular book $B_n$ I am trying to prove that $r(B_n,B_n)\le 4n+2$ where $r(B_n,B_n)$ is defined as the least positive number such that any graph $G$ on $r(B_n,B_n)$ vertices either has a subgraph (not necessarily induced) isomorphic to $B_n$ or its complement does.

Can someone here please give me any ideas or tell me of some techniques which ought to be pursued to solve problems of this kind. Any kind of opinion is welcome.

  • 0
    @Martin Sleziak: Thanks. I will email you. But I am still interested in an elementary argument for the special case. So I won't delete the question.2011-12-18

1 Answers 1

4

Let $k=r(B_n,B_n)-1$. Then we can color the edges of $K_k$ red and blue in such a way that there is no monochromatic $B_n$. Let $E_r$ and $E_b$ be the sets of red and blue edges, respectively, let $V\,$ be the vertex set of $K_k$, and for $v\in V\,$ let $\deg_r(v)$ and $\deg_b(v)$ be the number of red and blue edges, respectively, incident at $v$.

For each edge $e=\{u,v\}$ let $M(e)$ be the set of vertices that are connected to both $u$ and $v$ by edges of the same color as $e$, and let $\mu(e)=|M(e)|$. Then the number of monochromatic triangles in $K_k$ is $m=\frac13\sum_{e\in E_r\cup E_n}\mu(e)\;,$ since each triangle gets counted three times.

Suppose that $e=\{u,v\}\in E_r$. The edge $e$ together with the edges $\{u,w\}$ and $\{v,w\}$ for $w\in M(e)$ yield a red $B_{\mu(e)}$, so we must have $\mu(e). Similarly, $\mu(e) for each $e\in E_b$. Thus, $m\le\frac13(n-1)|E_r\cup E_b|=\frac13(n-1)\binom{k}2\;.\tag{1}$

Let $v\in V$. Each pair $\langle e_r,e_b\rangle\in E_r\times E_b$ such that $e_r$ and $e_b$ are both incident at $v$ determines a non-monochromatic triangle in $K_k$, so $v$ is a vertex of $\deg_r(v)\deg_b(v)$ non-monochromatic triangles. Each non-monochromatic triangle has two such vertices, so the number of non-monochromatic triangles is $K_k$ is $\frac12\sum_{v\in V}\deg_r(v)\deg_b(v)\;,$ and

$\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*}$

By Cauchy’s inequality we have $\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\;,$ and

$\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*}$

Letting $d=\frac12\big||E_r|-|E_b|\big|$, we then have

$\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*}$

and combining this with $(1)$ yields

$\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*}$

or

$\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*}$

Then $4n+1-k\ge 0$, so $r(B_n,B_n)=k+1\le 4n+2$.

This is actually a special case of Theorem 1.5 of Li & Zang, Introduction to Graph Ramsey Theory.

  • 0
    @Shahab: I’ve not seen the original Rousseau & Sheehan paper, but I shouldn’t be surprised. I did try to simplify the argument as much as was easily possible. I’d love to see a simpler argument, but I’m not going to hold my breath: what little I know of graph Ramsey theory suggests that the arguments are rarely very simple. And in this case there’s no real leeway, since (if I’m not mistaken) $4n+2$ is a sharp bound when $4n+1$ is prime.2011-12-20