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
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
251 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
84 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
310 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
118 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
65 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. ...
2
votes
1answer
155 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
151 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
45 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$.
10
votes
5answers
741 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
55 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
101 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
294 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
137 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
82 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
200 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
58 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
103 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
135 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
192 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
275 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
205 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
176 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
88 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
333 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
183 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
53 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
138 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
142 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
118 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
252 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
177 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
586 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
212 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
91 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
307 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.
0
votes
1answer
70 views

Ramsey's theorem.

For $k=2$, from this post A "geometrical" representation for Ramsey's theorem, how one can deduce the theorem from Constant $f:[\mathbb{N}]^2\to \{1,2\}$ (part 2), or by knowing that ...
1
vote
1answer
456 views

Monochromatic triangle and edge colouring

$r(k) := R(\underbrace{3,3,...,3}_k)$ (I.e. $r(k)$ is the minimum integer $n > 0$ such that every coloring of edges of $K_n$ in $k$ colors is guaranteed to produce a monochromatic triangle.) Show ...
0
votes
1answer
417 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 ...