Untitled Document

All the students in MAT 289.23 (now MAT 268) have presented posters at the Illinois State University Undergraduate Research Symposium. Some students participated two years in a row (because of follow-up work with the instructor).

2005 Undergraduate Research Symposium

LABELINGS OF 2-REGULAR GRAPHS
By: Alejandro Aguado, Heidi Hake, Mindy Schneider, Jessica Stob, Barbara Thompson, Danielle Vanschindel, Marcus Williams, and Hera Yayla, Mathematics; Joel Eagles, Chemistry
Faculty Advisor: Saad El-Zanati

In 1965, Alex Rosa introduced four kinds of graph labelings as tools for finding cyclic decompositions of complete graphs. The four labelings were called alpha, beta, sigma and rho. Alpha-labelings are the most restrictive labelings and rho-labelings are the least restrictive. All four produce cyclic decompositions of complete graphs. Since then, literally hundreds of papers have been written about labelings of various graphs. Most of the research has however focused on beta-labelings (also known as graceful labelings). In our study we focus on labelings of 2-regular graphs (graphs consisting of disjoint cycles). It is known that in about half the cases, 2-regular graphs do not admit beta-labelings. We find sigma and rho-labelings of a number of 2-regular graphs. Our results support a conjecture by El-Zanati and Vanden Eynden that all 2-regular graphs admit rho-labelings.

SCHEDULING OF TOURNAMENTS AND GRAPH FACTORIZATIONS
By: Alejandro Aguado, Mathematics
Faculty Advisor: Saad El-Zanati

This work was inspired by the following problem: twelve friends gather annually to play golf. They play in three groups of four for five days. Because this is a "social" event, each person would like to be grouped with everyone else at least once. Moreover, it is desirable for each person to have the same schedule as everyone else (i.e., a maximal balanced schedule is desired). It is easy to see that it is impossible to have each person play with everyone else in five days. We however find a best-possible schedule. In this optimal schedule each person plays with three other people twice, with six people exactly once and does not play with two people. This is a special case of a more general mathematical problem related to graph factorizations and scheduling of tournaments. In our study we invertigate optimal solutions of these general problems.

2005 Undergraduate Research Symposium

ON GAMMA-LABELINGS OF SOME INFINITE FAMILIES OF ALMOST-BIPARTITE GRAPHS I

By: Bonnie Frank, Lauren Barracca, Brittny Fitzgerald, Rachel Kuna, Peter Lamonica, Jennifer Love, Andrew Thurman, Mathematics
Faculty Advisor: Saad El-Zanati

In 1965, Alex Rosa introduced several types of graph labelings as means of attacking the problem of finding cyclic graph decompositions of complete graphs. Rosa showed that if a graph G with n edges admitted certain kinds of lablelings (rho-, sigma- or beta-), then G cyclically decomposes the complete graph on 2n+1 vertices. Moreover, if G is bipartite and if it admits a restrictive labelling, called an alpha-labeling, then G cyclically decomposes the complete graph on 2nx+1 vertices for every positive integer x (thus G divides an infinite family of complete graphs, rather than just one). A new labeling that yields the same decomposition outcome as alpha-labelings was recently introduced for graphs that are not necessarily bipartite. Blinco, El-Zanati and Vanden Eynden showed that if an almost-bipartite graph G with n edges admitted what they call a gamma-labeling, then G cyclically decomposes the complete graph on 2nx+1 vertices for every positive integer x. A non-bipartite G graph is almost-bipartite if it contains an edge whose removal makes G bipartite. As part of our project in MAT 289.23, our class is searching for infinite families of almost bipartite graphs that admit gamma-labelings.

ON GAMMA-LABELINGS OF SOME INFINITE FAMILIES OF ALMOST-BIPARTITE GRAPHS II
By: Hera Yayla, Ryan Bunge, Michael Duffy, Stephen Kinczyk, Ashley Leonard, Anthony
Schlorff, Chris Uhlman, Jake Klimkewicz, Mathematics
Schlorff, Chris Uhlman, Jake Klimkewicz
Faculty Advisor: Saad El-Zanati

2006 Undergraduate Research Symposium

OPTIMAL MUTATION RATES FOR DIGITAL EVOLUTION: EXPLORING AVIDA
By: Nora Hayes, Joshua Hallam, Ryan LaCosse, Sarah Wagner, Mathematics
Faculty Mentor: Fusun Akman

