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
22 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 ...
1
vote
1answer
137 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
92 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 ...
5
votes
4answers
250 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
70 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
124 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
75 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
58 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
188 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
268 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.
4
votes
3answers
287 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
89 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 ...
3
votes
1answer
188 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
53 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
238 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
77 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
138 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
48 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
71 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 + ...
2
votes
0answers
88 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
242 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 ...
4
votes
1answer
95 views

Euclidean Ramsey theory problem

Let $k\geq 1$ be given. Consider the following statement: For all (non equilateral) triangles (represented by 3 points in $\mathbb R^2$) and for all $k$-colorings of $\mathbb R^2$ there exists a ...
0
votes
3answers
334 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
92 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
20 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
359 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
141 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
68 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. ...
3
votes
1answer
182 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
178 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
48 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
118 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$.
11
votes
5answers
900 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
58 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
117 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
85 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
62 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
76 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
379 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
148 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
83 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
220 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
66 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
112 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
150 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
269 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 ...
11
votes
2answers
316 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
65 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
226 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$ ...