Ramsey Theory

Ramsey theory is a branch of mathematics that studies the "forced" emergence of particular kinds of structures. At a high level, I rather like the informal description of Ramsey theory given by Landman and Robertson:

Ramsey theory is the study of the preservation of properties under set partitions. In other words, given a particular set \( S \) that has a property \( P \), is it true that whenever \( S \) is paritioned into finitely many subsets, one of the subsets must also have property \( P \)?

There are lots of different problems that are Ramsey theoretic in flavor concerning a remarkable plethora of mathematical structures. One of the most fundamental though is in graph theory; here Ramsey-type problems often manifest in questions about edge colorings. For example, a standard "party problem" question asks how many people must be at a party in order to be certain that there must always exist a group of 4 people who are all mutual friends or all mutual strangers (assuming that any two people are either friends or strangers)? This question can be stated more formally in terms of colorings on graphs, asking what is the minimal \( r \) such that any \(2\)-coloring of a \( K_r \) admits a monochromatic \( K_4 \) as a subgraph? Here the value of \( r \) is one of the "diagonal" Ramsey numbers. While the answer to this question is known, in general, the Ramsey numbers are incredibly difficult to compute: for example, the value of the next diagonal Ramsey number, asking for the minimal value of \( r \) such that any \(2\)-coloring of a \( K_r \) admits a monochromatic \( K_5 \) as a subgraph is unknown (but it is known that \( 43 \leq r \leq 48 \)).

Now, the question(s) above are asking for the emergence of complete subgraphs. However, we can more generally investigate the Ramsey numbers of any particular kind of subgraph. In fact, the Ramsey numbers of many simple families of graphs (including stars, paths, and cycles) have been determined exactly: see Radzisowski for a survey of known results of Ramsey numbers. One of the questions I am most interested in is the study of the Ramsey numbers of a family of graphs known as double stars. A double star (denoted \( S(n,m) \)) is a particular kind of tree on \( n + m + 2 \) nodes, formed by taking two disjoint stars (of size \( n \) and \( m \) respectively) and adding an edge joining their centers; the Ramsey numbers of the double stars were solved in most cases by Grossman et al. In particular, they show that for all \( n \leq \sqrt{2} m \) and \( n \geq 3m \), the Ramsey numbers of the double stars satisfy \{ r(S(n,m)) = \left[ \begin{array}{lr} \text{max}(n + 2m + 1, 2n + 2), & \text{for } n \text{ odd}, m \leq 2\\ \text{max}(n + 2m + 2, 2n + 2), & \text{otherwise} \end{array} \right]. \} It was conjectured in Grossman et al. that the above result holds in the range \( \sqrt{2}m < n < 3m \) as well. Surprisingly however, Norin et al. showed that the conjecture is false, as well as providing asymptotic results for the ramsey numbers of \( S(n,m) \) in the gap. The exact value of \( r(S(n,m)) \) in the range \( \sqrt{2}m < n < 3m \), however, remains an open question that I am very interested in resolving, and for which I possess some partial results.