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$.
213
questions
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 ...
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,...
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 ...
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(...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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) ...
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 ...
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$, ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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., $\...
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 ...
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-...
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 ...
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 ...
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}$.
...
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 ...
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 $...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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+...
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 ...