Tagged Questions

2
votes
1answer
38 views

The Ramsey number $r(t,t,q)$ with $q\geq t$

Let q and t be positive integers with $q\geq t$. Determine the Ramsey number $r_t(t,t,q)$. This is from the book Introductory Combinatorics by Brualdi, and in the back it says the answer is q without ...
2
votes
2answers
73 views

What is a Ramsey Graph?

What is a ramsey graph and What is its relation to RamseyTheorem? In Ramsey Theorem: for a pairs of parameters (r,b) there exists an n such that for every (edge-)coloring of the complete graph on n ...
1
vote
1answer
52 views

Ramsey and Random Graph

By considering the random graph G(n,p), show that $$R(4,k)>\left ( \dfrac{k}{3\log k} \right )^{3/2} $$ Improve this bound as much as you can.
1
vote
1answer
66 views

A Problem about friends and strangers using Ramsey's Theory

Question: Consider a group of 8 people, each pair of which are either friends or enemies. Show that if some person in the group has at least 6 friends, then there are 4 people who are mutual friends ...
6
votes
2answers
113 views

How many 2-edge-colourings of $K_n$ are there?

I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially ...
2
votes
1answer
127 views

Ramsey Number Inequality

I want to prove that: $$R(\underbrace{3,3,...,3,3}_{k+1}) \le (k+1)(R(\underbrace{3,3,...3}_k)-1)+2$$ where R is a Ramsey number. In the LHS, there are $k+1$ $3$'s, and in the RHS, there are $k$ ...
2
votes
1answer
93 views

Ramsey Number proof

I am trying to prove: $R(3,3,3,3)\leq 4(R(3,3,3)-1) + 2$ I am confused as to how one can go from a $4$ color problem to a $3$ color problem by multiplying and adding. edit: $R$ is the Ramsey ...
0
votes
1answer
36 views

Edge coloring graph vertices probability

How to show the following: Let $R(k,t)$ denote the Ramsey function, that is the minimal number $n$ so that if the edges of a complete graph $K_n$ on $n$ vertices are each colored red or blue, then ...
4
votes
1answer
111 views

Graph theory dinner party problem

In a party of 6 people is it true that there exists four people either all do or all do not knowing each Other? I know it's false, and have the solution but not quite sure where to begin with the ...
0
votes
1answer
52 views

Graph theory mutual acquaintance and mutual strangers problem

Show that there is a gathering of five people in which there are no three people who all know each other, and no three people none of whom knows either of the other two. There is a solution in the ...
2
votes
0answers
38 views

Van der Waerden number

The Van der Waerden number $w(l,k)$ is the least $n$ such that for every $k$-coloring of $[n]$ has a monochromatic $l$-term arithmetic progression. Prove that $w(l,k)>(lk^{l-1})^{1/2}$ Give some ...
3
votes
2answers
66 views

Counterexample for $R(4,4) \neq 8$

