Ramsey number for tree and complete graph

105 Views Asked by At

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$.

I am not sure what exactly the Ramsey number for this means or how to begin finding it. I understand that usually problems like these involve finding lower and upper bounds.

In the linked problem, I am not understanding how the following claim is made:

Suppose you have the graph $G=(\frac{n−1}{m−1}+1)×K_{m−1}$, Then $T_m$ is not in $G$, and $K_{1,n}$ is not in $\bar{G}$. I am also looking for some help with the logic for finding the upper bound. I am trying to use the observation that you can pick the root of the tree or the single node in the bipartite graph but from there I can't see a construction for the desired objects.