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
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 ...
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 ...
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? ...
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?
2
votes
2answers
79 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
20 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 ...
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 ...
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
25 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
44 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
63 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
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 ...
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
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 ...
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 ...
0
votes
1answer
80 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
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 ...
1
vote
3answers
29 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
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 ...
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!
5
votes
2answers
95 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
113 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
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 ...
4
votes
4answers
154 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
60 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 ...
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
73 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
51 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 ...
0
votes
1answer
158 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 ...
0
votes
1answer
184 views

Consider all colorings of the edges of K6 such that every edge is either colored red or blue…

Consider all colorings of the edges of K6 such that every edge is either colored red or blue. Prove or disprove: there always exist at least two monochromatic triangles in any 2-coloring of the edges ...
1
vote
1answer
46 views

Graph Ramsey Theory for Multiple Copies of Graphs

I had the following question from Graph Ramsey theory. Show that if $m \geq 2$, then $$ R((m+1)K _{3},K _{3})\geq R(mK _{3},K _{3}) + 3. $$ Thanks.
3
votes
3answers
235 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
2answers
88 views

Crowding the boundary of non-constructivity without crossing it?

Can any sense be made out of my vague feeling that some proofs in Ramsey theory are as close as you can get to non-constructive proofs without crossing the line? Is there any way to make this ...
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 ...
3
votes
2answers
160 views

Given an infinite poset, show that it contains either a infinite chain or an infinite totally unordered set.

Been thinking about this one for awhile and I'm still stuck... Thought about proving it by arriving at a contradiction but I haven't reached anything noteworthy. If you do a proof by contradiction, ...
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 ...
2
votes
1answer
175 views

Six people at a party and its graph theory representation

I'm confused by this classic graph theory problem: Suppose there are six people at a party. Prove that it is always possible to find either three people who all know each other, or three people none ...
1
vote
1answer
70 views

$K_6$ contains at least two monochromatic $K_3$ graphs.

Let $K_n$ be a complete $n$ graph with a color set $c$ with $c=\{\text{Red}, \text{Blue}\}$. Every edge of the complete $n$ graph is colored either $\text{Red}$ or $\text{Blue}$. Since $R(3, 3)=6$, ...
7
votes
2answers
136 views

Every 33-length subsequence of $1,2,\dotsc,122$ contains a three term arithmetic progression

Is it possible to prove that every 33-length subsequence of the sequence $1,2,3,\dotsc,122$ contains a three term arithmetic progression? Maybe I should post it on mathoverflow
1
vote
1answer
47 views

Ramsey Theory//Question of Notation

I RESOLVED THIS QUESTION FOR MYSELF, THANKS FOR VIEWING, SORRY We have this notation: $$ \mathcal A \to \mathcal B_k^{n} $$ Which means: \begin{align*} &(\forall A \in \mathcal A)(\forall ...
2
votes
1answer
68 views

A problem relying on van der Waerden's theorem, and the existence of sums divisible by a given number $n$

Say we are given a sequence of integers $\{a_i\}_{i \in \mathbb{N}}$, as well as a pair of integers $n, m$. How can we show that there always exist positive integers $s, r$ such that the sums $a_s + ...
0
votes
0answers
29 views

Practical use of Ramsey numbers [duplicate]

I am fascinated by the Ramsey number, but I was wondering, what are practical uses of the Ramsey number? Except for the party problem, I can not come up with something where it is useful for. Do you ...
0
votes
0answers
66 views

How prove this will be a length of $3$ arithmetic progression. [duplicate]

This problem is my frend give me: Given $122$ consecutive integers, show that randomly selected $33$ integer, of which there will be a length of $3$ arithmetic progression. hint: length of ...