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

1
vote
1answer
35 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?
0
votes
0answers
21 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
51 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 ...
3
votes
2answers
61 views

Ramsey Numbers involving Cycles, $R(K_3, C_5)$

I've been asked to determine the value of $R(K_3, C_5)$, but I'm having a lot of difficulty putting all the pieces together. We were given the hint of using $R(3,4) = 9$, and I've tried to apply ...
4
votes
2answers
442 views

how to construct 17-vertexed graph for Ramsey number R(3,6)=18

Ramsey number $R(3,6)=18$. How to construct a graph of $17$ nodes which does not contain neither a clique of order $3$ or an independent set of order $6$. could you show me the tactics or the ...
0
votes
0answers
25 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 ...
1
vote
0answers
33 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 ...
15
votes
1answer
2k views

Why are there only a few known Ramsey numbers?

Can someone explain in a simple way, why there are so few known exact Ramsey Numbers? I guess it's because there are no efficient algorithms for this task, but are there so many combinations to test? ...
4
votes
1answer
147 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 ...
3
votes
0answers
53 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
2answers
83 views

How can we apply Ramsey's theorem to solve this problem on matrices?

This is from a problem set in a combinatorics course I am taking, and reads as follows: Let $m\geqslant 1$ be an integer. Prove there exists an $n\geqslant 1$ with he following property: every ...
0
votes
1answer
21 views

Upper bound on number of starting positions of a grid coloring game

Let's play a game! The game has the following rules: Let $G$ be a $N\times N$ grid. To each grid square $(x,y)\in G$, assign either $true$ or $false$; call this mapping $C$ (that is, if $(x,y)$ is ...
3
votes
2answers
335 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
1answer
41 views

Proving an 'obvious' Ramsey upperbound

