Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with ramsey-theory
Search options not deleted
user 2233
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$.
12
votes
Accepted
Is every knot unavoidable in the embeddings of some graph?
Yes. See this paper of Negami. The main result is that for any fixed knot (or link) of type $k$, there is a constant $R(k)$ such that every straight line embedding of $K_{R(k)}$ in $\mathbb{R}^3$ con …
- 32.1k
8
votes
Reference request: monochromatic paths in edge-colored complete graphs
For $c=2$, it is a theorem of Gerencsér and Gyárfás that $P(k,2)=\lfloor (3k-2)/2 \rfloor$.
For $c=3$, Gyárfás, Ruszinkó, Sárközy and Szemerédi proved that for sufficiently large $k$,
$P(k,3)=2k-1 …
- 32.1k
6
votes
Is there a graph that is Ramsey for $P_{2n}$ but is $C_{2n+1}-$free
Taking $F=K_{4n, 4n}$ does the trick. To see this, suppose we have coloured each edge of $K_{4n,4n}$ red or blue. Let $R$ and $B$ be the red and blue subgraphs of $K_{4n,4n}$. We may assume that $R …
- 32.1k
5
votes
Accepted
Small Ramsey numbers and Brooks' Theorem
It seems as if the Chvatal, Harary proof has a logical gap, and your proof seems to be missing some details.
Here is a proof that is based on Brook's Theorem. We plagiarize you and start by noting …
- 32.1k
4
votes
Accepted
Is there an uncountable extension of the Ramsey set $[\omega]^2$?
Yes. Just take $\mathcal{A}$ to be $[\omega]^2$ together with the powerset of the even integers.
- 32.1k
2
votes
Ramsey-Kuratowski numbers
Here are some bounds that I can extract from the dynamic survey Small Ramsey Numbers by Stanisław Radziszowski. Recall that for two graphs $G$ and $H$, $R(G,H)$ is the smallest integer $n$ such that e …
- 32.1k
1
vote
Sets of points containing permutations - a Ramsey-type question
Regarding the weak version, I can prove that there exists an $f$ such that for every two colouring of the $f(n) \times f(n)$ grid, every permutation of $[n]$ is contained in either $B$ or $W$. The pro …
- 32.1k