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
0answers
29 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
49 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
74 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
17 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
38 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
40 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
21 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
23 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
21 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
42 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
60 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
92 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
52 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
52 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
74 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
54 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
42 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
71 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
42 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
39 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
16 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
106 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
78 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
144 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
59 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
49 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
157 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
174 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
45 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
226 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
87 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
31 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
159 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
44 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
173 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
67 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
135 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 ...
2
votes
0answers
83 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
205 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 ...