SMC/UVM Joint  Combinatorics Seminar, Fall 2010-Spring 2011.

(Note:  If you are on the announcement distribution list, and wish to be removed, or if you or someone you know would like to be added, please contact the organizers at: jellis-monaghan@smcvt.edu or dan.archdeacon@uvm.edu).

Overview

For many years the Math and CS departments at UVM and SMC have conducted weekly or biweekly discrete math/combinatorics/computer science seminars, with the location alternating campuses. In addition to traditional talks in theoretical combinatorics, there has also been a focus on the applications of combinatorics.  Our goal is to bring together academic and industry researchers for a productive exchange of the theory and applications of combinatorics.  This fall's seminar series will continue and build on the foundations laid in the previous semesters.

Examples of areas of application in computer science include data mining, storage in disk arrays, the design of parallel algorithms, software testing, database formatting, file organization, the analysis of algorithms, the design of networks, and interconnection strategies for networks.  Applications in information theory include wireless networking (the design of radio and satellite networks), internet communication protocols, signal processing, timing analysis and multiaccess communications. Combinatorial techniques are also used to address problems involving scheduling, packing, data compression, and book-width and fault-tolerant processing.  In molecular biology/biotechnology, applications include mapping genomes, forming the clone libraries, and designing chips for DNA probes.  In the past year and a half, new applications have even come out of Wall Street; (t,m,s)-nets are being used in numerical integration problems in financial mathematics.

A wide range of combinatorial techniques and theory is available for such applications.  In recent years a great deal of work has been done on developing new constructions, and a powerful theory of combinatorial constructions is emerging.  These applications come at a time when the power of combinatorial constructions combined with computational methods is beginning to be fully realized.  The problems appearing in these applications are providing us with new and challenging existence questions as well as surprising applications of familiar and long studied combinatorial techniques.

Participating

These seminars are open to the public.  No registration or fees are required to attend. 

Both industry and academic users of combinatorial techniques are invited to  share their own particular interests by conducting one of the seminars.  If you have an industry problem or other application that you are working with, this is an opportunity to present it to group of people who may be able to offer some approaches to it using newly developed techniques.  If you are a mathematician or computer scientist, this is a chance to hear about interesting problems and to share your techniques with people who might have a real need for them.  

The format of the seminars may be presentations, workshops, background followed by discussion, or even brain-storming sessions, at the discretion of the individual speakers.  If you are interested in conducting a session, please contact the organizers at jellis-monaghan@smcvt.edu or dan.archdeacon@uvm.edu  with a brief description of what you would like to talk about.

Schedule and Abstracts

The seminars generally will occur every other week, mid-afternoon on Monday, Wednesday or Friday, depending on the speaker's schedule.  Check specific abstracts for details.

Links to on-line slides and other resources from the various talks (if available) are provided at the end of each abstract.

[Fall 2001 Abstracts]  [Spring 2001 Abstracts] [Spring 2002 Abstracts] [Fall 2003 - Spring 2004 Abstracts]  [Fall 2004-Spring 2005 Abstracts] [Fall 2005-Spring 2006 Abstracts]  [Fall 2006-Spring 2007 Abstracts] [Fall 2007-Spring-Summer 2008 Abstracts] [Fall 2008-Spring-Summer 2009 Abstracts], [Fall 2009-Spring-Summer 2010 Abstracts]

Date: Wednesday, April 27, 2011.

Time:  4:00-4:50  pm

Location: Math conference room, Lord House, 16 Colchester Ave, UVM Campus

Title: Steiner triple systems, pinched surfaces, and complete multigraphs

Speaker: Dan Archdeacon, UVM

Abstract:

It all starts with K_7 on the torus, where we can 2-color the faces so that the triangles in each color class form a Fano plane. We call this a biembedding of two Fano planes (the Steiner triple system, or STS, on  7 points). What if we want to embed more than two STS's at the same time? What if we allow the surfaces to have pinch points?

We present a plethora of examples and a profusion of techniques leading to some surprisingly general theorems.

Date: Wednesday, April 13, 2011.

Time:  4:10-5:00  pm

