Summer 2009 Research Projects:

Bar k-visibility graphs.
Mentors: I Johnson and E McNicholas at Willamette University.

Bar visiblity graphs were first studied in the 80's by graph theorists and computer scientists working on Very-large-scale integration (VLSI) technology. Imagine a set of horizontal line segments, or bars, in the plane. We say that a graph G is a bar visibility graph if there exists a one-to-one correspondence between vertices of G and bars in the set, such that there is an edge between two vertices in G if and only if there exists an unobstructed vertical line of sight between their corresponding bars. Recent attention has been drawn to a variety of generalizations and restric- tions of bar visibility graphs, including unit bar-k visibility graphs. In a bar-k visibility graph a line of sight is allowed to penetrate at most k bars. We will start by examining recent results regarding bar-1 visibility graphs and study questions such as: what is the largest number of edges in a bar k-visibility graph with n vertices? what is the largest crossing number of a bar k-visibility graph? what is the largest genus of a bar k-visibility graph? There are a plethora of unanswered questions in this field and students may wish to find and investigate their own.

Four students will be accepted to join this research group.

---

Studies in Combinatorial Game Theory.
Mentors: H Nordstrom at University of Portland

Although the formal mathematical study of game is only a few centuries old, it is quite clear that mathematicians and philosophers have been interested in games throughout human history. Many games studied are generalizations of children's games or simplified games of military strategy. One such game is a derivation of the NIM game and consists of a pile containing an odd number of objects from which players take turns removing one or more objects, with at most k objects removed by each player during his or her turn. The player who has removed an odd number of objects at the end of the game wins. If n is the number of objects in the initial pile, a specific solution for the pair (n,k) can be found. However, no general solution is known. This project will focus on generating general solutions to this game (and other similar games) through combinatorial and number theoretic techniques.

Two students will be accepted to join this research group.

---

Probabilistic Forecast Modeling in Operations Management.
Mentors: G Mitchell and M Niederhausen at the University of Portland

Many tactical forecasting applications exist in retail and wholesale distribution. For the most part, traditional methods are based on statistical analysis, such as exponential smoothing, HoltÕs and WinterÕs methods, and numerous variations of these produce forecasts of acceptable quality. Given stable demand and sufficient volume, these methods perform well enough to obviate the need for more sophisticated approaches.

There are, however, a number of problems in retail forecasting that cannot be adequately solved using these methods. Examples include very slow moving items, intermittent sellers, and unstable seasonal demand. This summer we will look for entirely new approaches for solving these problems. We will delve heavily into the possible applications of probability theory with an eye toward developing forecasting models of a predictive, rather than reactive, nature. We will test our models through validation against industry data and via simulation models that we construct for this purpose.

Prerequisites: Coursework in descriptive statistics and probability theory desirable. Some knowledge of basic computer programming will be useful and experience with MATLAB, C/C++, or Visual Basic is a plus.

Four students will be accepted to join this research group.

---

The Game of Go: Statistical Approaches to Artificial Intelligence.
Mentors: P Drake, J Mache and Y Chen at Lewis and Clark College.

The Asian game of Go has simpler rules than Chess, but writing a Go-playing 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 and learning from recorded games. This summer's work will focus on decomposing the board into regions, so that the program can perform and combine several local searches (with the work possibly spread over several machines) rather than performing a single global search.

Desired skills:
- Programming experience, especially in Java
- Basic knowledge of statistics
- Experience playing Go
(Parallel programming experience would be a plus.)
Here's more on the project so far: Orego
If you are not familiar with Go, please see: http://www.usgo.org/usa/waytogo/index.html

Six 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. We will consider variations of this game by altering the definition of a legal color. We then examine these variations with well-known classes of graphs, such as trees, outerplanar graphs, planar graphs, and chordal graphs. Our goal will be to use the structural properties of the class to formulate winning strategies for both Alice and Bob.

Four students will be accepted to join this research group.

---

Photos of 2009 summer mentors:

Erin McNicholas	Inga Johnson	Jens Mache	Peter Drake	Yung-Pin Chen
Jennifer Nordstrom	Chuck Dunn	Hans Nordstrom	Meike Niederhausen	Gary Mitchell

Research topics from summer 2008.

Research topics from summer 2007.