# 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?"

33 views

### Why is the lower bound 62?

Why is the lower bound of the minimum amount of points needed so that a $4$-coloring leaves at least one monochromatic triangle $62$, and not $66$? A lower bound of $66$ would seem obvious, since it ...
300 views

### Ramsey Numbers r(2, n) = n [duplicate]

How do you prove that r(2, n) = n in Ramsey numbers? We have to show that r(2,n)<=n and that r(2,n) >= n.
44 views

127 views

### Verify that R(p,2) = R(2,p) = p, where R is the Ramsey number

Verify that $R(p,2) = R(2,p) = p$, where $R$ is the Ramsey number It just seems obvious that $R(p,2) = R(2,p)$. But why do $R(p,2)$ and $R(2,p)$ both equal p?
43 views

### Infinite graphs satisfying a certain Ramsey property

Let $G$ be a countably infinite graph. If $G$ has cliques of arbitrarily large finite size, then $G$ satisfies the following property, which I will call $(*)$: for any $r\in \mathbb{N}$ and any $r$-...
231 views

### A sequence of $n^2$ real numbers which contains no monotonic subsequence of more than $n$ terms

I'm following a Combinatorics course at the moment, and have recent proved the Erdős–Szekeres Theorem (or, at least, some variation of): A sequence of length $n^2 + 1$ either contains an ...
148 views

### Can the complete graph $K_9$, be 2-coloured with no blue $K_4$ or red triangles?

I am working on the following problem on 2-coloured complete graphs: $K_9$ is coloured red and blue and contains no red triangle and no blue $K_4$ then every vertex must have red degree 3 and ...
162 views

### Monochromatic Solutions

I recently came across this paper: http://borisalexeev.com/pdf/foxgraham.pdf "On Minimal Colorings Without Monochromatic Solutions To a Linear Equation" Can someone explain in clearer terms what ...
51 views

### $4$-cycle of the same color in $K_n$

Let $k$ be a fixed positive integer. All edges of the complete graph $K_n$ are colored in one of $k$ colors. What is the least $n$ such that there always exists a $4$-cycle of the same color? This ...
36 views

### Ramsey Upper Bound improvement

I am trying to understand the upper bound that David Conlon produced for the diagonal Ramsey Numbers $$R(n+1,n+1) \leq n^{-c \frac { log n}{log \;{log n}}} \binom {2n}{n}$$ With the binomial theorem ...
21 views

### on binary strings without using Ramsey Theorem

Using the Ramsey Theorem Let $X$ be some countably infinite set and colour the elements of $X(n)$ (the subsets of $X$ of size $n$) in $c$ different colours. Then there exists some ...
63 views

### Deriving Van der Waerden's theorem from Rado's theorem

In Ramsey Theory Van der Waerden theorem states that, Let $k,r$ be positive integers. Then in every partitioning of the positive integers into $r$ classes there is one class which contains an ...
64 views

### combinatorics- persons in group

Let $$n = \binom {k + b-2}{k-1} \text{ and }k, b\ge 2$$ Prove that in each group of at least n persons there is k person is familiar with everybody or there are b persons two did not know each ...
25 views

### Lower Bound on VDW Numbers

I am trying to find the original proof given by E. Berlekamp that for prime $p$, $$W(p+1) \ge p2^p.$$ All the papers that I have searched only reference this result and give no proof.
23 views

### If $m,n$ are integers $\gt 2$ then $R(m,n) \leq R(m-1,n)+R(m,n-1)$ [duplicate]

THIS IS NOT THE DUPLICATE OF ABOVE BECAUSE:I require pigeonhole principle argument to my doubt which is not stated in the answer to above question... I missed my lecture the day the following ...
213 views

### Is Graham's number actually valid?

I had a few questions regarding Graham's number and Ramsey theory. I understand what Graham's number is and what it is attempting to solve. My question is, is a hypercube with dimension equal to ...
326 views

### Chromatic Triangles on a k17 graph

If the edges of the complete graph K17 (on 17 vertices with no three collinear) are each colored one of three colours can it be proven to have two or more monochromatic triangles?
128 views

39 views

96 views

### Ramsey Theory: Showing the existence of a special set of natural numbers.

Show that there is an infinite set of natural numbers such that the sum of any two elements has an even number of prime factors. My attempt: Define a coloring on the doubletons of $\mathbb{N}$, that ...
122 views

### Mixed Tsirelson Norm

The following is a definition of a Banach space that is a generalization of the original Tsirelson space. Nowadays such a space is called a Mixed Tsirelson space; it was introduced by Argyros and ...
81 views

### Local Lemma on lower bounding R(k,k)

We aim to prove that if $k \ge 3$ and $e2^{1-\binom{k}{2}}\binom{n}{k-2} \le 1$ then $R(k,k) >n$ Now I understand that we colour the edges of $K_n$ red and black with probability 1/2. For each k-...
66 views

### Give an explicit 2-coloring of the edges of Kn that proves R(k,k)> (k-1)^2

Right now I have: the coloring that there are k-1 subgroups of k-1 vertices. If each of the subgroups contains a connected graph that's one color (like black), and the edges between the subgroups is ...
94 views