Location: Jeanmarie 375, SMC Campus

Title: Fighting Fires on Flat Terrains

Speaker: Amir Barghi, Dartmouth College

Abstract:

Abstract: In the Firefighter Problem, a fire starts at a vertex of a graph, and in discrete time intervals, it spreads from burned vertices to their neighbors unless they are protected by one of the $f$ firefighters that are deployed every turn. Once burned or protected, a vertex remains in that state. This process terminates when the fire can not spread any longer. In the case of finite graphs, firefighters wish to minimize the damage or the time that the fire rages. When a fire starts in a locally-finite infinite graph, the key question is whether the fire can be stopped.

In this talk, we will discuss three different models for how the vertices of an infinite graph are distributed on the Euclidean plane. All these models have a geometric aspect: in the first two models, random and extremal geometric graphs, the geometric aspect is due to the adjacency criterion, and in the third model, plane-like graphs, it is due to the specific representation of an infinite planar graph on the Euclidean plane.

This is a joint work with Peter Winkler.

NOTE: Slightly later time than usual!

Date: Wednesday, March 16, 2011.

Time:  4:00-4:50  pm

Location: Math conference room, Lord House, 16 Colchester Ave, UVM Campus

Title: Graph Polynomials and Khovanov Homology

Speaker: Iain Moffatt, University of South Alabama

Abstract:  

Motivated by Khovanov homology and relations between the Jones polynomial and graph polynomials, we construct a homology theory for embedded graphs from which the chromatic polynomial can be recovered as the Euler characteristic. For plane graphs, we show that our chromatic homology can be recovered from the Khovanov homology of an associated link. We apply this connection with Khovanov homology to show that the torsion-free part of our chromatic homology is independent of the choice of planar embedding of a graph.

We extend our construction and categorify Bollobas and Riordan's ribbon graph polynomial (a generalization of the Tutte polynomial to embedded graphs). We prove that both our chromatic homology and the Khovanov homology of an associated link can be recovered from this categorification.

This is joint work with Martin Loebl.

Date: Wednesday, March 2, 2011.

Time:  4:00-4:50  pm

Location: Math conference room, Lord House, 16 Colchester Ave, UVM Campus

Title: Geometric drawings with few edge-lengths

Speaker: Dan Archdeacon, UVM

Abstract:

 You are trying to draw a graph and your objective is to have most edges of roughly the same length. What's the best you can achieve for the ratio longest-edge:shortest-edge? While this ratio is unbounded in general, it is bounded for bipartite graphs and for outer-planar graphs.

I'll discuss this and similar topics regarding optimal graph drawings.

Date: Wednesday, February 9, 2011.

Time:  4:00-4:50  pm

Location: Jeanmarie 380, Saint Michael's College Campus

Title: Separable permutations and Greene's Theorem

Speaker: Greg Warrington, UVM

Abstract:

Given a permutation, what is the maximum length of an increasing subsequence?  Or, more generally, what is the maximum sum-of-lengths of k disjoint increasing subsequences?  Greene's Theorem answers this general question in terms of the "shape" associated to the permutation under the Robinson-Schensted correspondence.  But it doesn't tell you the actual lengths of each of the k subsequences.  In joint work with A. Crites (U. Washington) and G. Panova (Harvard U.), we show that the shape gives you these individual lengths when your permutation is "separable."  I will present an application of this result to shortest containing supersequences.

Date: Wednesday, January 26, 2011.

Time:  4:00-4:50  pm

Location: Math conference room, Lord House, 16 Colchester Ave, UVM Campus

Title: Trinity symmetry and regular maps in kaleidoscopes

Speaker: Dan Archdeacon, UVM

Abstract:

Symmetric objects such as the Platonic solids are very beautiful. Is it possible for a polyhedron to have even more symmetry than the Platonic solids? Yes: there are several other symmetries involving geometric duality, Petrie polygons, and various mirror images suggestive of a kaleidoscope.

We present constructions of polyhedra that in a sense possess the highest possible amount of symmetry.

Dates: Wednesday, December 1, 2010.

