Discrete Mathematics Day, Fall 2004
Bard College, Annandale-on-Hudson, NY
Saturday, October 9th, 2004
Olin Language Center, Room 115
9:30am - 5:00pm (first talk at 10:15)
Natalie Priebe Frank (Vassar College) : An Introduction to Substitution Tilings and their Graphs
Robert McGrail (Bard College): Sorting the Sortable from the Unsortable
Rosa Orellano (Dartmouth College): Kronecker products of the symmetric group and partition algebras
Ricky Pollack (NYU-Courant Institute): A New Methodology in Geometric Transversal Theory
Marjorie Senechal (Smith College): Quasicrystals and the Golden Rhombohedra
Lunch will be provided for all participants. There is no registration
fee, but pregistration is recommended so we can have a head count for
lunch. Also, students, post-docs and recent PhD's can apply for travel
funds to attend the conference. To preregister and/or apply for travel
funds, please send email to email@example.com.
Directions/Lodging information: http://www.bard.edu/about/location/
Note: This is peak fall foliage time, so you may want to make lodging reservations soon.
Local Organizer: Lauren Rose, firstname.lastname@example.org, 845-758-7362
Supported by Bard College and the National Security Agency.
For more information, contact either email@example.com or firstname.lastname@example.org
Continental Breakfast and Welcome
Robert McGrail (Bard College)
Sorting the Sortable from the Unsortable
We consider a problem that stems from a reasonably simple scoring system. The structure of this problem is somewhat similar to the sorting of numbers as well as greedy approaches to the knapsack problem. Since the former problem (sorting) is solvable but the latter (knapsack via greedy algorithm) is not, an investigation into the solvability or our scoring problem is warranted. This talk settles this matter, yet raises other interesting mathematical questions.
Marjorie Senechal (Smith College)
Quasicrystals and the Golden Rhombohedra
Unreasonably, perhaps, the key geometric tools lay ready and waiting, but the discovery of quasicrystals in 1984 generated a veritable landslide of new research in the mathematics of aperiodic order. We know far more today than we did then, but important questions, especially in 3-space, remain open. In this talk I'll try to justify these statements; in particular, I will review the first-ever set of three dimensional aperiodic tiles, due to Robert Ammann, and state unsolved problems they still pose.
Lunch in Manor Cafe
(Optional) Tour of the Frank Gehry designed Performing Arts Center
Rosa Orellana (Dartmouth College)
Kronecker products of the symmetric group and partition algebras
In this talk I will discuss some simple combinatorial rules for decomposing Kronecker products of the symmetric group and other wreath products.
I will then show how they apply for the study of partition centralizer algebras.
Ricky Pollack (NYU-Courant Institute)
A New Methodology in Geometric Transversal Theory
We (in joint work with J. E. Goodman) describe a new encoding of a family of mutually disjoint compact convex sets that captures many of its combinatorial properties and use it to give a new proof of the Edelsbrunner-Sharir theorem that a collection of n mutually disjoint compact convex sets in the plane cannot be met by straight lines in more than 2n-2 combinatorially distinct ways. The encoding generalizes our encoding of planar point configurations by "allowable sequences" of permutations. Since it applies as well to a collection of compact connected sets with a specified pseudoline arrangement A of separators and double tangents the result extends the Edelsbrunner-Sharir theorem to the case of geometric permutations induced by pseudoline transversals compatible with A.
Natalie Priebe Frank (Vassar College)
An Introduction to Substitution Tilings and their Graphs
This talk will center around ways to construct infinite tilings of Euclidean space using a few different methods of ``substitution''. The most well-studied method is purely geometric and produces self-similar tilings, of which the famed Penrose tiling is an example. From a combinatorial perspective, tilings have a natural graph structure and can be thought of as a way to discretize space. Defining substitutions for tilings based solely on their combinatorial structure is difficult, and we will discuss some attempts to do this and the examples that motivate them. We hope to touch lightly upon how the tools from fields such as geometry, combinatorics, topology, dynamical systems, computer science, and algebraic number theory are brought to bear on the study of substitution tilings.