Undergrad Math Club Presetns Megan Heenehan (ECSU, Wes PhD '13): 'Kd Are You There???'

Thursday, February 26, 2015
12:00 PM - 1:00 PM (ET)
ESC 184 (Woodhead Lounge)
Event Type
Lecture
Contact
David Constantine, x2167
Department
Academic
Link
https://eaglet.wesleyan.edu/MasterCalendar/EventDetails.aspx?EventDetailId=48394

Abstract: Suppose I have a group of people and I want to know who is a friend of whom. I want to visualize how the people are connected. We can do this by creating a graph in which we have a vertex for each person and we put edges between people who are friends. We can then color the graph by assigning each vertex a color in such a way that if vertices are connected by an edge, that is if people are friends, they are assigned different colors. How many colors will we need? If there is a group of people that are all friends with each other they will each need a different color, this is a clique in the graph. More generally, if there are d people who are all friends with each other then there is a clique of size d (Kd) the graph will require at least d colors. Is the converse true? That is, if we need to use d colors, does this mean there is a clique of size d in the graph? Or are there d people that are all connected in some other way? In terms of graph theory the question is: Does a graph requiring d colors contain a Kd in some way? In this talk we will look at some attempts to answer this question. No prior knowledge of graph theory will be assumed.

Get Directions
Event Date
Event Time
Title
Building