Combinatorics Seminars Academic year 2010-2011 |
SMC Math Dept. | SMC Home | Jo Ellis-Monaghan Home | |
UVM Math Dept. | UVM CS Dept. | UVM Home | Dan Archdeacon Home |
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).
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.
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.
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.
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.
Date |
Speaker |
Title |
9/8/2010 | Jo Ellis-Monaghan | The Tutte/Potts connection in the presence of an external field. |
10/1/2010 | Tom Hull | Origami math is in creasing |
10/13/2010 | Dan Archdeacon |
Representing Graphs in Steiner Triple Systems |
10/15/2010 | Gregory McColm | Graphical models of crystal |
10/27/2010 | John Schmitt | On the size and structure of graphs with a constant number of 1-factors |
11/10/2010 | Jeff Dinitz | Constructions for Retransmission Permutation Arrays |
11/17/2010 (rescheduled TBA) | Dan Archdeacon | Trinity symmetry and kaleidoscopic maps |
12/1/2010 | Peter Winkler | Random Walks and the Gittins Index |
1/26/2011 | Dan Archdeacon | Trinity symmetry and regular maps in kaleidoscopes |
2/9/2011 | Greg Warrington | Separable permutations and Greene's Theorem |
3/2/2011 | Dan Archdeacon | Geometric drawings with few edge-lengths |
3/16/2011 | Iain Moffatt | Graph Polynomials and Khovanov Homology |
3/23/2011 | Debra Boutin | Graphs and Symmetry |
4/13/2011 | Amir Barghi | Fighting Fires on Flat Terrains |
4/27/2011 | Dan Archdeacon | Steiner triple systems, pinched surfaces, and complete multigraphs |
[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 to SMC: From major cities, see SMC
Directions
Once on Interstate 89 see below:
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).
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.