LEAPS-MPS: Anti-Ramsey Properties of Graphs and Other Combinatorial Objects

Graphs play a crucial role in modeling relations in real world applications, for example, in computer networks, computer graphics, electric circuit designs. This project aims to study anti-Ramsey properties of graphs. It was originally motivated by the problems posed in Ramsey theory, one of the most fundamental and thriving areas in discrete mathematics. The project for graphs naturally extends to solutions of equations, resulting in an interesting connection to combinatorial number theory. The PI will involve both undergraduate and graduate students in this project. The PI will carefully integrate education with research by providing necessary tools and easing students into research. Students will be exposed to all stages of conducting original research, from collaboration with each other to writing process, as well as presenting results at conferences. The study of anti-Ramsey properties of graphs and solutions to equations is a relatively new and unexplored research area. The project focuses on finding rainbow substructures in colored objects. In particular, the PI will study rainbow numbers, the smallest number of colors needed to guarantee a rainbow arithmetic progression in a graph, set of integers, or integers modulo n. The work will employ techniques from combinatorics, algebra, number theory, in addition to computer-aided computations. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.