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.
Graduate Student Combinatorics Seminar
Wednesday, December 3, 2008 - 12:30pm
Omar Abuzzahab
University of Pennsylvania