We are exploring Avida, revolutionary software created to study the biology of self-replicating and evolving digital organisms which are nothing but simple computer programs. Since evolution of real-life organisms is impossible to observe accurately, studying digital organisms allows us to record many generations in a short period of time. These organisms compete for “energy” (food) which enables them to copy their genetic code and reproduce asexually. Experiments have shown that Avida not only models but also explains the mechanisms behind the key ingredients of evolution, such as adaptation, in nature.
In this project we make adjustments to the mutation rate, the environmental settings, and the initial population, and run the program for several generations. A mutation rate in Avida is the probability that a digital organism will have some of its code or instructions changed. A mutation can occur as a copying error or through point mutation, which is the replacement of an instruction with another instruction. Environmental settings are tasks that need to be performed (such as addition of binary strings); the organisms that adapt best to the environment through mutated genes (programs) are rewarded with more energy to replicate themselves. The initial population is the set of primitive organisms that are present when the world begins. The adaptation of one organism or a whole population is measured by a function called the “Fitness Level.” The fitness level is inversely proportional to the gestation period. Our objective is to find the optimal mutation rates to maximize the fitness levels. We will create a new digital world that is 60 by 60 cells and contains four different types of organisms. These organisms will contain acode with “nop” commands (similar to “junk DNA”): they will not be able to reproduce at first. The organisms will gain the ability to replicate through random point mutations. We will start the world with a certain point mutation rate. After 100,000 generations we will extract the dominant genotype and put it in an environment where the point mutation is 0. After 25,000 generations in this new environment, we will look at the average fitness level for the population. We will repeat the experiment 50 times, each with different point mutation rates, and compare fitness levels to see which point mutation rates maximize the fitness level.

FRACTAL DIMENSION OF RIVER SYSTEMS VERSUS GEOLOGICAL AGE
By: Bryan Robinson, Brian Schmalzer, Andrew O'Connell, Michael Urbanc, Mathematics
Faculty Mentor: Fusun Akman

There are many naturally occurring objects that seem to repeat themselves infinitely many times as we observe them at higher and higher resolutions. For example, parts of silhouettes of mountain ranges, shorelines, branching trees, bronchi, and river systems when studied on a smaller scale tend to have the identical shape (on the average) as the larger object. These “self-similar” or “fractal” objects do not live in the same Euclidean world as the rest of us, in the following sense. Unlike perfect geometric shapes, fractals are far from being smooth. The fractal dimension of such an object is a measure of the “wiggliness” of the object (which does not change even after a change of scale). As a crude example, we consider a sheet of paper which is normally two-dimensional. If we start crumpling it, the sheet starts looking thicker than 2-D due to the creases, and when completely balled up it almost looks three-dimensional. It is believed that the human eye perceives a landscape whose fractal dimension is 0.2 to 0.3 higher than the supposed Euclidean dimension as “natural”. Thus the rugged Blue Ridge Mountains look natural with dimension 2.2-2.3, whereas the super-rugged Bryce Canyon in Utah (dimension 2.5) looks alien. Computer-generated images of fractal landscapes have been used in cinematography for a long time, arguably starting with “The Wrath of Khan” (Star Trek II).
During this project we will obtain highly detailed digital images of river basins and data on the ages of the same rivers as measured by geologists. We will use these pictures to carefully define and calculate the fractal “box-counting” dimension of each, using standard software. We will then relate the fractal dimensions of these rivers to the ages of the rivers: we hypothesize that older river basins have higher dimension. In the crumpled paper example above, we notice that as time progresses the wiggliness (dimension) of the sheet increases; this is believed to be a common feature of many natural formations. Another aspect of our project will be the comparison of mathematical concepts such as “fractal dimension” to geological concepts such as “sinuosity” that describe river systems quantitatively and the creation of a partial dictionary. We will be asking for the help of experts from the Geology Department at ISU in locating geological software that computes variables related to the fractal dimension.

ON GAMMA-LABELINGS OF 2-REGULAR ALMOST BIPARTITE GRAPHS
By: Ryan Bunge, Mathematics
Faculty Mentor: Saad El-Zanati

In 1965, Alex Rosa introduced several types of graph labelings as means of attacking the problem of finding cyclic graph decompositions of complete graphs. Rosa showed that if a graph G with n edges admitted certain kinds of labelings (rho-, sigma-, or beta-), then G cyclically decomposes the complete graph on 2n+1 vertices. Moreover, if G is bipartite and if it admits a restrictive labeling, called an alpha-labeling, then G cyclically decomposes the complete graph on 2nx+1 vertices for ever positive integer x (thus G divides an infinite family of complete
graphs, rather than just one). A new labeling that yields the same decomposition outcome as alpha-labelings was recently introduced for graphs that are not necessarily bipartite. Blinco,El-Zanati, an Vanden Eynden showed that if an almost-bipartite graph G with n edges admitted what they call a gamma-labeling, then G cyclically decomposes the complete graph on 2nx+1 vertices for every positive integer x. A non-bipartite G graph is almost-bipartite if it contains an edge whose removal makes G bipartite. I show that every 2-regular almost-bipartite graph G has a gamma -labeling, except when G is C_3 or C_3 U C_4.