The ramsey-theory tag has no wiki summary.

**8**

votes

**1**answer

475 views

### monochromatic cycle-free colouring of the complete graph on R?

Hi
So there is an edge-colouring of a complete graph on R (the reals), with countably many colours that as no monochromatic triangle. To find it map R to (0,1) write the numbers in binary and if 2 ...

**20**

votes

**1**answer

1k views

### Monochromatic triangles in every two-coloring of the plane?

An old problem (possibly due to Erdős and Graham?): given a triangle $T$ and a two-coloring of the plane, does there necessary exist a monochromatic congruent copy of $T$? Here "monochromatic" means ...

**4**

votes

**1**answer

316 views

### Ramsey pairs of classes graphs

Motivation
Call a set $H$ of vertices of a graph $G$ homogeneous if it is either independent or complete.
Every perfect graph of size $n$ has a homogeneous subset of size $\sqrt n$.
Noga Alon has ...

**2**

votes

**2**answers

1k views

### Proofs of Lower Bounds for Ramsey Numbers?

As a sort of dual question to this question, I am wondering what proofs people know of lower bounds on Ramsey numbers $R(k, k)$. I know of two proofs: there is Erdos's beautiful probabilistic ...

**12**

votes

**2**answers

2k views

### Noncombinatorial proofs of Ramsey's Theorem?

I know of 2(.5) proofs of Ramsey's theorem, which states (in its simplest form) that for all $k, l\in \mathbb{N}$ there exists an integer $R(k, l)$ with the following property: for any $n>R(k, l)$, ...

**18**

votes

**2**answers

740 views

### Ramsey multiplicity

Given a positive integer $a$, the Ramsey number $R(a)$ is the least $n$ such that whenever the edges of the complete graph $K_n$ are colored using only two colors, we necessarily have a copy of $K_a$ ...

**2**

votes

**1**answer

376 views

### Suppose the independent number of a graph is bounded. How small the clique number can be?

Suppose the independent number of a graph is bounded. How small the clique number can be? linear?
It seems to be a natural problem to ask. but I could not find any reference.
Thanks.

**5**

votes

**2**answers

250 views

### Bounds on a partition theorem with ambivalent colors

I've been running into the following type of partition problem.
Given positive integers h, r, k, and a real number ε ∈ (0,1), find n such that if every (unordered) r-tuple from an n ...

**22**

votes

**5**answers

4k views

### Erdos Conjecture on arithmetic progressions

Introduction:
Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length.
Question:
I ...

**3**

votes

**2**answers

545 views

### Where can I find a catalog of known Ramsey numbers?

Is there an online catalog available of Ramsey numbers, preferably one that for unknown values documents the known upper/lower bounds?

**15**

votes

**10**answers

3k views

### Applications of infinite Ramsey's Theorem (on N)?

Finite Ramsey's theorem is a very important combinatorial tool that is often used in mathematics. The infinite version of Ramsey's theorem (Ramsey's theorem for colorings of tuples of natural numbers) ...

**12**

votes

**6**answers

15k views

### Magnitude of Graham's Number?

I recently stumbled across this number, and then (foolishly, most likely) decided to try to describe it in a blog post
http://frothygirlz.com/2010/01/14/big-numbers-part-2/
Q - Are there any ...

**8**

votes

**2**answers

926 views

### Ramsey Theory, monochromatic subgraphs

If we have the complete countably infinite bipartite graph $K_{\omega,\omega}$ and we colour the edges with just two colours. Should we expect to get a monochromatic copy of $K_{\omega,\omega}$.
...

**5**

votes

**5**answers

996 views

### Bound on cardinality of a union

Suppose I have n finite sets A1 through An contained in some fixed set S, and I am given non-negative integers N and N1 through Nn such that each Ai has cardinality N, and each k-tuple intersection ...

**5**

votes

**1**answer

319 views

### Non trivial colouring of the edges of an infinite complete graph

Can you build a probabilistic scheme for colouring each edge (independently of all other edges) of the complete graph G on the positive integers such that the probability that G contains an infinite ...

**5**

votes

**2**answers

670 views

### Infinite Ramsey theorem with infinitely many colours

Clearly, it is possible to colour the edges of an infinite complete graph so that it does not contain any infinite monochromatic complete subgraph. Now what about the following?
Let $G$ be the ...

**13**

votes

**4**answers

802 views

### Splitting pythagorean triples

Can one partition the set of positive integers into finitely many pythagorean-triple-free subsets? If so, what is the smallest number of such subsets? Taking a wild guess, I would
be least surprised ...

**8**

votes

**5**answers

973 views

### Can one make Erdős's Ramsey lower bound explicit?

Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number R(k). Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large ...