Articles of ramsey theory

Ramsey Number R(4,4)

In trying to deduce the lower bound of the ramsey number R(4,4) I am following my book’s hint and considering the graph with vertex set $\mathbb{Z}_{17}$ in which $\{i,j\}$ is colored red if and only if $i-j\equiv\pm2^i,i=0,1,2,3$; the set of non-zero quadratic (mod 17) and blue otherwise. This graph shows that $R(4,4)\ge 18$. That’s all […]

A sequence of $n^2$ real numbers which contains no monotonic subsequence of more than $n$ terms

I’m following a Combinatorics course at the moment, and have recent proved the Erdős–Szekeres Theorem (or, at least, some variation of): A sequence of length $n^2 + 1$ either contains an increasing subsequence of length $n+1$, or a decreasing one of length $n+1$. I have been set an exercise to prove the following: For each […]

Coloring a Complete Graph in Three Colors, Proving that there is a Complete Subgraph

Color the edges of a complete graph on $n$ vertices $K_n$ in three colors (red,blue,yellow) such that at most $\dfrac{n^2}{k}$ are colored red ($k$ is some natural number). Prove that $K_n$ contains either blue $K_p$ or yellow $K_p$ (complete subgraph on p vertices where all of its edges are colored blue or all are colored […]

Do Ramsey idempotent ultrafilters exist?

I was studying idempotent ultrafilters when I saw that no principal ultrafilter could ever be idempotent, because $\left\langle n \right\rangle \oplus \left\langle n \right\rangle = \left\langle 2n \right\rangle$. A Ramsey ultrafilter is, by definition, never principal, so the question that arose to me was: do Ramsey idempotent ultrafilters exist? First some explanation: One of the […]

What is Ramsey Theory ? what is its own importance in maths?

3 days ago , i had a discussion with a close friend who studies physics – still a student – . and i was telling her about the biggest known numbers in maths , so i told her about numbers such googol and googolplex, then about Graham number and she asked me , what is […]

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 in red). But then I’ll find a $K_4$ with $(v_1,v_3,v_5,v_7)$, which is definitely not a counterexample. Perhaps someone can […]

Lower bound for monochromatic triangles in $K_n$

Say $K_n$ is a complete graph of $n$ nodes, and every edge is either blue or red. I’m trying to find $T_n$, which is the lower bound for the number of monochromatic triangles in $K_n$ (monochromatic meaning triangles whose 3 edges are of the same color). I’m trying this approaches: A. Let $v_i$ a vertex […]

At least one monochromatic triangle from $p_n=\lfloor{en!}\rfloor+1$ points

In space there are given $p_n=\lfloor{en!}\rfloor+1$ points. Each pair of points are connected by a line, and each line is coloured by one of the $n$ colours. Prove that there is at least one triangle of the same coloured sides. I am not getting how to counter the $e$ here. Please help. I however made […]

Partitioning Integers into Equal Sets to Guarantee Arithmetic Progression

I’ve run into the following problem which I am sure is true but I cannot prove it: If we color the integers in the set $S = \{1, 2, \ldots, 3n \}$ with $3$ colors such that each color is used $n$ times, there always exist integers $a,b,c \in S$ with distinct colors such that […]

An example showing that van der Waerden's theorem is not true for infinite arithmetic progressions

One of the possible formulations of Van der Waerden’s theorem is the following: If $\mathbb N=A_1\cup \dots\cup A_k$ is a partition of the set $\mathbb N$, then one of the sets $A_1,\dots,A_k$ contains finite arithmetic progressions of arbitrary length. In the other words, if we color the set of all positive integers by finitely many […]