Colloquium Speaker

Speaker:Katherine St. John
Boise State University
Topic:Games on Random Structures
Date:Thursday, May 20, 1999
Time:9:30 AM
Place:Gould-Simpson, Room 701


Refreshments will be served in the 7th-floor lobby of Gould-Simpson at 9:15 am


ABSTRACT


Games are a useful tool for classifying structures, such as bit strings and graphs. This talk will focus on randomly-generated bit strings and graphs, what these structures ``look like,'' and some standard game techniques used in computer science. For example, we can ask what fraction of graphs with 3 vertices contains a triangle? What is the fraction for graphs with 4 vertices? What happens to this fraction as the number of vertices gets large? The answer changes, in surprising ways, if we allow the edges to occur randomly (i.e. with probability that depends on the number of vertices). We will discuss these results of Fagin, Spencer, and Shelah, and recent work on other important structures in computer science such as bit strings and trees.