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)

Speakers:

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 mathdept@bard.edu.

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, rose@bard.edu, 845-758-7362

Supported by Bard College and the National Security Agency.

For more information, contact either rose@bard.edu or mathdept@bard.edu

------------------------------------------------------------

Program

9:30

Continental Breakfast and Welcome

10:15

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.

11:15

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.

12:15

Lunch in Manor Cafe

1:00

(Optional) Tour of the Frank Gehry designed Performing Arts Center

2:00

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.

3:00

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.

4:00

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.

------------------------------------------------------------