Consortium Schools:

Summer 2008 Research Projects:
Graphs with Randomly Weighted Edges. Mentors: C Starr and P Otto at Willamette University. Finding the minimal spanning tree of a weighted graph is a standard problem in graph theory. In this project we investigate the question: what happens when the weights are assigned randomly? Specifically, what is the expected total weight of a minimal spanning tree in this case? Some results are known; for example, recently a formula for the expected value in terms of the Tutte polynomial of the graph was derived. However, because the Tutte polynomial is difficult to compute, very few concrete results are known. One wellknown conjecture is the monotonicity of the expected value for complete graphs with uniformly distributed edges over [0,1]. Possible paths of exploration include deriving new formulations for the expected weight and applying existing results to different graphs or classes of graphs and other weight distributions; participants will also formulate their own questions for exploration. Four students will be accepted to join this research group. The Game of Go: Statistical Approaches to Artificial Intelligence. Mentors: P Drake and Y Chen at Lewis and Clark College. The Asian game of Go has simpler rules than Chess, but writing a Goplaying program that can compete with strong human players has proven exceedingly difficult. In fact, Go is considered one of the "grand challenges" of artificial intelligence. We will explore various statistical / machine learning approaches to the problem, including Monte Carlo methods, genetic algorithms, and learning from recorded games. Desired skills:
Four students will be accepted to join this research group. Competitive Graph Coloring. Mentors: J Nordstrom and C Dunn at Linfield. This project will be in an area of graph theory called competitive graph coloring. The Graph Coloring Game has two players: Alice and Bob. The players alternate coloring the uncolored vertices of a graph using a finite set of colors. Alice colors first. At each step of the game, the players must choose to color an uncolored vertex with a legal color. In the basic formation of the game, a color is legal for an uncolored vertex if the resulting coloring has no adjacent vertices with the same color. Alice wins the game if all vertices of the graph are colored; otherwise, Bob wins. The least number of colors such that Alice has a winning strategy is called the game chromatic number of the graph. The classes of graphs for which the most is known relative to this parameter are trees and forests. While the upper bound on the game chromatic number is known for these graphs, it is not known what structural properties the graphs must have in order to achieve the bound. This project will attempt to find these properties, thereby classifying trees and forests completely with respect to the Graph Coloring Game. Four students will be accepted to join this research group. Wavelet Analysis of Bird Song. Mentors: C Hallstrom, S Salomone at the University of Portland. Transform techniques, such as the Fourier Transform, have long been used to analyze timeseries data such as audio signals. The Wavelet Transform in particular has many features making it an attractive tool for extracting information from an audio signal needed to analyze recordings of bird songs. In the course of this project, we will investigate the fundamental concepts of wavelets and the wavelet transform and proceed to apply this tool to the analysis of bird songs. In particular, we'll consider the problem of removing noise from the signal as well as identifying individuals from recordings of multiple birds using both analytical and computational tools. Prior programming experience is not necessary. Four students will be accepted to join this research group. Obstacle Numbers of Graphs. Mentor: J Laison at Willamette University. This project will be in the field of geometric graph theory, which is a link between graph theory and discrete geometry, and uses tools from both disciplines. Obstacle numbers of graphs were defined by students in a research project in 2006. An obstacle representation of a graph G is a drawing of G in the plane with straight line edges, together with a set of polygons called obstacles, such that an edge exists in G if and only if it does not intersect an obstacle. The obstacle number of G is the smallest number of obstacles in any obstacle representation of G. The study of obstacle numbers of graphs has barely begun, and almost every question about them is still open. For example, is there a graph with obstacle number greater than 1? Students in the project will formulate their own conjectures and determine the direction research will take in this new area. Depending on the direction of research, some programming experience may be helpful. Two students will be accepted to join this research group. Photos of 2008 summer mentors:
Research topics from summer 2007. 