Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I edited the question so that it is now clear that you are looking for subgraphs isomorphic to $B_n$, but not necessarily induced subgraphs. It is clear that this is the intended meaning of the question as complete graphs and their complements have no induced subgraphs that are nontrivial books at all. –  Stefan Geschke Dec 18 '11 at 9:38
    
This result is a special case of Theorem 2 from C. C. Rousseau, J. Sheehan: On Ramsey numbers for books; dx.doi.org/10.1002/jgt.3190020110 But perhaps someone will come up with an elementary argument for this particular case. –  Martin Sleziak Dec 18 '11 at 11:07
    
@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. –  Shahab Dec 18 '11 at 11:38

1 Answer 1

up vote 4 down vote accepted

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)<n$. Similarly, $\mu(e)<n$ 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.

share|improve this answer
    
I think this is the same proof mentioned in the paper which Martin Sleziak talked about above. I am really interested in a more elementary argument. Thanks though. –  Shahab Dec 20 '11 at 11:12
    
@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. –  Brian M. Scott Dec 20 '11 at 11:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.