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 |
| 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 |
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.