LEAPS MPS: The Erdos-Ko-Rado Property of Well-Covered Graphs

California State University-Stanislaus, Turlock CA

Investigators

Abstract

Many types of relations and processes, including physical and social systems, can be modeled using a graph. Graph models of such systems tend to be very large, requiring mathematical techniques that can extract global information from the graph at the smaller, local level. Extremal graph theory can be thought of as the study of how global properties of a graph influence its local structure. The aim of this project is to investigate questions in extremal graph theory, particularly those that relate to a well-known extremal set theory result called the Erdos-Ko-Rado theorem. Undergraduate student researchers at the PI’s Hispanic-serving institution will work in pairs to take on parts of this project. These students will have the opportunity to learn how to leverage their individual strengths while conducting cutting-edge research. Additionally, a colloquium series will be established within this project to connect students and faculty in the PI’s department to high-impact role models in the mathematical sciences. The Erdos-Ko-Rado (EKR) theorem is a pivotal result in extremal set theory that gives an upper bound on the number of sets of a fixed size that are pairwise intersecting. Of particular interest is the straightforward construction of an intersecting family that attains this bound by collecting all sets of the specified size that contain some fixed element. In 2005, Holroyd, Spencer, and Talbot formulated an EKR property for graphs related to intersecting families of independent sets. This property has a corresponding construction, called an r-star, that takes all independent sets of size r containing a fixed vertex of the graph. A graph is called r-EKR if the maximum size of an intersecting family of size r independent sets is equal to the size of the largest r-star in the graph. This project aims to study the r-EKR property, and related concepts, for certain classes of graphs. 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.