Texas State University

Title: NREUP Site in Discrete Mathematics

Director:

Email:

Dates of Program: May 24 - July 8, 2010

Summary: The program will focus on the following two research projects:

A drawing of an infinite graph is said to be incomprehensible if the edges are arbitrarily long or if the windows of any fixed diameter drawing contains arbitrarily many vertices. A graph is incomprehensible if every drawing of it is incomprehensible. For example, any drawing of the infinite grid in an infinite strip of fixed width is incomprehensible. The students will work on extensions of these definitions and related results to finite graphs. For example, to what extent are real-world graphs, such as social networks or the internet, incomprehensible?
The squares of an mxn checkerboard are alternately colored black and white. Two squares are said to be neighboring if they belong to the same row or the same column and there is no square between them. In 2010, Okamoto, Salehi, and Zhang conjectured that one can place coins on some of the squares of an mxn checkerboard (at most one coin per square) such that for every two squares of the same color the number of coins on neighboring squares are of the same parity, while for every two squares of different colors the number of coins on neighboring squares are of opposite parity. The students will work on completing a proof of the above Checkerboard Conjecture and on answering some related questions on the modular chromatic number of graphs.

Student Researchers Supported by MAA: