Consortium Schools:

Summer 2009 Research Projects:
Bar kvisibility graphs. Bar visiblity graphs were first studied in the 80's by graph theorists and computer scientists working on Verylargescale 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 onetoone 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 bark visibility graphs. In a bark visibility graph a line of sight is allowed to penetrate at most k bars. We will start by examining recent results regarding bar1 visibility graphs and study questions such as: what is the largest number of edges in a bar kvisibility graph with n vertices? what is the largest crossing number of a bar kvisibility graph? what is the largest genus of a bar kvisibility 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. 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. 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.
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. 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 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:
Six students will be accepted to join this research group. Competitive Graph Coloring. 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 wellknown 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:
Research topics from summer 2008. Research topics from summer 2007. 