Research

Discrete Mathematics

(Leader: Prof. Greg McColm)

Monday, April 21, 2014

Title: Coradjacent Edge Fundamental Transversals
Speaker: Joy D'Andrea
Time: 2:00pm‐3:00pm
Place: CMC 108

Abstract

Given a face fundamental transversal (see seminar talk from Spring 2010) on the complex of a polyhedron, two edges are called coradjacent if they share a common face. To obtain its edge transversal, we require that every edge we gather to be incident to two faces in different orbits in the face fundamental transversal (this type of edge is known as an interior edge). An edge in a represented orbit is the predecessor edge, whereas an edge that is coradjacent to the predecessor is in an unrepresented orbit, which is the successor edge. In this talk, we will present a partial result that shows if a face fundamental transversal has a set of interior edges that intersects each orbit at least once, then there exists a CRH (coradjacency relation) connected edge fundamental transversal whose edges are incident to the faces in the face fundamental transversal.

Monday, April 14, 2014

Title: Efficient Biclique Coverings
Speaker: Gregory Churchill
Time: 2:00pm‐3:00pm
Place: CMC 108

Abstract

A biclique is a complete bipartite subgraph. A biclique covering for a graph is a family of bicliques where each edge of the graph belongs to at least one biclique. For this talk we will discuss how efficient a biclique covering can be from two perspectives: we will consider the weight of a biclique covering—which is the sum of the vertex sets of the bicliques in the covering; and we will consider biclique coverings of a graph where each edge of the graph is contained in precisely one biclique.

The two main results to be presented will involve biclique coverings of the complete graph. But what the speaker finds most interesting is the highly surprising proofs of these results.

Monday, April 7, 2014

Title: Advances on Boolean admissibility systems
Speaker: Joseph Van Name
Time: 2:00pm‐3:00pm
Place: CMC 108

Abstract

A Boolean admissibility system is a Boolean algebra along with extra structure that tells one which least upper bounds are important and should be considered. Boolean admissibility systems are related to point-free topology since the category of all zero-dimensional frames (i.e., frames with a basis of clopen sets) is equivalent to the category of all subcomplete Boolean admissibility systems.

We shall first focus on the problem of determining when a subset of a Boolean algebra is precomplete. The collection of all precomplete subsets of a Boolean algebra \(B\) gives a characterization of the smallest zero-dimensional frame that has \(B\) as its algebra of complemented elements. Determining the precomplete subsets of a Boolean algebra is complicated by the fact that the precomplete subsets are not preserved under taking most of the standard constructions involving Boolean algebras such as subalgebras and images. We shall also focus on the problem of how a Boolean admissibility system can be represented as a quotient of a Boolean admissibility system whose underlying Boolean algebra is an algebra of sets and each considered least upper bound is a union of sets.

Monday, March 31, 2014

Title: Two Approaches to Simulating One-Dimensional Cellular Automata Using DNA-based Tiles
Speaker: Daria Karpenko
Time: 2:00pm‐3:00pm
Place: CMC 108

Abstract

The basic abstract mathematical framework for self assembly of DNA-based tiles is the aTAM, or Abstract Tile Assembly Model. Recent advances in DNA nanotech have suggested new mechanisms that would allow the “sticky ends” of the tiles to be enabled or disabled via tile to tile interaction during the self-assembly process. The aTAM can thus be extended to accomodate activation and deactivation of the aforementioned kind. We demonstrate an application of such an extension by providing two tile set constructions to simulate the action of a cellular automaton on a given input: one for a static assembly of the entire corresponding time history and another for a dynamic asynchronous simulation, which allows tiles to be replaced by their next time step counterparts using deactivation in conjunction with activation.

Monday, March 24, 2014

Title: Three Dimensions of Knot Coloring
Speaker: Brittany Hurst
Time: 2:00pm‐3:00pm
Place: CMC 108

Abstract

This survey article discusses three aspects of knot colorings. Fox colorings are assignments of labels to arcs, Dehn colorings are assignments of labels to regions, and Alexander-Briggs colorings assign labels to vertices. The labels are found among the integers modulo \(n\). The choice of n depends upon the knot. Each type of coloring rules has an associated rule that must hold at each crossing. For the Alexander-Briggs colorings, the rules hold around regions. The relationships among the colorings is explained.

Monday, March 17, 2014

Title: A Parity Theorem for crossings in \(K_n\) and \(K_{m,n}\)
Speaker: Michelle Krause
Time: 2:00pm‐3:00pm
Place: CMC 108

Abstract

The crossing number \(\mathrm{cr}(G)\) of a graph \(G\) is the minimum number of edge-crossings needed when \(G\) is drawn in the plane. Very few values are known for either complete bipartite graphs \(K_{m,n}\) or complete graphs \(K_n\) and the best general result for \(K_{m,n}\) isn't really all that general. I will talk about McQuillan and Richter's parity theorem for complete and complete bipartite graphs as presented in their 2010 paper.

