Spring 2002 GSS Schedule

Organizer: Jeff Farr

Date Speaker Topic Abstract
January 20 MLK Holiday
January 28 John Villalpando The Channel Assignment Problem and L(2,1) colorings Digital television, cell phones, and other wireless communications are changing the way we live. While discussing the Steelers' win on the cell phone and watching ESPN highlights over satellite television you must have asked, how does this information get to me? Wireless communication flows through the air waves which are quickly becoming saturated. Your cell phone company must avoid the frequencies used by your satellite company.

The channel assignment problem is the problem of assigning frequencies to radio transmitters in such a way that the communications do not interfere. Two transmitters are considered to interfere with each other if they share similar frequencies and are at a prescribed distance from one another.
In this presentation we will begin by discussing the channel assignment problem. We will introduce some concepts of graph theory, primarily colorings. We will then discuss L(2,1) colorings and its relationship to the channel assignment problem. We will finish by studying certain parameters of L(2,1) colorings on paths, cycles, trees, and various other types of graphs. pdf file
February 4 Jeff Farr Alliances in Graphs Alliances play important roles in ecology, in the military, in society, and in many other applications. Of course, many networks and relationships may be modelled using graphs. In this talk we introduce the brand new study of offensive and defensive alliances in graphs. Vertices which are allied agree to support each other in the case of an ``attack" by vertices that are not part of the alliance. An alliance in which every member is important is called a critical alliance. We will study the mathematical properties of alliances, paying special attention to critical alliances. pdf file
February 11 Brian Hunt A Gentle Introduction to Multicriteria Optimization Many problems involve finding a preferred solution in the presence of multiple objective functions or criteria. Most often some (or possibly all) of these criteria are in conflict with each other, especially as the number of criteria increases. A solution that is very good with respect to one criterion may be poor with respect to one or more of the other criteria. The presence of this conflict makes it impossible to find an optimal solution that optimizes all objective functions simultaneously. This requires introducing the concept of a nondominated solution. In this talk, nondominated solutions will be defined and solution methodologies for finding the nondominated solution set will be discussed. Examples will be presented for bi-criteria problems for ease of graphical representation. Preference cones and the role they play in multicriteria optimization problems will also be discussed.
pdf file
February 18 President's Day
February 25 Suman Balasubramanian A Colorful Approach to Gallai Theorems In 1959 Gallai showed that the vertex independence number and the vertex covering number of a graph G=(V,E) sum to V. Over the last twenty years, many results similar to Gallai's Theorem have been observed . These theorems are referred to as ``Gallai Theorems," and usually have the form: a + b =n, where a and b are integer-valued minimum or maximum functions corresponding to some property of a graph on n vertices.

Slater described several graph subset parameters using linear programs (LP) and integer programs (IP). Graph theoretic minimization (maximization) problems can be modelled in terms of LP/IP problems using the adjacency matrix, A, the (closed) neighborhood matrix, N, and the vertex-edge incidence matrix, H. Gallai Theorems for the resulting parameters may be obtained by using the concepts of LP-duality and complementarity. Slater defines several of the parameters generated by the above matrices, but leaves other parameters unstudied. In this talk, we take a closer look at some of those unstudied parameters.
March 11 Tom Macdonald MIT Guest Speaker Ambiguity Functions: What are they? How do engineers use them? Why are they interesting to mathematicians? The ambiguity function provides a description of a finite-energy waveform (i.e., a square-integrable function) in both the time and frequency domains. This function has been used extensively to characterize radar and sonar applications. In this talk the definition of the ambiguity function is given, and a number of salient properties of the function are discussed. The application of the ambiguity function as a tool to analyze satellite communications is presented. Particular attention is paid to the development of the relationship between the ambiguity function and the performance of a communications system. Finally, the talk concludes with the introduction of the synthesis problem for ambiguity functions, which is a non-trivial mathematical exercise. pdf file
March 18 Spring Break
March 25 Shannon Purvis The Kings Problem Consider an n by k chessboard. Our task is to place non-attacking kings on the board. We want to know how many possible boards we can get with no two kings in adjacent squares. This number turns out to be hard to find. In this talk, we discuss a matrix representation for the legal configurations of kings on the board and use these matrices to find the number of possible n by k boards where n is fixed. We will also discuss approaches to solving the problem asymptotically for any n and k.
April 1 Easter Break
April 8 Jon Edds Card Collecting and Combinatorics Many young kids take an interest in collecting football and baseball cards. The goal is to collect the whole set of n cards by purchasing packs that contain k cards. Provided that the cards in each pack are uniformly distributed without repetition, we are able to represent this situation by a stochastic matrix. By raising this matrix to the power t, we are able to express the probability of collecting all the cards by purchasing t packs of cards. We develop an asymptotic formula as n, k, and t go to infinity. pdf file
April 15 Ron Scott Isomorphisms of Elliptic Curves Having a Point of Order 5 After a brief introduction describing how points on elliptic curves behave like an abstract algebra group, a special curve is introduced which has a point of order 5. The goal of the study is to find out how many of these curves are distinct and how many are just isomorphisms of another curve. Answering this question requires a journey through an interesting application of Maple's algebra abilities, the factoring of polynomials over finite fields, some simple Galois theory, and a little probability theory at the end. Certain regular isomorphism patterns are found, together with more surprising and random-seeming results. pdf file