# Tagged Questions

Ramsey theory refers to questions of the form "how many objects are needed to guarantee that a given property of the collection holds?"

29 views

### There must be a monochromatic odd cycle in $t$-coloring of $K_{2^t+1}$

Prove: if we $t$-color the edges of the complete graph on $2^t+1$ vertices, then there must be a monochromatic odd cycle. This is supposed to be an easy exercise but I haven't made much progress. ...
40 views

336 views

### Ramsey number $R(n,n) > (n-1)^2$

I got an home work assignment, prove that: $R(n,n) > (n-1)^2$ Note that I saw on Wikipedia that for subgraph of $K_n$ with k vertices, $R(k,k) > 2^{k/2}$. I tried to work with that, but ...
22 views

### Show a function is bounded using Ramsey's Theorem

Suppose we have so,e bounded functions $g_1, \dots, g_k$, a function $f$, and constants $\epsilon, \delta$ such that whenever $f(x)-f(y) > \epsilon$ then $\max_i g_i(x) - g_i(y) > \delta$. I ...
93 views

### 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$ ...
20 views

### Ramsey Numbers and the Probabilistic Method

I am trying to prove that if there exists a real number $0 < p <1$ such that $$\binom{n}{k}p^k + \binom{n}{q}(1-p)^q < 1$$ for some $k, q \in [n],$ Then $R(k,q) > n.$ I see by the ...
26 views

### Focus of arithmetic progression applied to Van der Waerden's Theorem

So Im working through my notes which prove Van der Waerden's Theorem for the case $m=3$. The method my lecturer has chosen is to first prove the Lemma below. The Lemma is proved by induction but I can'...
19 views

### Monochromatic congruent triangles on a 10-gon

Five vertices of a regular $10$-gon are painted red and five blue. Prove that there will always be two congruent monochromatic triangles. Please tell me if my proof is acceptable. I don't know how ...
8 views

### Ramsey number for two graphs

Given R(G, H) = n, we have the minimum number such that $K_n$ will always contain G in one color OR H in the other. Is this definition correct? I ask because I'm very confused about the particular ...
35 views

### Prove that there exists a one-color $K_3$ in a $K_{17}$ which is colored with three colors [duplicate]

Assume that we have a $K_{17}$ and we color every edge of it with 3 colors ( Like Red, Blue & green ). Prove that for every coloring of $K_{17}$ with 3 colors, After coloring, We have a one-...
46 views

### Prove that every edge-coloring of $K_{17}$ with $3$ colors contains a monochromatic $K_3$. [duplicate]

Also, Prove that every edge-coloring of $K_6$ with $2$ colors contains at least two monochromatic copies of $K_3.$ I have no idea how to start these problems. What should I do?
29 views

### Colouring $K_{2s-1}$

Suppose we 2-colour $K_{2s-1}$ such that no vertex has more than one blue edge incident to it, prove that the graph contains a red $K_s$. I've never seen a Ramsey theory question like this and am ...
39 views

### Total number of gifts given at the end of a party

The following is true for n guests at a Christmas party: ...
47 views

### Graph Theory Proof that R(3,4)=9

