Branch of combinatorics with the philosophy that 'total disorder is impossible'. For example, Ramsey's theorem asserts that for each $n$, every sufficiently large graph either contains a clique of size $n$ or a stable set of size $n$.

learn more… | top users | synonyms

31
votes
2answers
4k views

Why is this new result such a big deal?

This popular article reports a recent result in reverse mathematics, showing that a certain theorem in Ramsey theory is provable from RCA$_0$, the base theory in SOSOA. Then there are a bunch of ...
30
votes
4answers
2k views

Cliques, Paley graphs and quadratic residues

A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs. If p=1 mod 4 is a prime, we can define the ...
29
votes
0answers
730 views

3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$. Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = (\...
22
votes
5answers
5k 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 ...
21
votes
1answer
4k views

Reconstructing the argument that yields Graham's number

Graham's number achieved a kind of cult status, thanks to Martin Gardner, as the largest finite number appearing in a mathematical proof. (It may no longer hold that record, but that is not my concern ...
20
votes
1answer
2k 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 ...
18
votes
2answers
808 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$ ...
17
votes
4answers
1k 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 ...
17
votes
3answers
585 views

Ergodic limits along subsets of $\mathbb{N}.$

Let say that an infinite subsets $A$ of $\mathbb{N}$ is "nice w.r.to ergodic limits", if it can replace $\mathbb{N}$ in the individual ergodic theorem, that is, if it is such that the following ...
16
votes
10answers
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) ...
16
votes
4answers
482 views

Sets of points containing permutations - a Ramsey-type question

The following question arised as a side-question in a geometric problem. It has a "feel" similar to problems in Ramsey-theory, but I have not found any mention of it (also I'm not very familiar with ...
16
votes
0answers
289 views

Simpler proofs of certain Ramsey numbers

The reason for the gorgeous simplicity of the classic proofs of $R(3,3)$, $R(4,4)$, $R(3,4)$ and $R(3,5)$ is that essentially all you need is the trivial bound and a picture. But for bigger Ramsey ...
14
votes
1answer
328 views

Convergence rate of Fagin's 0-1 law for first-order properties of random graphs

Fagin's 0-1 law for first-order properties of random graphs states that, for every first-order sentence in the logic of graphs, the probability that a uniformly random $n$-vertex graph models the ...
13
votes
3answers
757 views

Differences of near diagonal Ramsey numbers.

I am a graduate student trying to get involved in Ramsey theory. My question comes from: Erdős on graphs: his legacy of unsolved problems By Fan R. K. Chung, Paul Erdős, Ronald L. Graham p.14 of ...
12
votes
6answers
18k 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 ...
12
votes
2answers
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)$, ...
12
votes
5answers
1k 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 ...
11
votes
2answers
751 views

Where is the Erdős–Rado theorem stated in Erdős and Rado's Bull AMS paper?

This may be inappropriate for MO, but here goes: if I have understood the statement of the Erdős–Rado theorem correctly, then it contains as a special case the following result: if $\mu$ is ...
11
votes
2answers
639 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 ...
10
votes
6answers
1k views

Algorithms for calculating R(5,5) and R(6,6)

Calculating the Ramsey numbers R(5,5) and R(6,6) is a notoriously difficult problem. Indeed Erdős once said: Suppose aliens invade the earth and threaten to obliterate it in a year's time unless ...
10
votes
2answers
531 views

Is every knot unavoidable in the embeddings of some graph?

Is it the case that, for any given knot $K$, there exists some graph $G$ whose every embedding into $\mathbb{R}^3$ (or into $\mathbb{S}^3$) contains a cycle that realizes $K$? I know the ...
10
votes
2answers
632 views

Does van der Waerden's Theorem hold for $\omega_1$?

One way to phrase van der Waerden's Theorem is: For every finite coloring of $\mathbb N$ and every finite $F \subseteq \mathbb N$, there exist $a,b \in \mathbb N$ such that $a + b \cdot F$ is ...
10
votes
3answers
824 views

Density Ramsey theorems with explicit asymptotics

I wonder what interesting and non-trivial examples of density Ramsey theorems with explicit asymptotics are there? I'm aware of two examples: Szemerédi's theorem and density Hales-Jewett theorem. ...
10
votes
1answer
536 views

Could there be an exact formula for the Ramsey numbers?

Let $R(k)$ denote the diagonal Ramsey number, i.e. the minimal $n$ such that every red-blue colouring of the edges of $K_n$ produces at least one monochromatic $K_k$. Is it possible that there ...
9
votes
3answers
1k views

A General Framework for Ramsey Theory ?

There are few results in modern mathematics that I find so deep and full of philosophical implications as Ramsey's theorem. I am aware (at some basic level) that it has generated a plethora of ...
9
votes
2answers
377 views

From very many sets of fixed measure in a probability space, can we select many that have a positive intersection?

I assume the following Lemma is either well known or, more probably, a Corollary of a much stronger well known Theorem, and I would be grateful for a reference: For all $\delta\in (0,1)$ and all $\...
8
votes
4answers
941 views

Is this Ramsey-type problem an open problem?