Here I want to prove the following: $$R(s_{1},s_{2},\ldots ,s_{k}) < R(s_{1}+1,s_{2},\ldots ,s_{k})$$ For $s_{1},\ldots ,s_{k} \in \mathbb{N}$, $s_{i}\geq 2$. (Or can it hold with equality in some ...
6
votes
1answer
291 views

Known bounds and values for Ramsey Numbers

Is there a good online reference that lists known bounds on Ramsey numbers (and is relatively up to date)? The wikipedia page only has numbers for $R_2(n,m)$. I am specifically interested in known ...
1
vote
1answer
42 views

Directory for known bound of Ramsey numbers?

I must admit I'm not a google connoisseur, but I have not been able to find a place where I can find known lower bounds for many Ramsey numbers, something ideal would be if I could insert (3,44) and ...
0
votes
1answer
23 views

What does $N(q_1, q_2, … , q_s ; r)$ mean in van Lint's stating of Ramsey's Theorem?

I've started reading van Lint and Wilson's A Course in Combinatorics and on Theorem 3.3 (Ramsey's Theorem) they use the notation $N(q_1, q_2, ... , q_s ; r)$ without an explanation prior to it. Can ...
0
votes
1answer
26 views

T/F prove for modified Ramsey's theorem

By Ramsey's theorem we know that: $\forall k \in \mathbb N : \exists N \in \mathbb N$ that an arbitrary graph $G$ on a set of vertices $\{1,2,...,N\}$ contains $k$ vertices, which represent either a ...
0
votes
1answer
22 views

Ramsey's Theory — Combinatorics

There are 17 people in a room. Each pair of people are either friends, enemies, or not acquainted. Prove that there is a group of 3 people that are on equal standing with each other (i.e. all 3 are ...
1
vote
1answer
47 views

Hindman's theorem on coloring a set with $n$ colours

Hindman's theorem states that if we colour $\mathbb{N}$ (positive integers) with a finite number of colours $c_1,\ldots,c_n$, then there exists a color $c_i$ and an infinite subset $A \subset ...
2
votes
1answer
66 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 ...
0
votes
0answers
30 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 ...
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 ...
1
vote
0answers
56 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 ...
0
votes
1answer
20 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 ...
2
votes
3answers
53 views

Is there only one counter example in $K_5$ for $R(3,3)$?

Title says it all. And the one that I know is below. (image from wikipedia) My question is: Is there only one counter example in $K_5$ for $R(3,3)$ where $K_5$ is a complete graph of 5 points and ...
1
vote
2answers
823 views

Ramsey Number R(4,4)

In trying to deduce the lower bound of the ramsey number R(4,4) I am following my book's hint and considering the graph with vertex set $\mathbb{Z}_{17}$ in which $\{i,j\}$ is colored red if and only ...
0
votes
1answer
84 views

Homework question about Ramsey numbers

Consider a group of nine people. We know that at least one person, say Adam, knows an even number of people and does not know an even number of people. Show that either Adam and two other people all ...
0
votes
1answer
61 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 ...
1
vote
3answers
30 views

Prove: For any 2 coloring of 2-space, one of the color classes contains points at all distances

We color the 2D-plane either red or blue at every point. Prove that one of the sets (either red or blue), contains two points at distance $D$, for every positive real number $D$.
0
votes
1answer
75 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!
4
votes
1answer
107 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 ...
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 ...
11
votes
2answers
288 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 ...
5
votes
2answers
96 views

Old exam question about well ordering on $\mathbb{R}$

I am not sure how to start tackling this question and would love a hint: Let $<$ the regular order relation on $\mathbb{R}$, and $<_w$ well ordering on $\mathbb{R}$. We define a coloring ...
1
vote
1answer
43 views

Uncountable monochromatic set

Maybe you can help me with that. I was asking myself if you take an uncountable set $S$ and let $S^{(2)}$ be 2-coloured, must there exist an uncountable monochromatic set in $S$?
1
vote
1answer
44 views

Special Ramsey number $r(G)$

With $r(G)$ I refer to the smallest $n$ such that every blue-red colouring of the edges of $K_n$ contains a monochromatic copy of the grpah $G$ (this exists because $r(G)\le R(|G|)$). Now let $I_k$ ...
0
votes
1answer
17 views

Using Ramsey theory to show some properties of subgraph of a directed graph

Let $r > 1$ be an integer. Prove that there is an integer $n_0$ such that for every integer $n\geq n_0$ and every directed graph $G = (\{1,...,n\}, E)$ without loops, $G$ has an induced ...
0
votes
1answer
114 views

Ramsey Number for Star graphs

For two graphs $H_1$ and H2, the Ramsey number $r(H_1, H_2)$ is the minimum number r so that in any red-blue coloring of the edges of the complete graph Kr on r vertices there is necessarily either a ...
3
votes
1answer
213 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 ...
2
votes
1answer
263 views

Algorithm to find a permutation that contains the fewest possible monotone subsequences of length $k$

Fix natural numbers $k,n$, with $k<n$. I want to find a permutation in $S_n$ that contains fewest monotone (increasing or decreasing) subsequences of length $k$. For example the permutation ...
3
votes
0answers
84 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 ...
4
votes
4answers
160 views

How long does a sequence need to be to be guaranteed to have a monotonic subsequence length k?

The sequence 7, 2, 4, 1, 4, 8 has an increasing subsequence length four (2, 4, 4, 8) and a decreasing subsequence length three (7, 4, 1). It has other monotonic (increasing or decreasing) subsequences ...
3
votes
1answer
61 views

Monochromatic solutions to $x_{1}+x_{2}+\cdots+ x_{m}=x_{m+1}$

What is the least $n$ such that any $2$-coloring of $[n]$ has a monochromatic solution to the equation $$x_{1}+x_{2}+\cdots+ x_{m}=x_{m+1}.$$ I think the answer is $m^{2}+m-1$. I have a coloring of ...
3
votes
3answers
239 views

Does “Big Data” Have a Ramsey Theory Problem?

I'm erring on the side of conservatism asking here rather than MO, as it is possible this is a complex question. "Big Data" is the Silicon Valley term for the issues surrounding the huge amounts of ...
4
votes
1answer
123 views

There exist $\{a_{n}\},\{b_{n}\}$ such $\lim_{n\to\infty}\frac{a_{n}}{b_{n}}=c?$

Let $ A$ and $ B$ are two infinite subsets of the natural numbers $\mathbb{N}$, such that $$A\cap B=\emptyset \qquad A\cup B=\mathbb N$$ Question: is it true that for every natural $c>0$, ...
1
vote
3answers
74 views

Why is this binomial coefficient bounded thus?

Source: Miklos Bona, A Walk Through Combinatorics. $$ \forall k\geq 2,\binom{2k-2}{k-1}\leq4^{k-1}.$$ The RHS is the upper bound of the Ramsey number $R(k,k)$. How can I prove the inequality ...
0
votes
2answers
54 views

$k$ colorings of the non empty subsets of $[n]$ gives the same color to two disjoint sets and their union.

This question was already asked but I didn't get enough information from the answer. Here is a link to the question. Here is the question restated. Show that for $n$ large enough, every $k$ coloring ...
6
votes
2answers
109 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
163 views

Schur's theorem and infinite version

I've got a homework exercise on Schur's theorem, which says that for any $r \in \mathbb N$ there is an $n \in \mathbb N$ such that for any $r$-colouring of $[n] := \{1, \dots, n\}$ there is a ...