Questions tagged [ramsey-theory]

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

Filter by
Sorted by
Tagged with
47 votes
8 answers
4k views

Ron L. Graham’s lesser known significant contributions

Ron L. Graham is sadly no longer with us. He was very prolific and his work spanned many areas of mathematics including graph theory, computational geometry, Ramsey theory, and quasi-randomness. His ...
38 votes
2 answers
5k 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 ...
none's user avatar
  • 381
36 votes
0 answers
1k 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 = (\alpha,...
Igor Pak's user avatar
  • 16.3k
35 votes
5 answers
4k 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 ...
Mike's user avatar
  • 703
34 votes
1 answer
2k views

Two-colouring the two-sphere

Suppose that $S^2$ is the unit sphere in $\mathbb{R}^3$. Is there a function $f \colon S^2 \to \{0,1\}$ so that, for any orthonormal basis $(u,v,z)$, exactly one of the values $f(u)$, $f(v)$, and $f(...
GaussJordan's user avatar
33 votes
1 answer
2k views

Is there a configuration of 5 points on the plane where any two can be covered by an axis aligned rectangle?

I'm trying to figure out the question in the title for a project that I'm working on. My goal is to find a configuration of five integer points on the plane, where we can overlap any pair of them ...
aradarbel10's user avatar
31 votes
1 answer
9k 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 ...
Timothy Chow's user avatar
  • 78.1k
28 votes
6 answers
12k 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 ...
Emile Okada's user avatar
27 votes
5 answers
8k 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 ...
Alex R.'s user avatar
  • 4,902
26 votes
1 answer
3k 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 ...
Matthew Kahle's user avatar
23 votes
2 answers
1k 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$ ...
Andrés E. Caicedo's user avatar
23 votes
1 answer
1k views

List Ramsey numbers?

The diagonal Ramsey number $R(n,n)$ is the least number $m$ for which the following holds: in any edge-colouring of the complete graph $K_m$ in which each edge is coloured blue or red, there is a ...
bof's user avatar
  • 11.5k
21 votes
10 answers
5k 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) ...
alexod's user avatar
  • 757
20 votes
4 answers
2k 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 ...
20 votes
1 answer
610 views

If $S_\mathbb N$ is partitioned into finitely many pieces, must one piece contain a "skew copy" of every countable group?

Suppose $G$ and $H$ are groups. $C \subseteq H$ is called a skew copy of $G$ in $H$ if $C = hK$ for some $h \in H$ and some subgroup $K$ of $H$ with $K \cong G$. Question 1: Suppose the infinite ...
Will Brian's user avatar
  • 17.4k
20 votes
1 answer
1k views

On Erdös–Kakutani like Equivalents of the Failure of Continuum Hypothesis

Among all mysterious equivalents of the Continuum Hypothesis and its negation, there is an algebraic combinatorial equivalent of $\neg \mathit{CH}$ in Erdös and Kakutani - On non-denumerable graphs (...
Morteza Azad's user avatar
19 votes
1 answer
723 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 ...
David Eppstein's user avatar
19 votes
0 answers
606 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 ...
Myshkin's user avatar
  • 17.4k
18 votes
3 answers
711 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 ...
Pietro Majer's user avatar
  • 56.5k
17 votes
2 answers
2k views

A proof of Van der Waerden's theorem using a weakened form of Szemeredi's theorem

Van der Waerden's theorem states that any colouring of the integers in a finite number of colours has monochromatic arithmetic progressions of arbitrary length. Szemerédi's Theorem is a dramatic ...
Ivan Meir's user avatar
  • 4,782
17 votes
0 answers
1k views

Almost monochromatic point sets

There are many sort of equivalent theorems about monochromatic configurations in finite colorings, such as Van der Waerden, Hales-Jewett or Gallai's theorem, the latter of which states that in a ...
domotorp's user avatar
  • 18.3k
17 votes
0 answers
830 views

Ramsey's theorem for the first uncountable ordinal

Sierpiński proved that a version of Ramsey's theorem for colourings of pairs of countable ordinals fails miserably by comparing the ordering of $\omega_1$ with the linear ordering of (a subset of) the ...
Tomasz Kania's user avatar
  • 11.3k
16 votes
2 answers
3k 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)$, ...
Daniel Litt's user avatar
  • 22.2k
16 votes
2 answers
2k 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 ...
Yemon Choi's user avatar
  • 25.5k
16 votes
4 answers
635 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 ...
László Kozma's user avatar
15 votes
6 answers
21k 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 ...
Robert's user avatar
  • 161
15 votes
5 answers
2k 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 ...
Randomblue's user avatar
  • 2,937
15 votes
1 answer
1k views

Ramsey Number R(3,3,4)

How much is known about the Ramsey number R(3,3,4)? There is a trivial upper bound of 34, but are any tighter bounds known?
Thomas's user avatar
  • 2,691
15 votes
1 answer
2k 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 ...
Thomas Bloom's user avatar
  • 6,608
13 votes
2 answers
890 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 ...
Will Brian's user avatar
  • 17.4k
13 votes
3 answers
903 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 ...
Orange's user avatar
  • 124
12 votes
3 answers
2k 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 ...
Mirco A. Mannucci's user avatar
12 votes
2 answers
810 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 ...
Jonathan Kariv's user avatar
12 votes
1 answer
398 views

Ramsey Theorem for the class ORD

Is it true that given a (definable) 2-coloring of the ORD (class of ordinals), $\chi:[ORD]^{2}\rightarrow\lbrace 0,1\rbrace$, there exists an unbounded $H\subseteq ORD$ which is homogenous, i.e., $\...
Sam Dworetzky's user avatar
12 votes
0 answers
225 views

Does $2^{\aleph_0}\rightarrow [\aleph_1]^2_3$ require that the continuum is weakly inaccessible?

A classic result of Sierpiński shows that $2^{\aleph_0}\nrightarrow [\aleph_1]^2_2$, that is, there is a coloring of pairs of real numbers using two colors such that both colors appear on any ...
Todd Eisworth's user avatar
11 votes
3 answers
1k 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. Let ...
11 votes
1 answer
297 views

Higher-dimensional Sierpiński partitions

Given a well-ordering of $\mathbb{R}$, there is a natural way to define an associated partition of pairs of real numbers into two pieces: one assigns the value $0$ to a pair $r<s$ if the well-...
Todd Eisworth's user avatar
11 votes
0 answers
480 views

Are there 100 points that are part of every half-density part of the plane?

Is there a configuration $P$ that consists of 100 points of the plane such that every $X\subset\mathbb R^2$ whose density is half contains an isometric copy of $P$? I am deliberately being vague ...
domotorp's user avatar
  • 18.3k
11 votes
0 answers
226 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 ...
domotorp's user avatar
  • 18.3k
10 votes
2 answers
2k 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}$. ...
alext87's user avatar
  • 3,167