Time:  4:00-4:50  pm

Location: Jeanmarie 380, Saint Michael's College Campus

Title:  Random Walks and the Gittins Index

Speaker:  Peter Winkler, Dartmouth

   Suppose there are two or more tokens at vertices of some

fixed connected graph.  Each token will, if you prod it, step

to a random neighbor.  You wish to get a token to some specified

target vertex as fast as you can.

   If you have to pick one token and stick with it, the problem

is easy: you compute the expected "hitting time" to the target

for each token, and choose the one that minimizes this quantity.

But if you're allowed to change your mind at any time, the

situation changes.

   It turns out that there's still a simple way to play this game

optimally, based on a variation of a concept called the "Gittins

index."  We'll present our adaptation of a fabulous proof, due to

Richard Weber, that this really works.  (Joint work with Ioana

Dumitriu and Prasad Tetali).

Date: TBA.

Time:  4:00-4:50  pm

Location: Math conference room, Lord House, 16 Colchester Ave, UVM Campus

Title: Trinity symmetry and kaleidoscopic maps

Speaker: Dan Archdeacon, UVM

Abstract:

The Platonic solids have a very rich symmetric group. But exactly how

far can we, and should we, extend the concept of symmetry for other polyhedra?

We give several such extensions and a construction of polyhedra with a truly

amazing number of symmetries. This is joint work with J. Siran and M. Conder.

Date: Wednesday, November 10, 2010.

Time:  4:00-4:50  pm

Location: Jeanmarie 380, Saint Michael's College Campus

Title: Constructions for Retransmission Permutation Arrays

Speaker: Jeff Dinitz, UVM

Abstract:

Li, Liu, Tan, Viswanathan, and Yang  introduced a technique for resolving overlapping channel transmissions that used an interesting new type of combinatorial structure. In connection with this problem, they provided an example of a 4 x4 array having certain desirable properties.

We define a class of combinatorial structures, which we term  "retransmission permutation arrays", that generalize the example that Li  et al. provided. We show that these arrays exist for all possible orders. We also define some extensions having additional properties, for which we provide some partial results.

Date: Wednesday, October 27, 2010.

Time:  4:00-4:50  pm

Location: Jeanmarie 380, Saint Michael's College Campus

Title: On the size and structure of graphs with a constant number of 1-factors

Speaker: John Schmitt, Middlebury College

Abstract: We investigate the maximum number of edges in a graph with a prescribed number of 1-factors.  We also examine the structure of such extremal graphs.  Several open problems will be given.

Date: Friday, October 22, 2010.

Time:  2:00-2:50  pm

Location: Saint Edmunds 102, Saint Michael's College Campus

Title: Graphical Models of Crystals

Speaker: Gregory McColm,  University of South Florida

Abstract:

The atomic or molecular structure of a crystal can be modeled by a periodic graph, i.e., a graph whose vertices are points in Euclidean 3-space, such that three translations by linearly independent vectors induce automorphisms of the graph.  Such graphs and similar combinatorial structures have been used to model crystals since the Seventeenth century, although it has been only since the 1980s that crystallographers have tried to use such graphs as designs for novel crystals.  This will be a brief introduction to a revived and growing field of applied geometry.

Date: Wednesday, October 13, 2010.

Time:  4:00-4:50  pm

Location: Math Conference Room, Lord House, 16 Colchester Ave, UVM Campus

Title: Representating Graphs in Steiner Triple Systems

Speaker: Dan Archdeacon, UMV

Abstract:

A graph is a set of vertices and a collection of edges, each edge being a pair of vertices. A Steiner triple system (STS) is a set of points and a collection of blocks, each block being a triple of points, such that every pair of points is in a unique block.

 We study representing graphs in STS: injectively mapping vertices of a graph to points of an STS such that no two edges map to the same block. We focus first on graphs that can be represented in the Fano plane. Some results are given about representing all graphs of a given order before turning attention to representing graphs of a bounded degree. We close with some interesting observations about representing graphs of small size, called configurations in STS.

Date: Wednesday, September 8, 2010.

Time:  3:00-3:50  pm

