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
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 ...
3
votes
1answer
207 views

Ramsey Type problem (variant of people at a party)

There is $n$ people at a party. Prove that there are two people such that, of the remaining $n-2$ people, there are at least $\lfloor n/2\rfloor-1$ of them, each of whom either knows both or else ...
4
votes
1answer
80 views

Euclidean Ramsey theory problem

Let $k\geq 1$ be given. Consider the following statement: For all (non equilateral) triangles (represented by 3 points in $\mathbb R^2$) and for all $k$-colorings of $\mathbb R^2$ there exists a ...
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
3answers
253 views

Ramsey's theorem [closed]

I'm reading introduction to combinatorics and encountered an exercise I couldn't answer Let S be a set of six points in the plane, with no three of the points collinear. Color either red or blue each ...
1
vote
2answers
85 views

Reconciling two statements of Ramsey's Theorem.

In the appendix to Shelah's book on Classification Theory: THEOREM 2.1 (Ramsey's Theorem): (1) For any infinite ordered set $I$, and $n$-place function $f$ from $I$, with range of cardinality ...
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 ...
4
votes
2answers
320 views

What is Ramsey Theory ? what is its own importance in maths?

3 days ago , i had a discussion with a close friend who studies physics - still a student - . and i was telling her about the biggest known numbers in maths , so i told her about numbers such googol ...
5
votes
0answers
126 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 ...
2
votes
1answer
66 views

Prove a relation related to sets

In a city, among each pair of people, there can be exactly one of k different relationships (relationships are symmetric). A crowd is a set of three people in which every pair have the same relation. ...
3
votes
1answer
162 views

Accessible Applications of Graph Ramsey Theory

I am giving a short lecture series on graph Ramsey theory to a group of gifted high school seniors. The brief outline is to start with the "six people at a dinner party" question, transition into the ...
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 ...
1
vote
1answer
46 views

n-coloring of a graph using Schur's Theorem

Using Schur Theorem I have to prove that for any $n\geq 1$ there is a number $f(n)$ such that if $A=${$2,3,4,...f(n)$} is partitioned into n sets $A_1$, $A_2$...$A_n$ there is a $j\in${1,2,...,n} ...
4
votes
1answer
112 views

Arithmetic progression in a subset of $\mathbb N$

What non-trivial sufficient and/or necessary conditions are there for existence an arithmetic progression (finite or infinite length) in an infinite subset of $\mathbb N$.
11
votes
5answers
765 views

Why König's lemma isn't “obvious”?

I keep facing König's lemma "Every finitely branching infinite tree over $\mathbb{N}$ has infinite branch". Why it is not taken "obvious" but needs a careful proof? It seems somewhat obvious, but I ...
1
vote
1answer
56 views

Ramsey number R(3,n)

I want to prove that $R(3,n) \ge 2(n-1)$ but I am not sure how to do that since using induction does not seem to work. Could anyone give me an idea? Thank you!
6
votes
2answers
104 views

Two subsets and their union have same color

Color all nonempty subsets of $[n] = \{1,2,\ldots,n\}$ with colors $1,2,\ldots,r$. Show that, for all large enough $n$, there exist two disjoint nonempty subsets $A,B \subseteq [n]$ such that ...
0
votes
1answer
79 views

Ramsey's theory inequality with $t$-subsets

Let $q_{1},\, q_{2}, \ldots, q_{k},t$ be positive integers, where $q_{1}\geq t, q_{2}\geq t, \ldots, q_{k}\geq t$. Let $m$ be the largest of $q_{1},q_{2}, \ldots, q_{k}$. Show that ...
2
votes
1answer
57 views

The Ramsey number $r(t,t,q)$ with $q\geq t$

Let q and t be positive integers with $q\geq t$. Determine the Ramsey number $r_t(t,t,q)$. This is from the book Introductory Combinatorics by Brualdi, and in the back it says the answer is q without ...
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
2answers
321 views

Permutation of 1…9 with no ascending or descending subsequence of length 4

Arrange the numbers $1,2,...,9$ in such an order that no four of them appear (adjacently or otherwise) in ascending or descending order. Show that there is no arrangement of the numbers $1,2,...,10$ ...
2
votes
2answers
141 views

What is a Ramsey Graph?

What is a ramsey graph and What is its relation to RamseyTheorem? In Ramsey Theorem: for a pairs of parameters (r,b) there exists an n such that for every (edge-)coloring of the complete graph on n ...
1
vote
1answer
83 views

Ramsey and Random Graph

By considering the random graph G(n,p), show that $$R(4,k)>\left ( \dfrac{k}{3\log k} \right )^{3/2} $$ Improve this bound as much as you can.
4
votes
2answers
204 views

Guaranteeing an integer lattice point centroid

My question is this: Writing $n(4)$ to be the minimum number of integer lattice points in the plane so that some four of them must determine an integer lattice point centroid, show that $n(4)=13$. I ...
1
vote
1answer
60 views

Notation Confusion

This is an extremely soft question. This is a definition from Ramsey Theory: $n\to (l_1,\ldots, l_r)^k$ if for every $r$-coloring of $[n]^k$, there exists $i$, $1\le i\le r$, and a set $T$, ...
4
votes
1answer
105 views

Do Ramsey idempotent ultrafilters exist?

I was studying idempotent ultrafilters when I saw that no principal ultrafilter could ever be idempotent, because $\left\langle n \right\rangle \oplus \left\langle n \right\rangle = \left\langle 2n ...
3
votes
1answer
136 views

