DMD 2011




Poster Session



Local Attractions


Discrete Mathematics Days - July 15th & 16th

Lowell Abrams
Cellular Automorphisms of Surfaces and Self-Duality
joint with Dan Slilaty (Wright State University)

Given a graph G cellularly embedded in a closed surface S, an automorphism of G is called a cellular automorphism of G in S when, loosely speaking, it takes facial boundary walks to facial boundary walks. I will describe how we constructed complete catalogs of all irreducible cellular automorphisms of the sphere, projective plane, torus, Klein bottle, and three-crosscaps surface for a particular notion of reducibility related to taking minors.

We have also determined concrete procedures sufficient for constructing all possible self-dual embeddings in any closed surface S given a catalog of all irreducible cellular automorphisms in S. I will illustrate by way of examples some of these procedures and some resulting self-dual graphs.

sarah-marie belcastro
Counting Kempe-equivalence classes for 3-edge-colored cubic graphs

Maximal two-color chains of graph edges are called edge-Kempe chains, and switching the colors along such a chain is called a edge-Kempe switch.  Given two proper edge colorings of a graph, can you always get from one to the other via a sequence of edge-Kempe switches? (No.) If one edge-coloring of a graph can be transformed into another edge-coloring of that graph by a sequence of edge-Kempe switches, then the two edge-colorings are edge-Kempe equivalent. If a graph has at least two proper edge colorings that are not Kempe-equivalent, how many non-equivalent proper edge colorings are there?  We attempt to compute the number (denoted K'(G,3)) of edge-Kempe equivalence classes of 3-edge colorings for certain types of cubic graphs.  Along the way, we will introduce decompositions of cubic graphs and of 3-edge colorings of cubic graphs that assist in our computations.

This work is joint with Ruth Haas.

Jonathon Bloom
Modified Growth Diagrams, Permutation Pivots,
and the BXW Map Ø
* (pdf)

Satyan Devadoss
The world of particle collisions

Configuration spaces are not only fundamental objects in mathematics, but appear in numerous areas such as robot motion planning, DNA sequencing, sensor networks, surface reconstruction, and orgami designs. Our story is motivated by the conguration space of particles moving on a circle.

This talk, using visual brushstrokes, looks at the combinatorics and topology of this space, which is more complicated that it seems. These novel spaces now appear across a broad spectrum of research, from geometric group theory, to combinatorics, to phylogenetics and statistics. The entire talk is heavily infused with visual imagery.

Jeff Dinitz
Constructions for Retransmission Permutation Arrays

Recently, Li, Liu, Tan, Viswanathan, and Yang introduced a technique for resolving overlapping channel transmissions that used an interesting new type of combinatorial structure. In connection with this problem, they provided an example of a 4 x 4 array having certain desirable properties. We define a class of combinatorial structures, which we term "Retransmission Permutation Arrays" (or RPA's), that generalize the example that Li et. al. provided. These RPA's turn out to be arrays that are row latin and satisfy an additional property in each of the top two corners. We show that these arrays exist for all possible orders. We also define some extensions having additional properties, for which we provide some partial results.

Peter Dodds
Complexity, Big Data Science, and Happiness

I will open with my own evolving view of complex systems, what we really mean when we talk about a science of complexity, and, possibly for my own amusement, the framing of mechanisms as stories.  I will discuss how science and engineering are changing as we move further into the era of understanding, controlling, and creating complex systems, as more research fields, ranging from astronomy to literary analysis, make the transition from being data scarce to data rich.  I will give a short survey of some key advances in the area of complex networks which has capitalized on work in statistical mechanics and combinatorics.  I'll end the talk with some findings from our present work on measuring emotional states through text analysis with a focus on the English language and Twitter.

Tom Hull
Bounds on a sequence for counting flat vertex folds

We consider the problem of counting the number of different ways C(v) in which a single vertex v in a flat origami crease pattern can fold flat.  Here we define two foldings of the vertex to be different if they have different assignments of mountains and valleys to the creases.  This problem is generally very well-understood, and in this talk we will summarize what is known about its solution.  However, closer examination of these results leads to questions about what values are possible for C(v).  This generates a sequence N_n of the number of different possible values for C(v) where v is a flat-foldable vertex of degree 2n.  In addition to being a new sequence, not much is known about N_n.  We present ways of calculating N_n, give an exponential upper bound, and wrestle with problems encountered with finding a good lower bound for N_n.

John Jungck
If Life Is Analog, Why Are We Being So Discrete?

While Calculus and/or Statistics are the one or two courses either required of or most frequently taken mathematics courses by biology students, they screen most biology students from (1) reasoning analytically about broad visual metaphors of biology such as phylogenetic trees, pedigrees, fate maps, metabolic pathways, food webs, interactomes, and genetic maps that represent relationships as graphs, (2) measuring with new mathematical tools based upon fractals, computational geometry, Lindenmayer systems, cellular automata, etc., and (3) understanding why  they  should choose one option versus another in widely used “black box” software such as in bioinformatics packages for analyzing DNA, RNA, and protein sequences, in geographic information systems for examining causal bases of spatial relationships in environmental and epidemiological problems, and in morphological image analysis of two and three dimensional biological  specimens. I will report on biology student projects that use graph theory to explore numerous areas of biology ranging from molecular biology, cell biology, genetics, anatomy, and developmental biology to population biology, ecology, epidemiology, and evolution with highly  interactive software packages that we have built such  as BioGrapher, Ka-me’: A Voronoi  Image Analyzer, 3D FractaL Tree, many spreadsheet applications such as EvolSeq, Split Decomposition, and javaBENZER from our Biological ESTEEM (Excel Simulations and Tools for Exploratory, Experiential Mathematics) Project, and NUMB3R5 COUNT! (Numerical Undergraduate Mathematical Biology Education) Project, and on projects from our recent workshop at the National Institute of Mathematical Biology Synthesis Center (NIMBioS) on “Graph Theory and Networks in Biology”.

Brigitte Servatius
Geometric and Petrie (Self) Duality

For a graph embedded on a surface there are several forms of duality, e.g.
the geometric dual, where vertices and faces are interchanged, or the Petrie dual, where vertices and left-right paths are interchanged. Self-dual graphs are well studied on the sphere and on other surfaces, but what about self-Petrie graphs? On the sphere there are no interesting graphs which are both self-dual and self-Petrie, but are there any on other surfaces? We want to explore the existence and construction of such highly regular maps.

Eric Swartz
Locally 2-arc transitive graphs (pdf)

Thomas Zaslavsky
Nonattacking Chess Pieces: The Bishops' Dance

Recreational chess fans (of Western chess) have asked questions like: What is the largest number of identical pieces (queens, or bishops, or ...) that can be placed on a chessboard so none attacks any other? A harder question: Given q identical pieces, how many ways can they be placed on an n x n chessboard? Here q is fixed, n is variable. Vaclav Kotesovec has collected and discovered amazingly many formulas for non-attacking chess pieces, but no proofs.

Seth Chaiken, Chris Hanusa, and I found that for some types of chess piece, including the queen and bishop, the answer is given by a cyclically repeating sequence of polynomials. This can be proved by geometry. To find the polynomials one must know how long the sequence is (the 'period'). That can be partly solved by geometry, but it is hard. We did prove that the bishop has period 2, no matter how many bishops there are. The proof uses the geometric theory of signed graphs.

Our theorem implies that Kotesovec's method is strong enough to give correct formulas for the bishops. His formulas show surprising properties, some of which we can or think we can prove geometrically.

I will explain the geometry and graph theory that lie behind all the foregoing assertions.