title: Two lower bounds for self-assemblies at temperature 1.
abstract: Using the Tile Assembly Model proposed by Rothemund and Winfree, we give two lower bounds on the minimum number of tile types needed to uniquely assemble a shape at temperature 1 under a natural assumption that there are no binding domain mismatches (any two adjacent tiles either form a bond or else both touching sides of the tiles are without glues). Rothemund and Winfree showed that uniquely assembling a full N x N square (a square where there is a bond between any two adjacent tiles) at temperature 1 requires N(2) distinct tile types, and conjectured that the minimum number of tile types needed to self-assemble an N x N square (not a full square) is 2N - 1. Our lower bounds imply that a tile system that uniquely assembles an N x N square without binding domains mismatches, requires at least 2N - 1 tile types.
authors.affiliation: Department of Computer Science, University of British Columbia, Vancouver, BC, Canada. jmanuch@sfu.ca
authors.forename: Ján
authors.initials: J
authors.lastname: Manuch
authors.forename: Ladislav
authors.initials: L
authors.lastname: Stacho
authors.forename: Christine
authors.initials: C
authors.lastname: Stoll
mesh_terms: D004247:DNA / Q000737:chemistry; D008958:Models, Molecular; D013696:Temperature
chemical_list: D004247:DNA