example of a finite coloring without infinite monochromatic set closed under addition

I am studying some theorems on combinatorial set theory, especially Ramsey theorem and Hindman's theorem. I think I am going to ask a silly question, but I am too much involved in the subject to think ...
1
vote
1answer
196 views

A Problem about friends and strangers using Ramsey's Theory

Question: Consider a group of 8 people, each pair of which are either friends or enemies. Show that if some person in the group has at least 6 friends, then there are 4 people who are mutual friends ...
10
votes
2answers
280 views

How many 2-edge-colourings of $K_n$ are there?

I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially ...
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 ...
2
votes
1answer
207 views

Ramsey Number Inequality

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$ ...
3
votes
1answer
104 views

Number of gifts given at the end of a party

So I'm working on a problem that has to do with Ramsey Theory. We have $n$ guests at a christmas party. We know two things about them. In any group of three there are two people who do not know each ...
2
votes
1answer
179 views

Ramsey Number proof

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
1answer
90 views

Edge coloring graph vertices probability

How to show the following: Let $R(k,t)$ denote the Ramsey function, that is the minimal number $n$ so that if the edges of a complete graph $K_n$ on $n$ vertices are each colored red or blue, then ...
2
votes
1answer
141 views

Upper bound for ramsey number $r(a_1,\ldots, a_m)$

I am looking for any (finite) upper bound of the ramsey number $r(a_1,\ldots, a_m)$. I can prove the well known fact for any positive integers $a,b$ there is a $c$ for which $c\ge r(a,b)$ by taking ...
3
votes
1answer
339 views

Graph theory dinner party problem

In a party of 6 people is it true that there exists four people either all do or all do not knowing each Other? I know it's false, and have the solution but not quite sure where to begin with the ...
0
votes
1answer
192 views

Graph theory mutual acquaintance and mutual strangers problem

Show that there is a gathering of five people in which there are no three people who all know each other, and no three people none of whom knows either of the other two. There is a solution in the ...
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 ...
4
votes
2answers
148 views

Counterexample for $R(4,4) \neq 8$

I try to find a counterexample for $R(4,4)\neq 8$. (R is the Ramsey-number). I drew a graph with 8 vedges and I coloured all edges $(v_i,v_j)$ with $i-j =\pm 2,4,6$ in the same colour (for example ...
4
votes
1answer
146 views

A problem in prime number theory

I was wondering if anybody here might provide me with a hint for this rather innocuous-looking problem: If $X:= \{pq: p, q \mbox{ are prime numbers and } p\neq q\}.$ In addition, let us suppose that ...
4
votes
1answer
122 views

Ramsey number for paths

Let $n = R(P_{r+1}, c)$ be the smallest integer such that if $K_n$ is $c$-edge-coloured, then it contains a monochromatic subgraph isomorphic to $P_{r+1}$, the path of length $r$. I need to show that ...
6
votes
3answers
253 views

Does a red/blue coloring of the infinite subsets of $\mathbb{N}$ necessarily give an infinite monochromatic $M\subset \mathbb{N}$?

The infinite Ramsey theorem states that for any $n$, if all the subsets of $\mathbb{N}$ of size $n$ are colored red/blue, then there is an infinite $M$ all of whose subsets of size $n$ are ...
0
votes
2answers
179 views

How I can prove Ramsey number R(2,3,4) > 8?

I need to prove $R(2,3,4) > 8$ with Ramsey theory. How can I do that?
1
vote
1answer
73 views

Simple proof that W(3,3)=27?

I was wondering that if there exists a simple proof that the van der Warden's number W(3,3) (the smallest positive integer $n$ such that any 3-coloring of the set $\{1, 2, ..., n\}$ has a ...
5
votes
3answers
613 views

Good way to learn Ramsey Theory

What are some good books on Ramsey theory? I have Van Lints book on Combinatorics: is this enough preparation to start reading about Ramsey theory? I want a book that includes important results and ...
2
votes
0answers
40 views

How to prove some properties of partitions of finite subsets of N? [duplicate]

Possible Duplicate: Any partition of {1,2,..,9} must contain a 3-Term Arithmetic Progression The problem is as such: Prove that there is not a partition of $N_9 = \{1, 2, 3, 4, 5, 6, 7, ...
3
votes
1answer
214 views

Amalgamation of graphs

I am trying to understand the definition of amalgamation of a $n+1$-partite graph as explained here(first few lines of page 4). We have a $n+1$-partite graph $G$ with partite sets $V_0,V_1,\cdots,V_n$ ...
3
votes
1answer
94 views

Any forest on 5 or more vertices contains an independent set of size 3.

I am looking for a short proof of this fact. This is clearly true by drawing these trees, but I am having trouble putting it into writing. Somehow I need to select 3 of the 5 vertices and show that ...
12
votes
1answer
317 views

Monochromatic squares in a colored plane

Color every point in the real plane using the colors blue,yellow only. It can be shown that there exists a rectangle that has all vertices with the same color. Is it possible to show that there exists ...
6
votes
1answer
166 views

Any partition of $\{1,2,\ldots,9\}$ must contain a $3$-Term Arithmetic Progression

Prove that for any way of dividing the set $X=\{1,2,3,\dots,9\}$ into $2$ sets, there always exist at least one arithmetic progression of length $3$ in one of the two sets.