The ramsey-theory tag has no wiki summary.
12
votes
1answer
159 views
Monochromatic squares in a colored plane
Color every point in the real plane using the colors blue,yellow only. It can be shown that there exists a rectangle that has all vertices with the same color. Is it possible to show that there exists ...
10
votes
1answer
84 views
Coloring of positive integers
Suppose $f:\mathbb{Z}^+\longrightarrow X$ is a function, with $X$ a finite set. Is it true that there are $a,b\in\mathbb{Z}^+$ such that $f(a)=f(b)=f(a+b)$.
9
votes
5answers
401 views
Why König's lemma isn't “obvious”?
I keep facing König's lemma "Every finitely branching infinite tree over $\mathbb{N}$ has infinite branch". Why it is not taken "obvious" but needs a careful proof?
It seems somewhat obvious, but I ...
7
votes
1answer
204 views
Closest pair of vectors in $\{0,1\}^n$
Suppose we are given $k$ points in $\{0,1\}^n$ (using Hamming distance as metric).
Consider the two points that have the smallest distance between
them.
Does there exist any results bounding this ...
7
votes
0answers
159 views
Graham's Number : Why so big?
Can someone give me an idea of how R.Graham reached Graham's Number as an upper bound on the solution of the related problem ? Thanks !
6
votes
3answers
166 views
Does a red/blue coloring of the infinite subsets of $\mathbb{N}$ necessarily give an infinite monochromatic $M\subset \mathbb{N}$?
The infinite Ramsey theorem states that for any $n$, if all the subsets of $\mathbb{N}$ of size $n$ are colored red/blue, then there is an infinite $M$ all of whose subsets of size $n$ are ...
6
votes
2answers
113 views
How many 2-edge-colourings of $K_n$ are there?
I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially ...
6
votes
1answer
263 views
Showing that $K_7$ contains at least 4 monochromatic triangles
A problem in my book is:
Let the edges of $K_7$ be colored with the colors red and blue. Show that there are at least four subgraphs $K_3$ with all three edges the same color (monochromatic ...
6
votes
1answer
60 views
Two subsets and their union have same color
Color all nonempty subsets of $[n] = \{1,2,\ldots,n\}$ with colors $1,2,\ldots,r$.
Show that, for all large enough $n$, there exist two disjoint nonempty subsets $A,B \subseteq [n]$ such that ...
6
votes
1answer
154 views
Any partition of $\{1,2,\ldots,9\}$ must contain a $3$-Term Arithmetic Progression
Prove that for any way of dividing the set $X=\{1,2,3,\dots,9\}$ into $2$ sets, there always exist at least one arithmetic progression of length $3$ in one of the two sets.
6
votes
2answers
257 views
Proof of the van der Waerden theorem
The van der Waerden theorem states that given any natural numbers $k$ and $r$, there exists a natural number $W=W(k,r)$ such that if the set $\{1,2\cdots W\}$ is divided into $r$ classes (also called ...
6
votes
1answer
190 views
What is the proof of the “thin set theorem”? A result in infinite Ramsey theory.
OK so here's a precise question:
Is it true that for every integer $k\geq1$ and every $f:\mathbb{Z}^k\to\mathbb{Z}$, there is some infinite subset $A\subseteq\mathbb{Z}$ such that $f(A^k)$ is not all ...
6
votes
2answers
195 views
Prove that $r(k,k) + k \leq r(k + 1, k + 1) $
Prove that
$r(k,k) + k \leq r(k + 1, k + 1)$,
where $r(k,l)$ is the minimum number of vertexes in a Graph, where we have a clique with $k$ vertexes or a stable set with $l$ vertexes.
There are ...
6
votes
0answers
84 views
van der Waerden's original proof
I am looking for a book/site which has the english translation of the proof of van der Waerden's theorem as presented by van der Waerden himself. In other words is the translation of the paper:
...
5
votes
1answer
191 views
Known bounds and values for Ramsey Numbers
Is there a good online reference that lists known bounds on Ramsey numbers (and is relatively up to date)? The wikipedia page only has numbers for $R_2(n,m)$.
I am specifically interested in known ...
5
votes
1answer
107 views
Ramsey theory, finite colourings of $\mathbb{N}$ and infinite monochromatic sets
I am trying to show that the following statement is false: whenever $\mathbb{N}$ is finitely coloured by $c: \mathbb{N} \to \{1,\ldots,k\}$ (in the sense of Ramsey theory), there exists an infinite ...
5
votes
1answer
162 views
What's the difference between Ramsey theory and Extremal graph theory?
Wikipedia teaches us that problems in Ramsey theory typically ask a question of the form: "how many elements of some structure must there be to guarantee that a particular property will hold?"
It ...
5
votes
1answer
344 views
Prove Ramsey Number R(3,5)=14
I'm having problem proving the ramsey number of R(3,5) = 14. Below is my proof.
Proof. Let $v_0$ be a vertex from a $k_{14}$ vertices. The vertices incident to $v_0$ are $v_1, v_2, \cdots , v_{13}$ ...
5
votes
1answer
317 views
Understanding various definitions of TREE($n$) in Friedman's finite form of Kruskal's tree theorem.
I was reading the Wikipedia article on Friedman's finite form of Kruskal's tree theorem, and am interested in the large numbers TREE(n). I would like to verify TREE(2)=3 myself, but find conflicting ...
5
votes
1answer
190 views
An upper bound for a graph Ramsey number
I am trying to prove the following result, given as an exercise in my book:
$r(K_m+\bar{K_n},K_p+\bar{K_q})\le\binom{m+p-1}{m}n+\binom{m+p-1}{p}q$.
Here $r(G,H)$ denotes the Ramsey number for the ...
4
votes
2answers
108 views
Guaranteeing an integer lattice point centroid
My question is this:
Writing $n(4)$ to be the minimum number of integer lattice points in the plane so that some four of them must determine an integer lattice point centroid, show that $n(4)=13$.
I ...
4
votes
1answer
103 views
A problem in prime number theory
I was wondering if anybody here might provide me with a hint for this rather innocuous-looking problem:
If $X:= \{pq: p, q \mbox{ are prime numbers and } p\neq q\}.$ In addition, let us suppose that ...
4
votes
2answers
257 views
how to construct 17-vertexed graph for Ramsey number R(3,6)=18
Ramsey number R(3,6)=18. How to construct a graph of 17 nodes which does not contain neither a clique of order 3 or an independent set of order 6. could you show me the tactics or the adjacency ...
4
votes
3answers
125 views
Erdős Probabilistic method
My question is based on the Erdos probabilistic method. I am trying to read from the paper here. The proof of Theorem 1 contains the statement
Since a block sequence is monochromatic with ...
4
votes
1answer
326 views
Ramsey number for books
Given a triangular book $B_n$ I am trying to prove that $r(B_n,B_n)\le 4n+2$ where $r(B_n,B_n)$ is defined as the least positive number such that any graph $G$ on $r(B_n,B_n)$ vertices either has a ...
4
votes
1answer
108 views
Edge coloring a graph to find a monochromatic $K_{2,n}$
I am trying to prove or disprove the following statement: Let $n>1$ be a positive integer. Then there exists a graph $G$ of size 4n-1 such that if the edges of $G$ are colored red or blue, no ...
4
votes
1answer
58 views
Arithmetic progression in a subset of $\mathbb N$
What non-trivial sufficient and/or necessary conditions are there for existence an arithmetic progression (finite or infinite length) in an infinite subset of $\mathbb N$.
4
votes
1answer
115 views
Graph theory dinner party problem
In a party of 6 people is it true that there exists four people either all do or all do not knowing each Other?
I know it's false, and have the solution but not quite sure where to begin with the ...
4
votes
1answer
67 views
Optimal sets for plane coloring problem
There is a reasonably well-known problem:
Given a plane with each point colored one of k colors, show there is a rectangle whose vertices are all of the same color, whose axes are parallel to the ...
4
votes
0answers
51 views
Arbitrary ratio sequences on a partition of $\mathbb{R}$ (Partition regularity of fixed ratio sequences)
Background:
This question arose purely recreationally and doesn't really fit into any context that I know of.
Let $A \sqcup B = \mathbb{R}$ be a partition of the ...
4
votes
1answer
55 views
Ramsey number for paths
Let $n = R(P_{r+1}, c)$ be the smallest integer such that if $K_n$ is $c$-edge-coloured, then it contains a monochromatic subgraph isomorphic to $P_{r+1}$, the path of length $r$. I need to show that ...
3
votes
4answers
165 views
Proof of Ramsey Theorem with explicit use of AC
What are minimal axiomatic requirements to prove Ramsey Theorem?
This one:
Let $X$ be some countably infinite set and colour the elements of $X^{(n)}$ (the subsets of $X$ of size $n$) in $c$ ...
3
votes
2answers
68 views
Counterexample for $R(4,4) \neq 8$
I try to find a counterexample for $R(4,4)\neq 8$. (R is the Ramsey-number).
I drew a graph with 8 vedges and I coloured all edges $(v_i,v_j)$ with $i-j =\pm 2,4,6$ in the same colour (for example ...
3
votes
1answer
71 views
Any forest on 5 or more vertices contains an independent set of size 3.
I am looking for a short proof of this fact. This is clearly true by drawing these trees, but I am having trouble putting it into writing. Somehow I need to select 3 of the 5 vertices and show that ...
3
votes
1answer
88 views
Amalgamation of graphs
I am trying to understand the definition of amalgamation of a $n+1$-partite graph as explained here(first few lines of page 4). We have a $n+1$-partite graph $G$ with partite sets $V_0,V_1,\cdots,V_n$ ...
3
votes
2answers
109 views
Affine Van der Waerden's theorem
I have the following statement which is claimed to be a version of Van der Waerden's theorem:
For any finite partition of $\mathbb{N}$, one of the cells contains
affine images of every finite ...
3
votes
1answer
112 views
Van Der Waerden without topological dynamics?
Applying topological dynamics to prove Van Der Waerden's theorem on the existence of monochromatic arithematic progression has now become a somewhat classical example of the power of topological ...
3
votes
1answer
220 views
How to prove this relation between Ramsey Numbers: $R(s, t) ≤ R(s, t-1) + R(s-1, t)$ for $s,t>2$
I am trying to prove that
$$R(s, t) ≤ R(s, t-1) + R(s-1, t) $$
for $s,t>2$, where $R(s,t)$ is the Ramsey number of $(s,t)$, and I'd be really grateful for a hint that gets me started.
3
votes
1answer
98 views
Permutation of 1…9 with no ascending or descending subsequence of length 4
Arrange the numbers $1,2,...,9$ in such an order that no four of them appear (adjacently or otherwise) in ascending or descending order.
Show that there is no arrangement of the numbers $1,2,...,10$ ...
3
votes
1answer
89 views
Number of gifts given at the end of a party
So I'm working on a problem that has to do with Ramsey Theory. We have $n$ guests at a christmas party. We know two things about them. In any group of three there are two people who do not know each ...
3
votes
1answer
139 views
Gallai's theorem, colourings and equivalence relations
I'm revising a few past papers on Ramsey theory and I've come across a question which feels like it should be easy if it weren't so confusingly set up - I was hoping someone here could help me make ...
3
votes
1answer
95 views
Extended form of infinite Ramsey's Theorem
I'm working on some Combinatorics, and in the past have happily used the infinite Ramsey Theorem (as detailed on http://en.wikipedia.org/wiki/Ramsey%27s_theorem), which says that for something like ...
2
votes
3answers
196 views
Good way to learn Ramsey Theory
What are some good books on Ramsey theory? I have Van Lints book on Combinatorics: is this enough preparation to start reading about Ramsey theory? I want a book that includes important results and ...
2
votes
1answer
135 views
Coloring Vertices of a 50-gon
This is a problem that I have spent a good 2 hours on but can seem to come up with any rigorous solution. If someone could provide one that would be great!
If we color 21 vertices of a 50-gon, how do ...
2
votes
1answer
775 views
Show that among 20 people there are either four mutual friends or four mutual enemies
Use the fact that among a group of 10 people, where any two people are either friends or enemies, there are either three mutual friends or four mutual enemies, and there are either three mutual ...
2
votes
1answer
38 views
The Ramsey number $r(t,t,q)$ with $q\geq t$
Let q and t be positive integers with $q\geq t$. Determine the Ramsey number $r_t(t,t,q)$.
This is from the book Introductory Combinatorics by Brualdi, and in the back it says the answer is q without ...
2
votes
1answer
127 views
Ramsey Number Inequality
I want to prove that:
$$R(\underbrace{3,3,...,3,3}_{k+1}) \le (k+1)(R(\underbrace{3,3,...3}_k)-1)+2$$
where R is a Ramsey number. In the LHS, there are $k+1$ $3$'s, and in the RHS, there are $k$ ...
2
votes
2answers
73 views
What is a Ramsey Graph?
What is a ramsey graph and What is its relation to RamseyTheorem?
In Ramsey Theorem:
for a pairs of parameters (r,b) there exists an n such that for every (edge-)coloring of the complete graph on n ...
2
votes
1answer
94 views
Ramsey Number proof
I am trying to prove:
$R(3,3,3,3)\leq 4(R(3,3,3)-1) + 2$
I am confused as to how one can go from a $4$ color problem to a $3$ color problem by multiplying and adding.
edit: $R$ is the Ramsey ...
2
votes
1answer
74 views
2012-gon- subsets of vertices.
Can we prove or disprove this?
For a sufficiently large $n$, every set of at least $ n$ points in the plane with no three collinear has a subset that form the vertices of a convex $2012$-gon.
Gerry ...
