Summer Combo in Vermont
Friday, July 25, 2008
All talks will be held in Jeanmarie 380 on the Saint Michael's College campus.
Plan on roughly 20 minute talks with 10 minutes for questions and transitions.
Time of Talk / Presenter / Title10:00 / Jeff Dinitz / Orthogonal rectangles
10:30 / Iain Moffatt / On generalized duality of embedded graphs
11:00 / John Schmitt / Sum degree of no class
11:30 / Greta Pangborn / Minimal Tile and Bond-Edge Types for Self-Assembling DNA Graphs
12:00 / Lunch
1:30 / Tom Zaslavsky / Three Conferences on Three Continents
2:00 / Vince Vatter / On points drawn from a circle
2:30 / Melanie Brown / Embeddings of Steiner Triple Systems of Order 9 with Regular Bipartite Duals
3:00 / Break
3:30 / Seth Chaiken / Tutte Functions, Determinants and Electrical Resistance
4:00 / Jo Ellis-Monaghan / Digraph polynomials
4:30 / Dan Archdeacon / Stamp foldings, meanders, and their relatives
5:00 / Rebecca Smith / Wreath-closed pattern classes
Jeff
Title: Orthogonal rectangles
Abstract:None yet, but sure to be scintillating…
Iain
Title:On generalized duality of embedded graphs
Abstract:In order to relate various ribbon graph models for knots, Sergei Chmutov recently introduced a generalized duality for embedded graphs. In some sense, generalised duality is duality with respect to a subset of edges.In contrast with the usual duality where an embedded graph andits dual are both lie in the same surface,an embedded graph and its generalized duals may lie in different surfaces. I will talk about some aspect of generalized duality - I just don't know which aspect yet!
John
Title:Sum degree of no class
Abstract:Given a distribution D of pebbles on the vertices of graph, G, of order n, we saythat a pebbling move consists of removing two pebbles from a vertex and then placingone pebble on an adjacent vertex. The pebbling number of G, P(G), is the least integerm such that, regardless of how m pebbles are distributed on the vertices of G, aftera sequence of pebbling moves we can move a pebble to any vertex. It is easy to seethat P(G) > n − 1 since placing each of n − 1 pebbles on a distinct vertex leaves onevertex without a pebble and no pebbling moves possible. Graphs for which P(G) = nare known as Class 0 graphs. We give a degree sum condition, which is best possible,that gives a guarantee that G is Class 0.
Greta
Title:Minimal Tile and Bond-Edge Types for Self-Assembling DNA Graphs
Abstract:We examine a model for self-assembling DNA graphical complexes using tiles of branched DNA molecules with free ‘sticky ends’. We address determining the minimum number of tile and bond edge types necessary to create a given graph under three different scenarios: 1. Where the incidental creation of complexes of smaller size than the target graph is acceptable; 2. Where the incidental creation of complexes the same size as the target graph is acceptable, but not smaller complexes; 3. Where no complexes the same size or smaller than the target graph are acceptable. In each of these cases, we find bounds for the minimum and maximum number of tile and edge types that must be designed and give specific minimum values for common graph classes (complete, bipartite, trees, regular, etc.). For these classes of graphs, we provide either explicit descriptions of the set of tiles achieving the minimum number of tile and bond edge types, or efficient algorithms for generating the desired set.
Tom
Title:Three Conferences on Three Continents
Abstract:Zaslavsky reports on what little he remembers about the healthy state of matroids in Louisiana, differential geometry and PDEs in Ukraine, and combinatorics in India, from the many conferences taken in while spreading signed graphs far and wide across the globe. (Be it said: during a very atypical phase of his life.)
Vince
Title:On points drawn from a circle
Abstract:(Joint with Steve Waton.) Choose n points from the unit circle, no two with the same x- or y-coordinate. Label these points 1 to n by height, reading bottom to top, and record these labels reading left to right. This operation produces a permutation. We characterize and enumerate the permutations that can be obtained in this manner.
Melanie
Title:Embeddings of Steiner Triple Systems of Order 9 with Regular Bipartite Duals
Abstract:When first studying surface embeddings of graphs, a common initial example is atriangulation of K7 on the torus where the faces are two-colorable. By considering eachtriangular face as a triple, we can view this as an embedding of two Steiner Triple Systemsof order 7, abbreviated STS(7), with a bipartite dual. We call such an embedding abiembedding. In this talk, we will explore biembeddings of STS(9)s. In particular, we willexamine families of block-disjoint STS(9)s that pairwise biembed. We will also explorethe underlying automorphisms and affine geometry.
Seth
Title:Tutte Functions, Determinants and Electrical Resistance
Abstract:To start, equivalent resistance of a network is the ratioof two weighted spanning tree counts. The underlying theoryleads us to combine some generalizations and variations ofTutte decomposition of graphs and the Tutte polynomial.The result is Tutte-like function with values in anexterior algebra, which is anti-commutative. The valuesgeneralize resistance and spanning tree enumeration; theypertain to distinguished edges for which the Tutte decompositionis not done. A form of addition new to Tutte functionsis used which involves a common extensor factor derived fromcontracting one element in both a graphic oriented matroidand its dual.
Results include generalizations of the matrix tree theoremwhich when combined with determinental identities yieldan identity that proves Rayleigh's electrical networkmonotonicity principle.
Jo
Title:Digraph polynomials
Abstract:We look at a ‘Tutte like’ polynomial for digraphs developed by Chung and Graham (with further elucidation by Chow and by D’Anona and Munarini). We realize it as a special case of a weighted transition polynomial, recognizing the ‘contraction’ as simply linked transitions.
Dan
Title:Stamp foldings, meanders, and their relatives
Abstract:Consider a string of n stamps. A folding is exactly what the name suggests: bending the stamps at their joints so that the result is a stack of stamps. A meander is curved line which crosses a fixed infinite planar line, say the x-axis, n times. We examine some recent results on the number of foldings, the number of meanders, and numbers associated with their variations.
Rebecca
Title:Wreath-closed pattern classes
Abstract:(see PDF)