I try to find a counterexample for $R(4,4)\neq 8$. (R is the Ramsey-number). I drew a graph with 8 vedges and I coloured all edges $(v_i,v_j)$ with $i-j =\pm 2,4,6$ in the same colour (for example ...
4
votes
1answer
55 views

Ramsey number for paths

Let $n = R(P_{r+1}, c)$ be the smallest integer such that if $K_n$ is $c$-edge-coloured, then it contains a monochromatic subgraph isomorphic to $P_{r+1}$, the path of length $r$. I need to show that ...
2
votes
3answers
196 views

Good way to learn Ramsey Theory

What are some good books on Ramsey theory? I have Van Lints book on Combinatorics: is this enough preparation to start reading about Ramsey theory? I want a book that includes important results and ...
3
votes
1answer
86 views

Amalgamation of graphs

I am trying to understand the definition of amalgamation of a $n+1$-partite graph as explained here(first few lines of page 4). We have a $n+1$-partite graph $G$ with partite sets $V_0,V_1,\cdots,V_n$ ...
3
votes
1answer
71 views

Any forest on 5 or more vertices contains an independent set of size 3.

I am looking for a short proof of this fact. This is clearly true by drawing these trees, but I am having trouble putting it into writing. Somehow I need to select 3 of the 5 vertices and show that ...
1
vote
1answer
264 views

Monochromatic triangle and edge colouring

$r(k) := R(\underbrace{3,3,...,3}_k)$ (I.e. $r(k)$ is the minimum integer $n > 0$ such that every coloring of edges of $K_n$ in $k$ colors is guaranteed to produce a monochromatic triangle.) Show ...
0
votes
1answer
184 views

Complete graph edge colouring in two colours: lower bound for number of monochromatic triangles

Say $K_n$ is a complete graph. Show that any coloring of edges of $K_n$ with $n \ge 6$ in two colors contains at least $$\frac1{20}\binom{n}3$$ monochromatic triangles. Any ideas on how to use Ramsey ...
2
votes
0answers
56 views

Ramsey (graph) theory question with tree and girth

Sorry for the abundance of questions I'm asking. Test is soon... Prove that for every tree $T$ and every $g \in \mathbb{N}$, exist $G$ with girth $g$, so that in any 2-edge-coloring of $G$ there is a ...
2
votes
1answer
74 views

2012-gon- subsets of vertices.

Can we prove or disprove this? For a sufficiently large $n$, every set of at least $ n$ points in the plane with no three collinear has a subset that form the vertices of a convex $2012$-gon. Gerry ...
0
votes
2answers
64 views

Complete graph-coloring

Can we prove or disprove the following statement? For any graph $H$ and any coloring $c$ of its edges with two colors, there exists $n$ such that every $2$-coloring of the edges of the complete graph ...
1
vote
2answers
336 views

Ramsey Number R(4,4)

In trying to deduce the lower bound of the ramsey number R(4,4) I am following my book's hint and considering the graph with vertex set $\mathbb{Z}_{17}$ in which $\{i,j\}$ is colored red if and only ...
1
vote
1answer
119 views

Ramsey theory - colouring of edges

I'm trying to understand a proof: $R(3,3) = 6$ proof: Take a red/blue colouring of $K_6$. Take a vertex $v$ (is an element of) $V(K_6)$, either $v$ is incident to $\geq 3$ red edges or, $v$ is ...
1
vote
1answer
95 views

Prove the following inequality: $N(P,P,2)\leq 4^{P-1}$

I've made very little headway on this problem, so any help is appreciated. Edit: Sorry, I should have explained that. In general, $N(p,q,2)$ is the smallest value of $n$ such that a red-blue ...
0
votes
3answers
278 views

Party problem / Ramsey's theorem R(3,3)

I'm looking for an algorithm that solve Party problem. The party problem asks to find the minimum number of guests that must be invited so that at least 3 will know each other or at least 3 will not ...
5
votes
1answer
315 views

Understanding various definitions of TREE($n$) in Friedman's finite form of Kruskal's tree theorem.

I was reading the Wikipedia article on Friedman's finite form of Kruskal's tree theorem, and am interested in the large numbers TREE(n). I would like to verify TREE(2)=3 myself, but find conflicting ...
6
votes
1answer
262 views

Showing that $K_7$ contains at least 4 monochromatic triangles

A problem in my book is: Let the edges of $K_7$ be colored with the colors red and blue. Show that there are at least four subgraphs $K_3$ with all three edges the same color (monochromatic ...
2
votes
2answers
195 views

Lower bound for monochromatic triangles in $K_n$

Say $K_n$ is a complete graph of $n$ nodes, and every edge is either blue or red. I'm trying to find $T_n$, which is the lower bound for the number of monochromatic triangles in $K_n$ (monochromatic ...
3
votes
1answer
218 views

How to prove this relation between Ramsey Numbers: $R(s, t) ≤ R(s, t-1) + R(s-1, t)$ for $s,t>2$

I am trying to prove that $$R(s, t) ≤ R(s, t-1) + R(s-1, t) $$ for $s,t>2$, where $R(s,t)$ is the Ramsey number of $(s,t)$, and I'd be really grateful for a hint that gets me started.
4
votes
1answer
326 views

Ramsey number for books

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 ...
5
votes
1answer
190 views

An upper bound for a graph Ramsey number

I am trying to prove the following result, given as an exercise in my book: $r(K_m+\bar{K_n},K_p+\bar{K_q})\le\binom{m+p-1}{m}n+\binom{m+p-1}{p}q$. Here $r(G,H)$ denotes the Ramsey number for the ...
6
votes
2answers
195 views

Prove that $r(k,k) + k \leq r(k + 1, k + 1) $

Prove that $r(k,k) + k \leq r(k + 1, k + 1)$, where $r(k,l)$ is the minimum number of vertexes in a Graph, where we have a clique with $k$ vertexes or a stable set with $l$ vertexes. There are ...
4
votes
1answer
108 views

Edge coloring a graph to find a monochromatic $K_{2,n}$

I am trying to prove or disprove the following statement: Let $n>1$ be a positive integer. Then there exists a graph $G$ of size 4n-1 such that if the edges of $G$ are colored red or blue, no ...
5
votes
1answer
191 views

Known bounds and values for Ramsey Numbers

Is there a good online reference that lists known bounds on Ramsey numbers (and is relatively up to date)? The wikipedia page only has numbers for $R_2(n,m)$. I am specifically interested in known ...
4
votes
2answers
257 views

how to construct 17-vertexed graph for Ramsey number R(3,6)=18

Ramsey number R(3,6)=18. How to construct a graph of 17 nodes which does not contain neither a clique of order 3 or an independent set of order 6. could you show me the tactics or the adjacency ...