Location: Jeanmarie 366, Saint Michael's College Campus

Title: The Tutte/Potts connection in the presence of an external field.

Speaker: Jo Ellis-Monaghan, Saint Michael's College

Abstract:

The classical relationship between the Tutte polynomial of graph theory and the Potts model of statistical mechanics has resulted in valuable interactions between the disciplines. Unfortunately, it does not include the external magnetic fields that appear in most Potts model applications. Here we define the V -polynomial, which lifts the classical relationship between the Tutte polynomial and the zero field Potts model to encompass external magnetic fields. The V -polynomial generalizes Nobel and Welsh’s W-polynomial, which extends the Tutte polynomial by incorporating vertex weights and adapting contraction to accommodate them. We prove that the variable field Potts model partition function (with its many specializations) is an evaluation of the V -polynomial, and hence a polynomial with deletion-contraction reduction and Fortuin-Kasteleyn type representation. This unifies an important segment of Potts model theory and brings previously successful combinatorial machinery, including complexity results, to bear on a wider range of statistical mechanics models.

No background in statistical mechanics is necessary: the talk will begin with an introduction to the Potts model and its properties as well as a quick review of the Tutte polynomial.

This is joint work with Iain Moffatt.

Directions and Parking
 

SMC

Directions to SMC:  From major cities, see SMC Directions Once on Interstate 89 see below:

Main Entrance:

Bear right off of exit 15, Interstate 89.  Stay in right lane and follow Route 15 through two lights.  After second light bear right into jug handle and go through intersection to campus.  The Office of Admission is located in the Hoehl Welcome Center on the left, with visitor's parking at the entrance.  (Coming from IBM on Route 15, turn right at the lights across from the jughandle)
 

South Entrance:

Bear right off of exit 15, Interstate 89 and get into left lane.  At first set of lights, take left into parking lot.  McCarthy Arts Center is on your right.  Ross Sports Center is on left at back of parking lot.  Visitor parking is marked in this lot (stay straight as you enter, and look to your left).  (Coming from IBM on Route 15, turn right at the lights by Purple Knight's Pizza.)

Maps: There are campus maps on the SMC website at SMC Campus Map 

Most talks are likely to be held in Jeanmarie, St. Edmunds Hall, or the Science building.

UVM
Picture: There is a picture of the Math Department building (Lord House, 16 Colchester Avenue) at http://www.emba.uvm.edu/math .

The seminars are often held here in the conference room on the first floor.

Parking: The easiest place to park is probably the Visitor Lot at Waterman.  It is located on College Street, across the street from the Waterman administration building.  Parking is paid, 75 cents/hour, 7 a.m. to 5 p.m., Monday through Friday, and free after 5 p.m. and on weekends and holidays.

Directions to the Vistors' lot:
From I-89: Take Exit 14W into Burlington. This puts you heading west on Williston Road going up hill.  Turn right onto North Prospect Street. Take first left onto College Street. Take first left into visitor parking lot. 

Heading north from Route 7: Follow Shelburne Road/Route 7 into Burlington. At rotary, bear right. Approximately 1/4 mile to first four-way stop, turn right onto Cliff Street. Head uphill to end of Cliff; take left onto South Prospect Street. Cross Main Street/Route 2. Take first left onto College Street. Take first left into visitor parking lot.

Maps: There are campus maps on the UVM website, and the direct URAL is:  http://www.uvm.edu/map  (the Math Department is 16 Colchester, the visitor lot is across College street from Waterman building).
 

IBM--Williston Site

From Interstate 89:  Coming from the north or south, take exit 12. From the north, turn left off exit ramp; from the south, turn right onto Route 2A. Follow the road past three traffic lights, over a bridge and up a hill. Watch for (and turn into) IBM entrance signs on the right. 

For the WILLISTON LOBBY:  After turning into IBM, go straight.  Pass the “Main Lobby” signs.  Go around the S-curve and over bridge. Take third left-hand turn into the visitor parking lot.

Map: Here is a map of the area near IBM.  The Williston site is the dark rectangle just to the south of the rectangle marked IBM.