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

0
votes
2answers
52 views

Coloring of $K_{17}$

For any 3-coloring of $K_{17}$ I have to show there exists either a red, blue or green triangle. To start, can I use proof by contradiction with color red, blue, green? So $(0,0,136)$ means all 136 ...
4
votes
1answer
117 views

The Erdős-Szekeres problem on points in convex position

The Erdős-Szekeres problem on points in convex position and its proof using Ramsey theorem are well know. The problem goes like this: For every natural number $k$ there exists a number $n(k)$ such ...
1
vote
1answer
129 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 ...
1
vote
1answer
89 views

Combinatorial Question using ramsey's theory or pigeonhole principle??

We are currently going over pigeonhole principle, ramsey's theorem (graphs and such). Stuck on this particular question: Within a group of an odd number of people, show that at least one person knows ...
0
votes
1answer
65 views

Ramsey Numbers and edge coloring

Show that for every $k \in\mathbb{N}$ there exists an $n \in\mathbb{N}$, where $n ≤ 3k!$ such that if $K_n$ is coloured in $k$ colours then we can find in $K_n$ a triangle whose edges are of the same ...
0
votes
1answer
81 views

Two coloring questions and ramsays number

What is the smallest $n$ such that every 2-coloring of edges of $K_n$ contains a red or blue 4-cycle (not $K_4$)? I am given that $R(4,4) \le 18$ and $R(3,5) \le 14$ Any help is greatly appreciated!
6
votes
0answers
233 views

van der Waerden's original proof

I am looking for a book/site which has the english translation of the proof of van der Waerden's theorem as presented by van der Waerden himself. In other words is the translation of the paper: ...
6
votes
0answers
205 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 ...
5
votes
0answers
169 views

number of potential couples

A potential couple is a pair of a man and a woman that like each other (assume that 'like' is a symmetric relation). Given a group of $M$ men and $W$ women, I want to know how many different ...
4
votes
0answers
48 views

Ramsey number $R(K_4,K_4,K_4)$.

I've done a bit of googling, but I can't seem to locate any bounds for $R(4,4,4)$. Here, $R(n_1,n_2,n_3)$ is the generalized Ramsey number where $n_1,n_2,n_3$ are orders of complete graphs. So, in ...
4
votes
0answers
227 views

History of Hindman's Theorem

At this blogpost about Hindman's Theorem, I read the following lines: 'I love the odd history so allow me to digress... etc. ' This sentence made me curious to know what this history looks ...
4
votes
0answers
81 views

Arbitrary ratio sequences on a partition of $\mathbb{R}$ (Partition regularity of fixed ratio sequences)

Background: This question arose purely recreationally and doesn't really fit into any context that I know of. Let $A \sqcup B = \mathbb{R}$ be a partition of the ...
3
votes
0answers
31 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 ...
3
votes
0answers
65 views

Conjectured Value of Ramsey Number $R(3,10)$

It is known that the value of the Ramsey number $R(3,10)$ is either 40, 41, or 42. Have any experts in the field offered a conjecture as to which it might be?
2
votes
0answers
103 views

Van der Waerden type numbers (for geometric progressions)

Van der Waerden theorem is true also for geometric progressions. Is there anything interesting in van der Waerden type numbers $ W'(r,k) $ derived from this version? ($ W'(r,k) $ is such that if the ...
2
votes
0answers
25 views

Questions on $R(K_l + \overline{K_t}, T_s) \le l(s-1)+t$

Following C. C. Rousseau and J. Sheehan "A class of ramsey problems involving trees" Journal of London Math. Soc. $1978$, I have some dudes about their proof for $R(K_l + \overline{K_t}, T_s) \le ...
2
votes
0answers
67 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 ...
2
votes
0answers
78 views

Monochromatic degenerate triangles in a two-coloring of the plane

In a similar vein to a question I asked a few days ago: Do all two-colorings of $\mathbb{R}^2$ contain three points of the same color which form the vertices of a degenerate triangle of side-lengths ...
1
vote
0answers
18 views