The attatched is supposed to prove that $R(3,4)=9$ . One line say says there is no red $K_3$ in the two-colouring of $K_8$ What is it talking about?- I can see plenty of red triangles! (with corners ...
62 views

### Ramsey Number algorithm

In general is there an algorithm to obtain Ramsey Number? For example how should I approach to get $R(2K_2, 2K_2)$ or R(3, 2K_2)?
180 views

### Coloring classes of $\{1,2,3,\dots,n\}$

I'm trying to prove the following statement There is an integer $n_0$ such that for any $n\ge n_0$, in every $9$-coloring of $\{1,2,3,\dots,n\}$, one of the $9$ color classes contains $4$ integers ...
25 views

### expressability of finite and infinite ramsey theorems in Peano arithmetic

finite ramsey theorem: for all e,k,r natural numbers, there exists a least natural number m=R(e,r,k) so that for all sets M when cardinality of M is larger or equal m and all of the e- tuples of M are ...
42 views

### Ramsey theorems for the naturals and for general infinite sets

In reverse mathematics and in recursion theory, the infinite Ramsey theorems are usually stated in terms of coloring of $[\Bbb N]^n$. How do these (not) imply the Ramsey theorems for general infinite ...
54 views

### Sufficiently many points in $\mathbb{R}^d$ must contain $m$ points forming the vertices of a convex polytope?

Let us say that a set of points in $\mathbb{R}^d$ is minimal if it forms exactly the set of vertices of a convex polytope. Equivalently, no proper subset of the points has the same convex hull; no ...
69 views

### Graph or its Complement contains a triangle.

How do I prove that the graph with at least 6 vertices or its complement contains a triangle? Do I have to prove that if a graph contains a triangle, then its complement doesn't contain, and the ...
27 views

### Prove that if $n > 1$ such that $n \to (a,b)$ and $m > n$, then $m \to (a,b)$.

I've simplified the question's notation to read as follows, If $n > 1$ such that every graph $H$ on $n$ vertices has $\alpha(H) \ge a$ or $\omega(H) \ge b$ and $m > n$, then every graph $G$ ...
24 views

### Find a graph with 5 vertices such that $\omega(G) = 2$ and $\alpha(G) = 2$.

I am trying to show that the following statement is false by providing a drawn graph as a counterexample. I've been pointed in the right direction that the statement is only true for at least 6 ...
97 views

### How do I get this upper bound for Ramsey numbers: $R_k \le \left \lfloor k!e \right \rfloor + 1$?

For every integer $k \ge 2$, $$R_k \le \left \lfloor k!e \right \rfloor + 1$$ where $R_k$ denotes $R(\underbrace{{3, 3, \ldots, 3}}_{k})$.
12 views

### What is the smallest $n$-uniform transversal of $\binom{[2n+2]}{2n}$?

For a family of sets $F \subseteq 2^{[m]}$, let $T \subseteq \binom{[m]}{n}$ an $n$-uniform transversal of $F$ if and only if $\forall f \in F~\exists t \in T: t \subseteq f$. In other words, each ...
85 views

39 views

### What's the deal with Ramsey graph theory with vertex-colourings instead of edge-colourings?

As in the edge-colouring case, we can talk of a $r$-Ramsey graph $R$ for some (finite) graph $G$ wrt. vertex-colouring, i.e. such that for every $r$-colouring of the vertices of $R$ there is a copy of ...
63 views

### A combinatorial proof for a bound on diagonal Ramsey numbers

I wish to prove $R(p,p)\leq\frac{2^{2p-2}}{\sqrt{p}}$ combinatorially. I have proved this algebraically through the definition of the binomial coefficient but I would much prefer a proof from ...
34 views

### Prove that a function described as below exists

$R(n,k,l)$ is defined like this : Imagine we have a set and we want to color every subset of it having $k$ elements with $n$ colors such that at the end of coloring, there exists a subset with $l$ ...
45 views

### Approaching Ramsey theory in a unified way

Ramsey theory consists of seemingly diverse results like van der Waerden theorem and Ramsey theorem. There does not seem any apparent connection between these beyond the usual "Order within disorder" ...
11 views

### prove that $R^*(r+1,k;a_1,…,a_r,k)=R^*(r,k;a_1,…,a_r)$

Imagine we have a set with $n$ members. we want to color $k-subsets$ of this set with $r$ colors called $c_1,\ldots,c_r$ such that one of these things happen : - we have a set with $a_1$ members such ...
54 views

### an edge coloring of $k_{16}$ with no monochromatic triangle [closed]

My plan is to show that $R(3,3,3)$ is more than 16. So, i want to prove it with graph-theory. i know i should find an edge coloring of $k_{16}$ which contains no monochromatic triangles. Can anyone ...
23 views

### can we find a $k_4$ colored with 1 color in a $k_8$ which is colored with just 2 colors?

Assume that we define edge coloring in this way : An edge coloring of a graph is an assignment of "colors" to the edges of the graph. So, now imagine we have a $K_8$ which has edges colored with just ...
70 views

### Uses of Ramsey Theory in Astronomy?

In the last paragraph of a Scientific American article of July 1990 that can be found here http://www.math.ucsd.edu/~ronspubs/90_06_ramsey_theory.pdf Graham and Spencer write "Today we can easily ...
65 views

### Ramsey counter examples

I do not know of any solution or if it's an open problem: Let $R(i,i)=k$, therefore there exists a counter examples with blue and red edges for a clique of size $k-1$. Does there exist a counter-...
27 views

### Monochromatic triangle in two closed set which cover the plane

I am reading Section on Euclidean Ramsey Theory in Ronald Graham's Rudiments of Ramsey Theory. Exercise 7.3 states that Show that if $E^2$ is covered by two closed sets of colors then every 3-...
188 views

### in every coloring $1,…,n$ there are distinct integers $a,b,c,d$ such that $a+b+c=d$

Prove that for every $k$ there is a finite integer $n = n(k)$ so that for any coloring of the integers $1, 2, . . . , n$ by $k$ colors there are distinct integers $a, b, c$ and $d$ of the same color ...
88 views

### Lower bound for Ramsey numbers: $R( n + 2 , 3 )>3n$

I need to prove the following inequality: $$R( n + 2 , 3 )>3n$$ where $n>1$ and $R(s,t)$ is a Ramsey number. The most general way to prove such inequalities is to paint a graph with $3n$ ...
85 views

### Infinitely many points in plane s.t. no point is a convex combination of other points

Let $A$ be an infinite set of points in the plane, with no three points of $A$ collinear. I want to prove that $A$ contains an infinite set $B$ such that no point of $B$ is a convex combination of ...
23 views

### Ramsey number for tree and complete graph [duplicate]

I am having a lot of trouble understanding Ramsey theory. I am working on an exercise that asks for the Ramsey number $R(T,K_{1,n+1})$ where $T$ is a tree with $m$ edges and $n$ is a multiple of $m$. ...
17 views

### Independent Set of Product Graph and Ramsey Number

For two graphs $G,H$, define $G\otimes H$: it has vertex $V(G)\times V(H)$, $(v_1,v_2)(v_1',v_2')\in E(G\otimes H)$ if it satisfies all the following three requirments (i) $(v_1,v_2)\neq (v_1',v_2')$ ...
39 views

### Maximum $K_6$-free graph on $15$ vertices?

My question is, suppose we have $15$ vertices. What is the maximum number of edges we can add between these vertices, each with a fixed colored red or blue, so that there is no monochromatic triangle? ...
108 views

### Finding the exact value for $H(7)$

The graphs that I work with are all complete, each edge is colored red or blue, and each vertex is colored red or blue. $\textbf{Definition:}$ A graph is $\textit{Happy}$ if there exists a vertex ...
$S$ is a set of R(m,m;3) points in the plane in which no 3 points are collinear. I am trying to prove that $S$ contains $m$ points that form a convex $m$-gon. I have tried using similar logic to the ...
### Finite coloring of $[\omega]^{<\omega}$.
It is known that Ramsey theorem does not hold for finite colorings of $[\omega]^{<\omega}$. So I am interested in this "partial" result: First let $S_n = ]n, +\infty[$ be the set of natural ...