10 votes
2 answers
573 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 famous ...
Joseph O'Rourke's user avatar
10 votes
3 answers
1k 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 $...
Roland Bacher's user avatar
10 votes
3 answers
475 views

How many colors do we need to avoid bichromatic triangles?

Ramsey theory studies whether a monochromatic subgraph (more generally, structure) appears when we color the edges of a complete graph with some colors. I wonder if the following type of question has ...
domotorp's user avatar
  • 18.3k
10 votes
2 answers
790 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 ...
Sesh's user avatar
  • 141
10 votes
1 answer
340 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 ...
user avatar
10 votes
1 answer
487 views

Looking for “Set theory for a small universe” by Ketonen

In the paper Partition theorems for systems of finite subsets of integers, Pudlák and Rödl show a Ramsey-type result. The main feature of this result is that the sizes of sets in such systems are not ...
Pedro Sánchez Terraf's user avatar
10 votes
1 answer
376 views

Two dimensional perfect sets

Consider the following family of sets $$ \begin{align*} \mathcal{F} = \{X\subseteq [0,1]\times [0,1] \mid \ &X \text{ is closed and }\\& \forall x \in \pi_0 (X) (\{y \in [0,1] \mid (x,y) \in ...
Lorenzo's user avatar
  • 2,134
10 votes
1 answer
320 views

Dense triangle-free graphs and their independent sets

Recall that a graph is triangle-free if it does not contain a copy of $K_3$. Also, for a graph $G$, $\alpha(G)$ shall denote its independence number. Lastly, we will write $o(1)$ to denote quantities ...
Zach Hunter's user avatar
  • 3,393
9 votes
4 answers
1k 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+...
idmercer's user avatar
  • 377
9 votes
3 answers
1k 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 ...
Mostafa's user avatar
  • 4,454

1
2 3 4 5