Ellis semigroup

I have only seen the construction of the Ellis semigroup applied to a group endowed with the discrete topology. Does the same idea works for any topological group? If not, where does it go wrong? (I ...
1
vote
0answers
63 views

Principal matrix, Ramsey theorem

Question: Let m be given. Show that if n is large enough, then every n-by-n 0, 1-matrix has a principal submatrix of size m in which all elements above the diagonal are the same, and all elements ...
1
vote
0answers
16 views

Equivalence of Theorems; the sphere on $\ell^2$ is finitely oscillation stable.

I just started reading the book Dynamics of Infinite-dimensional Groups, by Pestov, and right in the introduction the following theorem by Milman is cited: Let $\mathbb{S}^\infty$ denote the sphere in ...
1
vote
0answers
17 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 ...
1
vote
0answers
22 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.
1
vote
0answers
56 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 ...
1
vote
0answers
38 views

Probability that a subset of a degree-regular graph shares at least a certain number of mutual connections

Consider a set of $n$ vertices of common degree $p$. What is the probability that some subset of $x$ vertices from $n$ share $q$ mutual connections within that group of size $x$? i.e. If we have ...
1
vote
0answers
66 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 ...
1
vote
0answers
57 views

Link between Ramsey Theory, random graphs and spin glasses

As all three theories study the emergence of order, it would be natural if there were some links between: Ramsey theory; random graphs; spin glasses. Is there a textbook or an article that ...
1
vote
0answers
142 views

What was done to calculate the Ramsey numbers using a quantum computer?

I recently came across this paper titled Experimental determination of Ramsey numbers with quantum annealing I was wondering what exactly the gist of the paper, as I read it, it seems rather ...
0
votes
0answers
18 views

Upper limit on Ramsey number $R(a,b)$

How could we prove that if $R(a-1,b)$ and $R(a,b-1)$ are both even then $R(a,b)$ is strictly less than $R(a-1,b)+R(a,b-1)$ or $\begin{equation} R(a,b) < R(a-1,b)+R(a,b-1) \end{equation}$
0
votes
0answers
39 views

Salem Spencer Theorem

The Salem Spencer Theorem seems to be a very interesting combinatorial theorem. This blog motivated me to read more about it. I understand the statement of the theorem, however the proof isn't very ...
0
votes
0answers
23 views

Reference for Ramsey Numbers

Just wondering about diagonal Ramsey numbers $R(n)$. Can anyone provide reference on either of the following? Have there been any notable attempts to make sense of $R(n)$ by using non-combinatorial ...
0
votes
0answers
14 views

Canonical colorings over $ \omega $

Given a natural number n, let $ c:[X]^n \to \omega $ be a coloring by arbitrary many colors. Then there exists a subset $ H $ of $ X $ for which the restriction of $ c $ to $ [H]^n $ is canonical. ...
0
votes
0answers
26 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 ...
0
votes
0answers
59 views

Why was the Grahams Number needed?

I did some reasearch about the Grahams number and the proof in which context the number was mentioned as an upper bound. Now I also know that recently this upper bound has been lowered to $2 \uparrow ...
0
votes
0answers
37 views

Erdős-Sós conjecture tightest upper bound

The Erdős-Sós conjecture states that any graph of average degree greater than or equal to $k-2$ contains a copy of any tree on $k$ vertices. Does anyone know the current best upper bound on the ...
0
votes
0answers
30 views

Question about a possible relationship between additive and Bergelson multiplicative upper densities

Let $A \subseteq \mathbb{N}$; let $\mathbb{P} \subset \mathbb{N}$ be the set of all primes. Let $\forall n \in \mathbb{N}, F_n = \{a_n \prod_{i=1}^n (p_i^{r_i}): a_n \in \mathbb{N}, p_i \in ...
0
votes
0answers
72 views

proving an inequality by induction

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