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

learn more… | top users | synonyms

2
votes
0answers
23 views

Prove that there exists a one-color $K_3$ in a $K_{17}$ which is colored with three colors

Assume that we have a $K_{17}$ and we color every edge of it with 3 colors ( Like Red, Blue & green ). Prove that for every coloring of $K_{17}$ with 3 colors, After coloring, We have a ...
0
votes
2answers
566 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 ...
1
vote
1answer
30 views

Prove that every edge-coloring of $K_{17}$ with $3$ colors contains a monochromatic $K_3$. [duplicate]

Also, Prove that every edge-coloring of $K_6$ with $2$ colors contains at least two monochromatic copies of $K_3.$ I have no idea how to start these problems. What should I do?
1
vote
1answer
35 views

Total number of gifts given at the end of a party

The following is true for n guests at a Christmas party: ...
0
votes
1answer
28 views

Colouring $K_{2s-1}$

Suppose we 2-colour $K_{2s-1}$ such that no vertex has more than one blue edge incident to it, prove that the graph contains a red $K_s$. I've never seen a Ramsey theory question like this and am ...
2
votes
1answer
29 views

Graph Theory Proof that R(3,4)=9

The attatched is supposed to prove that $R(3,4)=9$ . One line say says there is no red $K_3$ in the two-colouring of $K_8$ What is it talking about?- I can see plenty of red triangles! (with corners ...
0
votes
1answer
37 views

Ramsey Number algorithm

In general is there an algorithm to obtain Ramsey Number? For example how should I approach to get $R(2K_2, 2K_2)$ or R(3, 2K_2)?
7
votes
1answer
162 views

in every coloring $1,…,n$ there are distinct integers $a,b,c,d$ such that $a+b+c=d$

Prove that for every $k$ there is a finite integer $n = n(k)$ so that for any coloring of the integers $1, 2, . . . , n$ by $k$ colors there are distinct integers $a, b, c$ and $d$ of the same color ...
3
votes
0answers
48 views

Coloring classes of $\{1,2,3,\dots,n\}$

I'm trying to prove the following statement There is an integer $n_0$ such that for any $n\ge n_0$, in every $9$-coloring of $\{1,2,3,\dots,n\}$, one of the $9$ color classes contains $4$ integers ...
0
votes
0answers
22 views

expressability of finite and infinite ramsey theorems in Peano arithmetic

finite ramsey theorem: for all e,k,r natural numbers, there exists a least natural number m=R(e,r,k) so that for all sets M when cardinality of M is larger or equal m and all of the e- tuples of M are ...
2
votes
1answer
37 views

Ramsey theorems for the naturals and for general infinite sets

In reverse mathematics and in recursion theory, the infinite Ramsey theorems are usually stated in terms of coloring of $[\Bbb N]^n$. How do these (not) imply the Ramsey theorems for general infinite ...
0
votes
0answers
6 views

Sufficiently many points in $\mathbb{R}^d$ must contain $m$ points forming the vertices of a convex polytope?

Let us say that a set of points in $\mathbb{R}^d$ is minimal if it forms exactly the set of vertices of a convex polytope. Equivalently, no proper subset of the points has the same convex hull; no ...
1
vote
2answers
51 views

Graph or its Complement contains a triangle.

How do I prove that the graph with at least 6 vertices or its complement contains a triangle? Do I have to prove that if a graph contains a triangle, then its complement doesn't contain, and the ...
0
votes
1answer
27 views

Prove that if $n > 1$ such that $n \to (a,b)$ and $m > n$, then $m \to (a,b)$.

I've simplified the question's notation to read as follows, If $n > 1$ such that every graph $H$ on $n$ vertices has $\alpha(H) \ge a$ or $\omega(H) \ge b$ and $m > n$, then every graph $G$ ...
0
votes
1answer
22 views

Find a graph with 5 vertices such that $\omega(G) = 2$ and $\alpha(G) = 2$.

I am trying to show that the following statement is false by providing a drawn graph as a counterexample. I've been pointed in the right direction that the statement is only true for at least 6 ...
2
votes
1answer
87 views

How do I get this upper bound for Ramsey numbers: $R_k \le \left \lfloor k!e \right \rfloor + 1$?

For every integer $k \ge 2$, $$R_k \le \left \lfloor k!e \right \rfloor + 1$$ where $R_k$ denotes $R(\underbrace{{3, 3, \ldots, 3}}_{k})$.
2
votes
1answer
74 views

Ramsey lower bounds

I'm doing some self study on Ramsey graph theory. One of the first theorems concerning lower bounds shows that if $${n \choose k} \cdot \frac {1}{2^{( \frac {k}{2}-1)}} <1$$ then $N(k,k)> n$ ...
1
vote
0answers
120 views

Algebra in Erdős's proof of lower bound for Ramsey number

A well known proof by Erdős shows a lower bound on the Ramsey number $r(k,k)$ using the probabilistic method. The theorem goes thusly: Let $n,\, k\in\mathbb{N}$ such that ${n \choose k}2^{1-{k ...
3
votes
1answer
657 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.
3
votes
1answer
351 views

Ramsey Number Inequality: $R(\underbrace{3,3,…,3,3}_{k+1}) \le (k+1)(R(\underbrace{3,3,…3}_k)-1)+2$

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$ ...
1
vote
0answers
98 views

Proving an inequality on Ramsey numbers by induction: $t_{r+1} \leq (r+1) (t_r - 1) + 2$ [duplicate]

Not sure how to proceed. I'm trying to prove that the following inequality is true. I know that $t_2 = 6$ and $t_3=17$ from the problem statement. The base case is obvious. $t_{r+1} \leq (r+1) (t_r ...
3
votes
1answer
272 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 ...
0
votes
0answers
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 ...
2
votes
0answers
84 views

Let $n \ge 6$. Prove that it is not possible to partition the edges of $K_n$ into floor($\frac{n}{6}$) planar subgraphs. [duplicate]

Any hints will be appreciated. Here are some things I thought about: Since $K_n$ is a complete graph, it must be $(n - 1)$ regular The sum of the degree of all its vertices is $n(n - 1)$ There are ...
2
votes
0answers
111 views

Number of edges needed for good colouring in Ramsey graph theory

Given $n$, consider the complete graph $K_{R(n)-1}$, where $R(n)$ is the diagonal Ramsey number. So there exist $2$-colourings of the edges of $K_{R(n)-1}$ without a monochromatic copy of $K_n$. ...
2
votes
2answers
52 views

Prove that the Ramsey number $R(4,4;3) = 13$

Prove that the Ramsey number $R(4,4;3) = 13$. I don't know how to deal with the Ramsey number $R(p_1,p_2,...,p_k;r)$ where r is larger than 2. Is there any useful inequality or construction of ...
0
votes
0answers
12 views

An extremal combinatorics problem

Given $n\in\Bbb N$, $\alpha\geq1$ denote $f(n,\alpha)$ as worst case minimum number of columns among all $n\times n^\alpha$ $0/1$ matrices with every row summing to $>\frac{n^\alpha}2$ that is ...
1
vote
1answer
47 views

Coloring Equilateral Triangles in $\mathbb R^n$

We start with this Example: No matter in which way you color the points of $\mathbb R^4$ with two colors, you can always find an equilateral triangle with vertices of the same color. In fact in ...
1
vote
0answers
36 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 ...
3
votes
0answers
56 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 ...
14
votes
1answer
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 !
0
votes
0answers
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$ ...
1
vote
1answer
40 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" ...
0
votes
0answers
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 ...
-1
votes
1answer
50 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 ...
0
votes
1answer
22 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 ...
1
vote
1answer
65 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 ...
2
votes
1answer
62 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 ...
3
votes
1answer
71 views

Infinitely many points in plane s.t. no point is a convex combination of other points

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 ...
0
votes
0answers
26 views

Monochromatic triangle in two closed set which cover the plane

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 ...
0
votes
1answer
37 views

Show that in any group of 9 people there is always a subgroup of 3 mutual strangers or a subgroup of 4 mutual acquaintances.

Show that in any group of 9 people there is always a subgroup of 3 mutual strangers or a subgroup of 4 mutual acquaintances. I know that this is an application of Ramsey's Theorem, but I'm not sure ...
3
votes
2answers
98 views

What are some important applications of the Erdős-Szekeres Theorem?

Erdős-Szekeres Theorem: Any finite sequence of $n^2+1$ real numbers contains a monotonic subsequence of length at least $n+1$. I was wondering what are the most important applications of the ...
0
votes
1answer
76 views

Lower bound for Ramsey numbers: $R( n + 2 , 3 )>3n$

I need to prove the following inequality: $$R( n + 2 , 3 )>3n$$ where $n>1$ and $R(s,t)$ is a Ramsey number. The most general way to prove such inequalities is to paint a graph with $3n$ ...
2
votes
0answers
37 views

Canonical colorings over $ \omega $

Given a natural number n, let $ c:[X]^n \to \omega $ be a coloring by arbitrary many colors, where $X$ is an infinite countable set. Then there exists an infinite subset $ H $ of $ X $ for which the ...
2
votes
1answer
94 views

Proof involving Ramsey numbers

$S$ is a set of R(m,m;3) points in the plane in which no 3 points are collinear. I am trying to prove that $S$ contains $m$ points that form a convex $m$-gon. I have tried using similar logic to the ...
0
votes
0answers
22 views

Ramsey number for tree and complete graph [duplicate]

I am having a lot of trouble understanding Ramsey theory. I am working on an exercise that asks for the Ramsey number $R(T,K_{1,n+1})$ where $T$ is a tree with $m$ edges and $n$ is a multiple of $m$. ...
0
votes
1answer
16 views

Independent Set of Product Graph and Ramsey Number

For two graphs $G,H$, define $G\otimes H$: it has vertex $V(G)\times V(H)$, $(v_1,v_2)(v_1',v_2')\in E(G\otimes H)$ if it satisfies all the following three requirments (i) $(v_1,v_2)\neq (v_1',v_2')$ ...
4
votes
0answers
39 views

Maximum $K_6$-free graph on $15$ vertices?

My question is, suppose we have $15$ vertices. What is the maximum number of edges we can add between these vertices, each with a fixed colored red or blue, so that there is no monochromatic triangle? ...
1
vote
0answers
108 views

Finding the exact value for $H(7)$

The graphs that I work with are all complete, each edge is colored red or blue, and each vertex is colored red or blue. $\textbf{Definition:}$ A graph is $\textit{Happy}$ if there exists a vertex ...
1
vote
1answer
68 views

Finite coloring of $[\omega]^{<\omega}$.

It is known that Ramsey theorem does not hold for finite colorings of $[\omega]^{<\omega}$. So I am interested in this "partial" result: First let $S_n = ]n, +\infty[$ be the set of natural ...