A blog claims that the following Ramsey-type (or van der Waerden type) problem is open: If the natural numbers are colored with finitely many colors, must there exist x and y (not both 2) such that x+...
8
votes
2answers
1k 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}$. ...
8
votes
3answers
897 views

A stronger version of Van der Waerden's theorem?

Let $W$ be an infinite word over a finite alphabet $\{1,\dots,n\}$ and $k$ a positive integer. An easy application of Van der Waerden's theorem implies the existence of $k$ disjoint and consecutive ...
8
votes
2answers
683 views

Asymptotics for Ramsey Theory

Ramsey Theory says that every sufficently large (but finite) complete graph having $d-$coloured edges contains a monochromatic complete subgraph with $k$ vertices. One could ask for asymptotics: Let $...
7
votes
3answers
327 views

Extracting countable chains from linear orders

There is a well-known fact in infinite combinatorics asserting that for each infinite linear order $P$ there is a countable subset $R\subseteq P$ of order type either $\omega$ or $\omega^{*}$ (by $\...
7
votes
2answers
507 views

Deriving Konig's Lemma directly from Infinite Ramsey's Theorem for triples

Let KL denote König's Lemma (for trees over $\mathbb{N}$), and RT(3) denote the Infinite Ramsey Theorem for triples over $\mathbb{N}$ (notation as in Simpson's book Subsystems of second order ...
7
votes
2answers
523 views

Combining van der Waerden's theorem with Ramsey's theorem

Consider positive integers $c$, $k$, and $s$. Does there exist some $N = N(c,k,s)$ such that the following holds? Take any $c$-coloring of the $k$-tuples of integers in $[1,N]$. Then there is an ...
7
votes
1answer
252 views

Sparse ramsey theory

It is known that for any graph H and all $k∈N$, there exists a graph $G$ such that any $k$-coloring of the edges of $G$ yields a monochromatic copy of H and ω(G)=ω(H) (the two graphs have the same ...
6
votes
2answers
129 views

Reference request: monochromatic paths in edge-colored complete graphs

Given $k,c \in \mathbb{N}$, let $P(k,c)$ be the minimum $n$ such that no matter how we color the edges of the complete graph $K_n$ with $c$ colors, there is always a monochromatic path of length $k$. ...
6
votes
1answer
282 views

3x3 submatrix with only $0$ or $1$ entries

I decided to cross-post the question here from math.stackexchange.com because I got no answer from there. It is a quick question on bipartite Ramsey numbers (I'm not an expert on the subject, so ...
6
votes
0answers
193 views

The Hales-Jewett Theorem for an infinite alphabet

Recall the Hales-Jewett Theorem: HJT: Given a finite alphabet $A$ and some $r \in \mathbb{N}$, there is some $H \in \mathbb{N}$ such that whenever $A^H$, the set of all length-$H$ words from $A$, ...
6
votes
0answers
105 views

Is there a Ramsey theory for Kneser graphs?

Ramsey theory for graphs usually studies colorings of the edges of complete graphs. I'm interested whether there are any results about edge-colorings of Kneser graphs. More specifically, I'm most ...
6
votes
0answers
165 views

A generalization of SOCA

Roughly speaking, SOCA (Semi Open Coloring Axiom) says that for an open coloring of the unordered pairs over an uncountable separable metric space you can always find an uncountable homogeneous subset ...
6
votes
0answers
86 views

Why have most maximal cliques of Paley graphs odd size?

I ask this question mainly by curiosity. See here for definitions and a plot of the clique numbers of the Paley graphs for the primes $p\equiv 1 \pmod 4$ up to $10000$. Is there an ...
5
votes
5answers
1k 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
2answers
872 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?
5
votes
2answers
766 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 ...
5
votes
2answers
533 views

The Problem about 2-coloring finite plane

Suppose we color a $X \times X$ finite plane by red and blue arbitrarily. How large does X need to be to guarantee a monochromatic combinatorial square $k \times k$ 1 0 1 0 1 1 1 1 1 1 1 1 1 ...
5
votes
2answers
614 views

Partition calculus question

For $m,n,k < \omega$, consider the equation $X \to (\omega \times k)^{m}_{n}$ What is the smallest $X$ known to satisfy it? Baumgartner-Hajnal theorem gives a satisfactory answer for $m=2$, but ...
5
votes
1answer
358 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
2answers
255 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 ...
5
votes
1answer
402 views

Are semigroups with finite-to-one right multiplication “moving”?

A semigroup $S$ is moving if $S$ is infinite, and for all finite $F\subseteq S$ and infinite $A\subseteq S$, there are $a_{1},\dots,a_{k}\in A$ such that, for all but finitely many $s\in S$, $$ \{a_{...
5
votes
1answer
498 views

small Ramsey number and Brooks' Theorem

I'm studying about Graph Ramsey Theory now. Starting this study, I'm reading Chvatal and Harary's series of papers. In the second paper (V.Chvatal, F.Harary, Generalized ramsey theory for graphs,Ⅲ. ...
5
votes
1answer
806 views

Graham-Rothschild via Hales-Jewett

I am currently reading the recent preprint of Dodos, Kanellopoulos, Tyros, where the ambitiously short proof of Density Hales Jewett theorem is provided. The important ingredient is Graham-Rothschild ...