Monday, March 10, 2014

SPRING BREAK — no seminar this week.

Monday, March 3, 2014

Title: Ternary Distributive Algebraic Structures
Speaker: Matthew Green
Time: 2:00pm‐3:00pm
Place: CMC 108

Abstract

We introduce a notion of ternary distributive algebraic structures, give examples and relate it to the notion of a quandle. Classification is given for low order structures of this type. Constructions of such structures from ternary Lie algebras is also discussed. If time permits we will also mention a cohomology theory that is analogous to Hochschild cohomology.

Monday, February 24, 2014

Title: Retinal Neural Networks and Discrete Models of Information Flow
Speaker: Apurva Bhatty
Time: 2:00pm‐3:00pm
Place: CMC 108

Abstract

The human retina is the sensory input system for human vision. It does not simply transduce light into a neural code; the retina also performs local information processing which carries out edge enhancement, local contrast enhancement, local signal compression, and compressed sensing prior to encoding the visual information for transfer to the brain for further processing and “perception”. I will review some neural network models of retinal signal processing and present a new neural network model which attempts to simulate some of the color processing capabilities of the human retina. The model shows a reasonable approximation of the color discrimination capabilities of human vision.

Monday, February 17, 2014

Title: From Mathematics to Sculpture
Speaker: George Hart, Stony Brook University
Time: 2:00pm‐3:00pm
Place: CMC 108

Abstract

George Hart will present and discuss examples of his mathematically informed sculptures, which generally apply computer technology in their design and/or fabrication. These include works made of metal, wood, plastic, or found objects, and often use laser-cutting, plasma-cutting or 3D-printing technologies in their realization. Mathematical and computer science aspects of these designs and their underlying foundations will be discussed and a few short videos will be shown. See georgehart.com for examples of his work.

George Hart is a sculptor who demonstrates how mathematics is cool and creative in ways you might not have expected. Whether he is slicing a bagel into two linked halves or leading hundreds of participants in an intricate geometric sculpture barn raising, he always finds original ways to share the beauty of mathematical thinking. An interdepartmental research professor at Stony Brook University, he holds a B.S. in Mathematics and a Ph.D. in Electrical Engineering and Computer Science from MIT. Hart is an organizer of the annual Bridges Conference on mathematics and art and the editor for sculpture for the Journal of Mathematics and the Arts. His research explores innovative ways to use computer technology in the design and fabrication of his artwork, which has been exhibited widely around the world. Hart co-founded the Museum of Mathematics in New York City and developed its initial set of hands-on exhibits. He also makes videos that show the fun and creative sides of mathematics.

Monday, February 10, 2014

Title: Multiple Zeta Values and Their Higher Level Generalizations
Speaker: Jianqiang Zhao, Eckerd College
Time: 2:00pm‐3:00pm
Place: CMC 108

Abstract

The Riemann zeta function is one of the most fascinating objects in mathematics. It is a historical fact that Euler had studied this function as a real function long before Riemann. In particular he was able to evaluate the function at even numbers up to 26 using Bernoulli numbers. Furthermore, he considered the double zeta values defined by nested double sums. In the 1990s, more than 200 years after Euler, this subject was revitalized and generalized to multiple zeta values (MZVs) by Hoffman and Zagier independently, almost at the same time. Since then MZVs have appeared unexpectedly in many diverse areas of mathematics and physics. In this talk I will survey some of the more recent results on MZVs and then consider their generalizations to higher levels. At the end of the talk I will describe some current joint work with my collaborators concerning multiple Eisenstein series whose constant terms in their Fourier expansions are essentially MZVs. Most of this talk will be accessible to graduate students and advanced undergraduate math majors.

Monday, February 3, 2014

Title: Edge-maximality of power graphs of finite cyclic groups
Speaker: Brian Curtin
Time: 2:00pm‐3:00pm
Place: CMC 108

Abstract

The power graph of a finite group is the undirected graph whose vertices are the group elements and two elements are adjacent if one is a power of the other. We discuss our recent work showing that among all finite groups of any given order, the cyclic group of that order has the maximum number of edges in its power graph.

Monday, January 27, 2014

Title: The Descriptive Complexity of Counter Machine Languages
Speaker: Greg McColm
Time: 2:00pm‐3:00pm
Place: CMC 108

Abstract

One of the fundamental structures in Descriptive Complexity Theory is an inclusion hierarchy of queries based on complexity measures. After a brief look at such hierarchies, we will focus on a hierarchy of languages accepted by Pushdown Automata-like machines.

We consider three kinds of generalized machines: generalized pushdown automata, generalized deterministic pushdown automata, and a pushdown-automata-like machine with counters instead of stacks. An old result of Liu and Wiener implies that these machines produce articulating hierarchies of languages, but that the corresponding languages may be different. We conclude with a discussion of the kind of questions descriptive complexity theorists would ask of such hierarchies.

This is joint work with Nataša Jonoska and Milé Krajčevski.