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
7 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
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 ...
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 ...
3
votes
2answers
295 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
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 ...
6
votes
1answer
285 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
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
40 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
59 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
88 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
51 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
770 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
73 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
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!
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 ...
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 ...
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 ...
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
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 ...
2
votes
1answer
254 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
76 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 ...
3
votes
3answers
225 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
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 ...
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
156 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 ...
2
votes
1answer
172 views

A “geometrical” representation for Ramsey's theorem

The [infinite] Ramsey theorem states that Let $n$ and $k$ be natural numbers. Every partition $\{X_1,\ldots ,X_k\}$ of $[\omega]^n$ into $k$ pieces has an infinite homogeneous set. Equivalently, ...
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
44 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.
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
157 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, ...