# Research

## Discrete Mathematics

### Monday, April 23, 2012

Title: Looking at Kolam Designs
Speaker: Joy D'Andrea
Time: 3:05pm‐3:55pm
Place: PHY 108

#### Abstract

Kolam is a form of painting that is drawn using rice powder. A kolam is a geometrical line drawing composed of curved loops, drawn around a grid pattern of dots. In South India, it is widely practiced by female Hindu family members in front of their homes. Kolam designs of South Indian folk art are treated as examples of two - dimensional picture languages. Some of the complicated kolam patterns are seen to be generable by context-free array grammars. In this talk, we will describe what a kolam is and we will use array grammars to generate our own kolams, where array grammars higher dimensional analogues of context free and context sensitive grammars.

### Monday, April 16, 2012

Title: Distinguishing Symmetry Types of Knots using Quandle Colorings
Speaker: W. Edwin Clark
Time: 3:05pm‐3:55pm
Place: PHY 108

#### Abstract

Here “knot” always means “prime, oriented knot”.

If $$Q$$ is a quandle and $$K$$ is a knot, let $$\langle Q,K\rangle$$ denote the number of colorings of $$K$$ by $$Q$$. This is known to be a knot invariant.

We say that $$Q$$ distinguishes knots $$K1$$ and $$K2$$ if $$\left\langle Q,K1\right\rangle\ !=\left\langle Q,K2\right\rangle$$. Here $$!=$$ means “not equal” for numbers, and below, means “not isotopic” for knots.

I report on the recent result by Tim Yeatman and me that all of the 2977 knots on at most 12 crossings given by braid representation at KnotInfo.com can be distinguished by a set of just 20 quandles.

Unfortunately this doesn't completely solve the problem. Each knot $$K$$, leads to three additional knots: $$r(K)$$, $$m(K)$$ and $$rm(K)$$ where $$r(K)$$ is $$K$$ with orientation reversed and $$m(K)$$ is the mirror image of $$K$$. And only one of these is given for each knot in the list of 2977 knots at KnotInfo.com.

For a knot $$K$$ there are five symmetry types: \begin{alignat*}{2} &K\text{ is chiral if } &\quad& K !=r(K)\text{, }K !=m(K)\text{, }K !=rm(K) \\ &K\text{ is fully amphichiral if } &\quad& K=r(K)\text{, }K=m(K)\text{, }K=rm(K) \\ &K\text{ is reversible if } &\quad& K=r(K)\text{, }K !=m(K)\text{, }K !=rm(K) \\ &K\text{ is negative amphichiral if } &\quad& K !=r(K)\text{, }K !=m(K)\text{, }K=rm(K) \\ &K\text{ is positive amphichiral if } &\quad& K !=r(K)\text{, }K=m(K)\text{, }K !=rm(K) \end{alignat*}

The number of knots of each type on at most 12 crossings is, respectively, 1319, 30, 1581, 47, and 1.

This extends the number of knots we'd like to distinguish from 2977 to 8562.

I will discuss the extent to which we can (and cannot) distinguish these 8562 knots using quandle coloring.

### Monday, April 9, 2012

Title: Formal Deformations of Lie algebras and Universal enveloping algebras
Speaker: Abdenacer Makhlouf, University of Haute Alsace
Mulhouse, France
Time: 3:05pm‐3:55pm
Place: PHY 108

#### Abstract

The aim of my talk is to give an introduction to Formal deformation Theory. I will show relationships between deformations of Lie algebras and deformations of their corresponding universal enveloping algebras. In particular I will discuss deformations of Universal enveloping algebras via linear Poisson structures.

### Monday, April 2, 2012

Title: Integration on Functions Defined by Finite Automata
Speaker: Tony Long
Time: 3:05pm‐3:55pm
Place: PHY 108

#### Abstract

We will consider functions defined by finite automata whose set of inputs is the set of digits used in representing numbers in radix $$r$$ notation for some integer $$r$$ greater than $$1$$, and we will introduce a method of calculating the Lebesgue integral for the functions defined by our automata. The Reisz Representation Theorem will provide some justification for our efforts. This is a continuation of work based on “Sets of Numbers Defined by Finite Automata” by J. Hartmanis and R. E. Stearns, along with guidance from Richard Stark.

### Monday, March 26, 2012

Title: LUB-Systems, Admissibility Systems, and LUB-Based Lattices
Speaker: Joseph Van Name
Time: 3:05pm‐3:55pm
Place: PHY 108

#### Abstract

LUB-systems, admissibility systems, and LUB-based lattices are all equivalent ways of formalizing the notion of a partially ordered set $$X$$ along with a collection of subsets of $$X$$ with least upper bounds that we want to consider. For example, in a join-semilattice, we consider only the least upper bounds of finitely many elements even though many other least upper bounds may exist. In a complete lattice, we consider all least upper bounds. In a directed complete partial order, we consider the least upper bounds of all directed sets. In fact, in some partially ordered sets, we do not consider any non-trivial least upper bounds.

