# Tagged Questions

Ramsey theory refers to questions of the form "how many objects are needed to guarantee that a given property of the collection holds?"

27 views

### what is the relation between diagonal Ramsey numbers $R(r,r)$ and Turán number $t_r(n)$?

Ramsey numbers are mostly unknown,I have seen bounds on Ramsey numbers ( for example via the probabilistic method) but there is more information about TurĂ¡n numbers, , and i can't find in the internet ...
35 views

### Any undirected graph on 9 vertices with minimum degree at least 5 contains a subgraph $K_4$?

Let $G$ be simple undirected graph with degree of every vertices is at least 5. Prove or disprove that $G$ contains subgraph $K_4$. I came up with this question when I were trying to find Ramsey ...
24 views

701 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.
376 views

277 views

### Ramsey Number proof: $R(3,3,3,3)\leq 4(R(3,3,3)-1) + 2$

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 ...
12 views

### What is the smallest $n$-uniform transversal of $\binom{[2n+2]}{2n}$?

For a family of sets $F \subseteq 2^{[m]}$, let $T \subseteq \binom{[m]}{n}$ an $n$-uniform transversal of $F$ if and only if $\forall f \in F~\exists t \in T: t \subseteq f$. In other words, each ...
85 views

38 views

### What's the deal with Ramsey graph theory with vertex-colourings instead of edge-colourings?

As in the edge-colouring case, we can talk of a $r$-Ramsey graph $R$ for some (finite) graph $G$ wrt. vertex-colouring, i.e. such that for every $r$-colouring of the vertices of $R$ there is a copy of ...
63 views

### A combinatorial proof for a bound on diagonal Ramsey numbers

I wish to prove $R(p,p)\leq\frac{2^{2p-2}}{\sqrt{p}}$ combinatorially. I have proved this algebraically through the definition of the binomial coefficient but I would much prefer a proof from ...
1k views

### Graham's Number : Why so big?

Can someone give me an idea of how R.Graham reached Graham's Number as an upper bound on the solution of the related problem ? Thanks !
34 views

### Prove that a function described as below exists

$R(n,k,l)$ is defined like this : Imagine we have a set and we want to color every subset of it having $k$ elements with $n$ colors such that at the end of coloring, there exists a subset with $l$ ...
44 views

### Approaching Ramsey theory in a unified way

Ramsey theory consists of seemingly diverse results like van der Waerden theorem and Ramsey theorem. There does not seem any apparent connection between these beyond the usual "Order within disorder" ...
11 views

### prove that $R^*(r+1,k;a_1,…,a_r,k)=R^*(r,k;a_1,…,a_r)$

Imagine we have a set with $n$ members. we want to color $k-subsets$ of this set with $r$ colors called $c_1,\ldots,c_r$ such that one of these things happen : - we have a set with $a_1$ members such ...
53 views

### an edge coloring of $k_{16}$ with no monochromatic triangle [closed]

My plan is to show that $R(3,3,3)$ is more than 16. So, i want to prove it with graph-theory. i know i should find an edge coloring of $k_{16}$ which contains no monochromatic triangles. Can anyone ...
23 views

### can we find a $k_4$ colored with 1 color in a $k_8$ which is colored with just 2 colors?

Assume that we define edge coloring in this way : An edge coloring of a graph is an assignment of "colors" to the edges of the graph. So, now imagine we have a $K_8$ which has edges colored with just ...
69 views

### Uses of Ramsey Theory in Astronomy?

In the last paragraph of a Scientific American article of July 1990 that can be found here http://www.math.ucsd.edu/~ronspubs/90_06_ramsey_theory.pdf Graham and Spencer write "Today we can easily ...
65 views

### Ramsey counter examples

I do not know of any solution or if it's an open problem: Let $R(i,i)=k$, therefore there exists a counter examples with blue and red edges for a clique of size $k-1$. Does there exist a counter-...
Let $A$ be an infinite set of points in the plane, with no three points of $A$ collinear. I want to prove that $A$ contains an infinite set $B$ such that no point of $B$ is a convex combination of ...
I am reading Section on Euclidean Ramsey Theory in Ronald Graham's Rudiments of Ramsey Theory. Exercise 7.3 states that Show that if $E^2$ is covered by two closed sets of colors then every 3-...