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$.
24
questions
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 ...
- 703
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 ...
- 4,902
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) ...
- 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 ...
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 ...
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 ...
- 78.6k
29
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 ...
- 393
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 ...
- 7,755
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 ...
- 4,792
16
votes
3
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)$, ...
- 22.2k
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 ...
- 2,937
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 ...
- 6,608
13
votes
2
answers
892
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 ...
- 17.4k
12
votes
2
answers
813
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 ...
- 436
12
votes
0
answers
226
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 ...
- 7,345
8
votes
1
answer
356
views
A combinatorial property of uncountable groups, II
Problem 1. Is it true that each uncountable group $G$ contains two subsets $A,B\subset G$ such that
1) for any $x,y\in G$ the intersection $xA\cap yB$ is finite and
2) for any function $\...
- 40.9k
7
votes
0
answers
217
views
A funny kind of Ramsey number
A shorter version of this question was posted on Math Stack Exchange.
Let $V$ be a nonempty set. $(V,S)$ is a graph if $S\subseteq\binom V2,$ a triple system if $S\subseteq\binom V3,$
a quadruple ...
- 11.9k
6
votes
1
answer
347
views
Ramsey type theorem
Let $\mathcal{P}(\{0,\dotsc,7\})$ denote the power set of $\{0,\dotsc,7\}$.
Is the following true?
For any function $f: \mathcal{P}(\{0,\dotsc,7\})\rightarrow\{0,1\}$ there exists $0\leq k\leq 3$ ...
- 909
4
votes
1
answer
206
views
Another funny kind of Ramsey number
Definition. $h(n_1,n_2)$ is the least number $m$ such that, if the edges of $K_m$ are colored with two colors, $1$ and $2,$ then for some color $i\in\{1,2\}$ there is a set $W\subseteq V(K_m)$ such ...
- 11.9k
4
votes
2
answers
667
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 ...
- 361
3
votes
1
answer
507
views
Is this version of van der Waerden's Theorem consistent with ZFC?
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 ...
- 17.4k
2
votes
0
answers
881
views
Happy ending problem – Why not a proof by induction?
I have been thinking for a while on the happy ending problem, looking for approaches to attack the Erdős–Szekeres conjecture: the smallest number of points for which any general position arrangement ...
- 229
2
votes
0
answers
133
views
Even cycle constrained edge coloring
Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...
- 13.7k
1
vote
0
answers
97
views
Group graphs and Ramsey theory. Sub-question 1
Question: Find/compute relations between the classical Ramsey numbers and their variations (described below) -- exact or asymptotic.
A graph is a set $\ X\ $ together with a (coloring) function
$\ c:\...
- 4,686