Penn Arts & Sciences Logo

Graduate Student Combinatorics Seminar

Wednesday, December 3, 2008 - 12:30pm

Omar Abuzzahab

University of Pennsylvania

Location

University of Pennsylvania

DRL 4N30

Given a graph, what is the best way to determine if it is connected? We can try writing an algorithm which queries the existence of edges and uses this information to decide if the graph is connected. Can we find such an algorithm which will never have to query every possible edge? The answer is no, and connectivity is said to be an "evasive" graph property. A much harder question asks "what makes properties evasive?" and surprisingly the techniques here will also involve elementary group theory and topology.