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
43 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 ...
1
vote
1answer
94 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 ...
0
votes
1answer
58 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
74 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!
7
votes
0answers
221 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 !
6
votes
0answers
163 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: ...
5
votes
0answers
127 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
71 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
52 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?
3
votes
0answers
81 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 ...
3
votes
0answers
153 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 ...
2
votes
0answers
84 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
19 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
54 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
76 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
0answers
71 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
32 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
54 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
48 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
118 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
23 views

An easy definition of an $n$-dimensional affine cube

In a few weeks I'm giving a presentation on the History of Ramsey Theory and I want to start off with Hilbert's cube lemma. The only problem is that the pre-requisites for this course is only ...
0
votes
0answers
38 views

What is the explanation for the $64$ in Graham's number $g_{64}$?

As in, why does the iteration of the function until $g_{64}$ guarantee this property that defines Graham's number? Why was this number chosen? If I had to guess (emphasis on guess), I'd say that the ...
0
votes
0answers
29 views

Hereditary and Pre-compact implies Compact

Lemma II.3.20 in the book Ramsey Methods in Analysis by Argyros and Todorcevic states that a pre-compact hereditary family $\mathcal{F}$ of finite subsets of $\mathbb{N}$ is compact. It is supposed to ...
0
votes
0answers
33 views

Some small (and probably easy) implication from combinatorics paper

I'm reading https://people.math.osu.edu/bergelson.1/PolSz.pdf . Question is about part from (1.7) on page 16. Why $ \lambda(\chi_{1})=\lambda(\chi_{1}) $? There's no problem if in 4-th verse ...
0
votes
0answers
47 views

2-colorings of arithmetic progression

Consider the following classical result: $\forall r \in \mathbb N : \exists N\in \mathbb N$ such that every 2-colored arithmetic progression of length N contains a monochromatic arithmetic ...
0
votes
0answers
63 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 ...