### Summer Combo in Vermont - July 13th 2012

If you are interested in contributing a poster please send email to Jo Ellis-Monaghan (jellis-monaghan@smcvt.edu) with the author(s), title, and abstract for the poster by July 7th.

**Brita Brudvig, Ben Fish, Solomon Garber, Max Jeter, Liwen Song, and Bob McGrail**

**Title: **CSP and Connectedness: Constraints in Universal Algebra

**Abstract:** In the 1990's, Jeavons showed that every finite algebra corresponds to a class of constraint satisfaction problems (CSP). Vardi later conjectured that idempotent algebras exhibit P/NP dichotomy: Every non NP-complete algebra in this class must be tractable. Here we discuss how tractability corresponds to connectivity in Cayley graphs. In particular, we show that dichotomy in finite quandles follows from a very strong notion of connectivity. Moreover, P/NP membership is first-order axiomatizable in involutory quandles.

**Mary Falcigno and Katelyn Heath, Saint Michael's College**

**Title:** Tiling and Threading of Polyhedra

**Abstract:** We model the DNA self-assembly techniques of tiling and threading to build the 3-arm polytopes that are not found in the octet-truss using DNA. We first find the tile types necessary to build the structures using branched junction molecules. We then create threading designs to assemble these polyhedron using DNA scaffolding strands . Once built, these nanostructures can be used in biomolecular computing, drug delivery, electronics, and nanotechnology. Our methods and designs aim to minimize the time, resources, and cost of creating these structures with DNA.

**Morgan R. Frank, Jeff H. Dinitz, The University of Vermont
**

**Title:** Enumerating Costas Latin Squares

**Abstract:** A Costas array is an nxn matrix filled with zeros except for exactly a single one in every row and every column so that all of the n(n-1)/2 displacement vectors between each pair of ones are distinct. A Costas latin square is a join of n mutually disjoint Costas arrays. In an effort to add to the characterization of all Costas latin squares up to order 29, we determine the maximum number of disjoint Costas arrays of orders n less than or equal to 29. We also search for maximal disjoint Costas arrays of orders n less than or equal to 29. Our results suggest future work towards a generator of Costas Latin Squares and a similar analyses for orders greater than 29.

**Tyler Hotte and Miranda LaRoque, Saint Michael's College**

**Title:** Designs for Self-Assembling Cubic Lattices

**Abstract:** We are using the Watson-Crick properties of DNA and the principles of graph theory to construct designs for self-assembling cubic lattices. Through this project, our objective is to find a design for the cubic lattice that can be expanded indefinitely and systematically in order for a scaffolding strand of DNA to run through the design. Once an optimal design is discovered, we thread the cube in a way that minimizes the number of different vertex configurations in the structure.

**Abigail Ruiz, John Brown, Devlin Mallory, and Christino Tamon**

**Title: **Perfect Signed Transfer on Signed Graphs

**Eric Sherman and Saja Willard, Saint Michael's College**

**Title:** DNA Polyhedrons

**Abstract**: We use the Watson-Crick properties of DNA in combination with graph theory to prove that a self-assembling tetrahedron, octahedron, and cuboctahedron may be constructed out of linear, scaffolding strands of DNA. To do that, we find an optimal threading of the polyhedra using the scaffolding strand and then find the minimum number of vertex configurations required for the construct. We also find geometric tiles for each shape to determine how the construct can connect to similar constructs (*e.g.* how a tetrahedron can connect to another tetrahedron).