### Monday, March 19, 2012

Title: Assembly Number and Loop Saturated Graphs
Speaker: Tilahun Muche
Time: 3:05pm‐3:55pm
Place: PHY 108

#### Abstract

An assembly graph $$G$$ is a finite connected graph where all vertices are rigid vertices of valency $$1$$ or $$4$$. The assembly number of $$G$$, denoted by $$\mathrm{An}(G)$$, is defined by $$\mathrm{An}(G)=\min\{k:\text{there exists a Hamiltonian set of polygonal paths }\{g_1,\dotsc,g_k\}\text{ in }G\}$$ where polygonal paths are paths that take $$90$$ degree turns at each vertex.

For a positive integer $$n$$, we define minimal realization number for $$n$$ to be $$R\min(n)=\min\{|G|:\mathrm{An}(G)=n\},$$ where $$|G|$$ is the number of $$4$$-valent vertices in $$G$$. A graph $$G$$ such that $$R\min(n)=|G|$$ is called a realization of $$R\min(n)$$. We denote by $$R\min(n)$$, the set of minimal realization graphs for some positive integer $$n$$. Each $$G$$ in $$R\min(n)$$ has the property that $$|G|\leq 3n-2$$ and $$R\min(n) < R\min(n+1)$$ for every natural number $$n$$.

The assembly graph, $$G$$, obtained from a given assembly graph $$G$$ by substituting every edge with a loop $$11$$, is called an interior loop-saturated graph. We prove that loop saturated assembly graphs achieve the bound of $$3n-2$$ and if a simple assembly graph has no loops then it is not in $$R\min(k)$$. These two facts support a conjecture that the set $$R\min(k)$$ consists of graphs constructed by loop saturation. More specifically, we conjecture that any graph obtained by loop saturation is a minimal realization graph and any minimal realization graph is obtained by loop saturation.

### Monday, March 5, 2012

Title: Reconstructing Shredded Documents by Edge-Matching of Tiles
Speaker: Apurva Bhatty
Time: 3:05pm‐3:55pm
Place: PHY 108

#### Abstract

Paper shredders disassemble a finite $$2$$-dimensional page into tiles with repeating identical (or almost identical) geometry. These pieces may be viewed as a jigsaw puzzle or an edge-matching tile puzzle. Reconstruction of the original document can be aided by the regularity of the $$2$$-d lattice defined by the center of the tiles (a finite subgraph of a periodic graph). We present a model of the shredding process and a new algorithm that speeds up the reconstruction, along with examples and code which were submitted to the DARPA Shredder Challenge. We also present a second algorithm which provides further speed-up of reassembly based upon explicit and implicit lattice points within the document and in printer codes.

### Monday, February 27, 2012

Title: On Algorithmic Packings of Hypergraphs
Speaker: Jill Dizona
Time: 3:05pm‐3:55pm
Place: PHY 108

#### Abstract

For $$k$$-graphs $$H,F_0$$, an $$F_0$$-packing of $$H$$ is a collection of pairwise edge-disjoint copies $$F$$ of $$F_0$$ which are subhypergraphs of $$H$$. Computing $$\nu_{F_0}(H)$$, the maximum size of an $$F_0$$-packing in $$H$$, is known to be an NP-hard problem (for most $$F_0$$). In my thesis we give a partial extension to hypergraphs of a result of Haxell and Rödl for graphs. In particular, when $$F_0$$ is a linear $$k$$-graph, an $$F_0$$-packing in $$H$$ of size $$\nu_{F_0}(H)-o\left(|V(H)|^k\right)$$ may be constructed in time polynomial in $$|V(H)|$$. In this talk, we introduce the tools used in our proof which is based on lemmas concerning hypergraph regularity and fractional packings. This is joint work with Brendan Nagle.

### Monday, February 20, 2012

Title: Fibonacci Vectors and Lucas' Hyperbolas
Speaker: Brian Curtin
Time: 3:05pm‐3:55pm
Place: PHY 108

#### Abstract

We discuss some properties of vectors whose entries are consecutive Fibonacci numbers. Using a few facts from elementary linear algebra and calculus 3, we show such vectors lie on certain hyperbolas in higher dimension. This generalizes a famous result of Lucas.

### Monday, January 30, 2012

Title: Classifying Crystal Nets, Part II
Speaker: Greg McColm
Time: 3:05pm‐3:55pm
Place: PHY 108

### Monday, January 23, 2012

Title: Classifying Crystal Nets
Speaker: Greg McColm
Time: 3:05pm‐3:55pm
Place: PHY 108

#### Abstract

In crystal design, crystals are often characterized by a periodic graph representing their atomic or molecular structure. The criteria developed for classifying them are largely combinatorial or topological, and we focus on one classification criterion: isomorphism of the graphs. Adapting the notion of a “space” of polyhedra of a common skeleton, we find that given certain constraints, we obtain spaces of periodic graphs, and we ask how they could be mapped.