The ramsey-theory tag has no wiki summary.

**9**

votes

**2**answers

1k 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

721 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

248 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 ...

**21**

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

505 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

894 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

967 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

314 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

642 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 ...

**12**

votes

**4**answers

755 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

946 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 ...