[May, 2015] DIMACS will welcome students participating in the 2015 Research Experiences
for Undergraduates (REU) program on June 1, and it looks like
the students from the 2014 program left them big shoes to fill.
During the past year, the 2014 REU students have co-authored 13
papers, given 13 conference talks, and presented many more posters
describing their research. In anticipation of the 2015 program, we
highlight a few of the results from the 2014 group.

The REU was well represented at the 2015
Joint Math Meetings (JMM), which included talks by five
students and posters presented by five more. Among the speakers was
Elizabeth Yang (Princeton University) who worked with postdoctoral
researcher Brian Nakamura on a project exploring the relationship
between competition graphs and permutation patterns. Competition
graphs trace their roots to ecology, where
they were applied to the study of food webs. A competition graph has
a node corresponding to each species in an ecosystem and a link
between them if they share a common prey. Thus, two species are
connected if they compete for food. More generally, competition
graphs can be created for other directed graphs (not just those
associated with food webs). They are constructed over the same set
of nodes, with two nodes being connected by a link in the
competition graph whenever they have a common successor node in the
graph. Studying competition graphs that arise from other families of
directed graphs is an area of active research. Nakamura and Yang’s
work extends previous work from the literature on competition graphs
arising from doubly partial orders on points in the plane. They
illustrate the connection between permutations and directed graphs
and then show that any doubly partial order
corresponding to a finite set of points in the plane can be
thought of as a doubly partial
order on a permutation in terms
of its induced directed graph and
competition graph. The connection with permutations allows them to
make observations on how the structure within a permutation leads to
structure within the competition graph by showing that each edge in
the competition graph corresponds to an instance of a 123 or a 132
pattern within the permutation. Additional related results are
described in Nakamura and Yang’s complete work on the arXiv.

Two student papers were also included in the 2015 IEEE Symposium on Technologies
for Homeland Security (IEEE HST). Roshan Thapaliya (Howard
University) worked with postdoctoral researcher Brian Ricks in
developing a simulation to assist homeland security professionals in
planning
for
crowd control during emergencies. They developed their simulation
based on a real incident at the Bradford City soccer stadium in 1985
that resulted in 56 deaths and more than 200 injuries. In what
became the worst fire disaster in English soccer history, a small
blaze turned into a panic-inducing inferno in less than three
minutes. The simulation that Thapaliya and Ricks developed is
envisioned as a tool to help planners understand the dynamics of a
crowd during a panic situation. It enables them to explore the
effect of factors such as: the location of fire and how fast it
spreads; the location of obstacles and how quickly they can be
surmounted; and the speed of pedestrian movement. A screen shot from
their simulation is shown at left. On the left side, an animation
shows the movement of people represented by red, blue, and black
dots. The red dots represent people who always make good decisions;
the blue are people who sometimes make mistakes; and the black dots
represent people who have perished in the fire represented by the
yellow disc. The gray bar represents a barrier that was present at
Bradford and prominent in film and interviews about the fire.
Simulations revealed that although the position of the obstacle had
an impact on survival rate, its affect was not nearly as large as
expected.

IEEE HST also included the work of fellow 2014 REU students Leo Behe
(Lehigh University) and Zachary Wheeler (Grove City College) and
2013 DIMACS REU student Brian Knopp (Montana Tech). The three
students worked with DIMACS faculty member William Pottenger and
postdoctoral researcher Christie Nelson on exploring the relative
performance of two machine learning methods for text classification.
The methods they tested were the well-known naïve Bayes (NB) method,
which assumes data are independent and identically distributed
(IID), and a variant called higher-order naïve Bayes (HONB) which
captures some of the dependencies within real-world data for better
performance, but at a higher
computational
cost. In an effort to better predict when it is advantageous to
invest the additional computational effort in using HONB, the
students and their mentors tested whether there is a correlation
between the degree to which the data follow a Zipf distribution and
the performance of HONB. In Zipf-distributed data, the frequency of
any value is inversely proportional to its rank in the frequency
table. It has been observed that natural language data can often
approximated with a Zipf distribution. Behe, Wheeler, and other
members of their research team looked at seven different real-world
data sets – both text and microtext – whose features were character
substrings of length n (called n-grams). In tests with multiple
values of n and multiple sizes of feature sets for each data set,
the team’s initial results suggest that in instances where the
Zipfian-ness is increasing but has not yet reached 100%, there does
seem to be a correlation with the performance of HONB. Such cases
generally involve smaller values of n and smaller feature sets.

Priscilla Lo (Rutgers University) worked with chemistry professor
Wilma Olsen and postdoctoral researcher Nicolas Clauvelin in both
the 2013 and 2014 DIMACS REU programs. In a forthcoming article in
the Journal of
Physics: Condensed Matter, they introduce a model and
computational framework that make it possible to incorporate
detailed structural features of DNA and histones in simulations of
short chromatin constructs. Their results reveal a remarkable effect
of nucleosome spacing on chromatin flexibility, with small changes
in DNA linker length significantly altering the interactions of
nucleosomes and the dimensions of the fiber as a whole. In addition,
they found that changes in nucleosome positioning influence the
statistical properties of long chromatin constructs. They observed
that simulated chromatin fibers with the same number of nucleosomes
exhibit polymeric behaviors ranging from Gaussian to worm-like,
depending upon nucleosome spacing. These findings suggest that the
physical and mechanical properties of chromatin can span a wide
range of behaviors, depending on nucleosome positioning, and that
care must be taken in the choice of models used to interpret the
experimental properties of long chromatin fibers.

Printable version of this story: [PDF]

References:

L. Behe, Z. Wheeler, C. Nelson, B. Knopp, and W. Pottenger, “To Be
or Not to Be IID: Can Zipf’s Law Help?” Proceedings of the 2015 IEEE
Symposium on Technologies for Homeland Security.

N. Clauvelin, P. Lo, O. I. Kulaeva, E. V. Nizovtseva, J.
Diaz-Montes, J. Zola, M. Parashar, V. M. Studitsky, and W. K. Olson,
“Nucleosome Positioning and Composition Modulate in Silico Chromatin
Flexibility,” to appear in Journal of Physics: Condensed Matter 27,
(2015).

B. Nakamura and E. Yang, “Competition Graphs Induced by
Permutations,” http://arxiv.org/abs/1503.05617.

R. Thapaliya and B. Ricks, “Using Crowd Simulation to Suggest
Efficient Evacuation in Emergency Situation,” Proceedings of the
2015 IEEE Symposium on Technologies for Homeland Security.

DIMACS Homepage

Contacting the Center