Combinatorics Seminars

Academic year 2006-2007

 

 

Overview Schedule and Abstracts Participating Directions and Parking

UVM    SMC    IBM

SMC Math Dept. 

SMC CS Dept. 

SMC Home  Jo Ellis-Monaghan Home
UVM Math Dept. UVM CS Dept. UVM Home Dan Archdeacon Home

 

SMC/UVM Joint  Combinatorics Seminar, Fall 2006-Spring 2007.

(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 have conducted weekly discrete math/combinatorics/computer science seminars.  These seminars are now held jointly with St. Michael's college, with the location alternating campuses. Recently, 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.

Date

Speaker

Title

10/05/06

Alan Ling

Asymptotic Existence of Resolvable Graph Designs 

10/26/06

Jo Ellis-Monaghan

An introduction to the Potts Model

11/9/06

Jeff Parker

Suffix Trees

11/30/06

Sergi Elizalde

A bijection between 2-triangulations and pairs of non-crossing Dyck paths

4/26/07

John Schmitt

Extremal Problems on Bipartite Graphs

5/2/07

John van Rees

Finding Transversals in a Rectangle

6/27/07

Peter Otto

The Random Cluster Model

6/28/07

Jeff Dinitz

The Hamilton-Waterloo problem: The case of triangle-factors and Hamilton cycles.

6/29/07

Tom Zaslavsky

Topological Hyperplanes

7/2/07

Tom Zaslavsky

Totally frustrated states:  A physics-like generalisation of graph colouring

7/3/07

Greta Pangborn

Unit Rectangle Visibility Graphs

7/5/07

Dan Archdeacon

My 4-color flu

7/6/07

Jo Ellis-Monaghan

Minimal Tile and Bond-Edge Types for Self-Assembling DNA Graphs

[Fall 2001 Abstracts]  [Spring 2001 Abstracts] [Spring 2002 Abstracts] [Fall 2003 - Spring 2004 Abstracts]  [Fall 2004-Spring 2005 Abstracts]

[Fall 2005-Spring 2006 Abstracts]

 

Date: Thursday, October 5,  2006

Time:  2:00-2:50  pm

Location: Math Department Conference Room, Lord House, UVM Campus

 

Title: Asymptotic Existence of Resolvable Graph Designs 

 

Speaker:  Alan Ling, UVM CS department

 

Abstract: 

 

Let v and g be integers with v > 0 and g non-negative, and let G be a fixed simple graph with n vertices, e edges, and degrees d_1, …, d_n.

 

 A graph design, GD(v,G,lambda),  is a collection A of graphs  isomorphic to G with vertices chosen from some set X with |X|=v,  such that every unordered pair of distinct points in X is an edge of  exactly  lambda elements of A.  A famous result of R.M. Wilson says that for a fixed G and lambda, there exists a GD(v,G,lambda) for all  sufficiently  large v satisfying certain necessary conditions.  Such a graph design  is resolvable, denoted RGD(v,G,lambda), if A can be  partitioned  into classes of graphs whose vertex sets partition X.  In this talk  I  will  outline a proof of the following asymptotic existence result for  resolvable  graph designs:  for any G and lambda, there exists v_0 such  that  for all v greater than or equal to v_0, an RGD(v,G,lambda) exists if and only if  n divides v and gamma divides lambda*(v-1), where gamma is the least  positive  integer with gamma*(1,n/2e) an element of span_Z {(d_i,1) : i=1,…,n}.

 

Date: Thursday, October 26,  2006

Time:  11:30 am -12:20 pm

Location: Jeanmarie 380, SMC campus

 

Title: The Potts/Tutte model and its applications

 

Speaker:  Jo Ellis-Monaghan, Mathematics Department, SMC

 

Abstract: 

 

This talk will provide a gentle introduction (with pictures) to the Ising and q-state Potts model partition functions of statistical mechanics.  These models play important roles in the theory of phase transitions and critical phenomena in physics, and have applications as widely varied as muscle cells, foam behaviors, and social demographics.  The Potts model is constructed on various lattices, and when these lattices are viewed as graphs (i.e. networks of nodes and edges), then, remarkably, the Potts model is also equivalent to one of the most renown graph invariants, the Tutte polynomial. Thus, the talk will also give a gentle introduction (with more pictures) to graph theory and the Tutte polynomial.  The Tutte polynomial is the universal object of its type, in that any invariant that obeys a certain deletion/contraction relation (or equivalently a particular state-model formulation), must be an evaluation of it.  The talk includes a (very) little history and some interesting properties of the Potts model partition function and Tutte polynomial, but the emphasis will be on how the Potts model and Tutte polynomial are related and how research into the one has informed the theory of the other, and vice versa.   The talk concludes with locations of zeros corresponding to phase transitions and computational complexity analysis, with perhaps a brief excursion into Monte Carlo simulations. 

 

(Note--due to heavy undergraduate participation, the talk was modified to an introduction to the Potts model:  Intro to Potts.pdf )

 

Date: Thursday, November 9,  2006

Time:  2:00 am -2:50 pm

Location: Farrell Room, St. Edmunds 315, SMC campus

 

Title: Suffix Trees

 

Speaker:  Jeff Parker, CS department, Merrimack College

 

Abstract: 

 

Suffix trees can be used to solve many natural problems quickly.  Not only do algorithms that use an existing tree run quickly, it is  possible to build a suffix tree in linear time.

The linear time construction has a reputation as being opaque.  In fact, there are three well known opaque constructions.  In this talk, we will introduce the suffix tree, give a few of it't many applications, and attempt to illuminate the construction. 

 

Date: Thursday, November 30,  2006

Time:  12:30-1:20 pm

Location: Math Department Conference Room, Lord House, UVM Campus

 

Title: A bijection between 2-triangulations and pairs of non-crossing Dyck paths

 

Speaker:  Sergi Elizalde, Department of Mathematics, Dartmouth College

 

Abstract: 

 

Triangulations of a convex polygon are known to be counted by the Catalan numbers. A natural generalization of a triangulation is a k-triangulation, which is defined to be a maximal set of diagonals so that no k+1 of them mutually cross in their interiors. It was proved by Jakob Jonsson that k-triangulations are enumerated by certain determinants of Catalan numbers, that are also known to count k-tuples of non-crossing Dyck paths.

 

There are several simple bijections between triangulations of a convex n-gon and Dyck paths. However, no bijective proof of Jonsson's result is known for general k. In this talk I will give a bijective proof for the case k=2, that is, I will present a bijection between 2-triangulations of a convex n-gon and pairs (P,Q) of Dyck paths of semilength n-4 so that P never goes below Q. The bijection is obtained by constructing isomorphic generating trees for the sets of 2-triangulations and pairs of non-crossing Dyck paths.

 

 

Date: Thursday, April 26,  2007

Time:  3:30-4:20 pm, refreshments at 3:15

Location: 203 Torrey, UVM Campus

 

Title: Extremal Problems on Bipartite Graphs

 

Speaker:  John Schmitt, Department of Mathematics, Middlebury College

 

Please see the poster: Combo_Seminar/Schmitt 4 26.pdf

 

 Date: Wednesday, May2,  2007

Time:  12:20-1:10 pm

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

 

Title: Finding Transversals in a Rectangle

 

Speaker:  John van Rees, CS department, University of Manitoba

 

Abstract:  Given an m x n rectangle (with m <=n) filled with integers, a transversal consists of a set of m cells with one from each row, and at most one from each column in which no two cells contain the same symbol.  In this talk we discuss bounds on the frequency of the symbols which will force the square to have a transversal. 

 

Date: Wednesday, June 27, 2007

Time:  11:00-11:50 a.m.

Location: Jeanmarie 290, SMC campus

 

Title: The Random Cluster Model

 

Speaker:  Peter Otto, Willamette University

 

Abstract:  In 1969 Kees Fortuin and Piet Kasteleyn introduced the random cluster model as a unification of two of the most famous models in statistical mechanics, namely, the bond percolation model and the Ising/Potts model.  Its connection to bond percolation  is that the random cluster model is also a stochastic geometry model that places the randomness on the {\it edges} of a graph.  On the other hand, the connection to the Potts model is that it incorporates the $q$ states that the {\it vertices} of the Potts models can randomly take on.  As a result, through the random cluster model, connectivity questions in the edge model can be related to questions of correlations in the corresponding vertex model.  In this talk, I'll introduce the general random cluster model and its coupling to the Ising/Potts model and then focus on the models defined on the complete graph to discuss the phase transition behavior of these models.

 

Date: Thursday, June 28, 2007

Time:  11:00-11:50 a.m.

Location: Jeanmarie 290, SMC campus

 

Title: The Hamilton-Waterloo problem: The case of triangle-factors and Hamilton

cycles.

 

Speaker:  Jeff Dinitz, University of Vermont

 

Abstract:  The Hamilton-Waterloo problem in the case of triangle-factors and

Hamilton cycles asks for a 2-factorization of Kn in which exactly r of

the 2-factors are triangle-factors and exactly s of the 2-factors are

Hamilton cycles. Necessarily n = 3 (mod 6) and r + s = (n − 1)/2.

The case of n = 9 (mod 18) was completely solved in 2004 by Horak,

Nedela and Rosa (except when s = 1). In that paper the authors also

solve the problem when n = 3 or 15 (mod 18) for the cases where

(n+3)/6  ≤  s  ≤  (n−1)/2. In addition, they give several infinite classes

when s = 1.

In this talk we discuss a solution to the problem in the case when

n = 3 (mod 18). We also discuss our solution to the problem when

s = 1.

 

Date: Friday, June 29, 2007

Time:  11:00-11:50 a.m.

Location: Jeanmarie 290, SMC campus

 

Title: Topological Hyperplanes

 

Speaker:  Tom Zaslavsky, SUNY Binghamton

 

Abstract:  A topological hyperplane (a 'topoplane') is a subspace H of R^d which is topologically like a true hyperplane.  An arrangement of topoplanes is a finite set A of topoplanes such that, for each pair H, H' that intersect, the intersection is a topoplane in H and in H'.  (Actually, this is a slight oversimplification.)  Therefore, when H and H' intersect, there are two possibilities: they cross, or they do not cross.

 

Main examples:  An arrangement of hyperplanes.  An arrangement of affine pseudohyperplanes (representing an affine oriented matroid).

 

Main Question:  Is the number of regions (connected components of the complement of the arrangement) given by the same formula as for an arrangement of hyperplanes?  The answer is 'yes' if every region is a topological ball.  Laura Anderson and I are (we believe) in the midst of proving that this is true.

 

Second Question:  How different is a topoplane arrangement A from an affine arrangement of pseudohyperplanes?  For example, is there a topoplane arrangement A' such that Union(A) = Union(A'), and in A' every pair of topoplanes that intersects crosses?  David Forge and I showed this 'ain't necessarily so'.

 

Date: Monday, July 2, 2007

Time:  11:00-11:50 a.m.

Location: Jeanmarie 380, SMC campus

 

Title: Totally frustrated states:  A physics-like generalisation of graph colouring

 

Speaker:  Tom Zaslavsky, SUNY Binghamton

 

Abstract:  When counting the proper colourisations of a graph, whose number is given by the chromatic polynomial, all one needs to know is the number of colours in the colour set; the nature of the individual colours is immaterial.   When colouring a gain graph, where the edges are labelled by elements of a group (called the gain group), that is no longer so.  In order for the concept of a proper colourisation to be meaningful the group must have a permutation action on the set of colours, and then the exact way the group acts is a crucial factor in counting proper colourations.

 

One reason to study gain graph colouring is that it generalises simple physical models of spin glasses like the Ising model, in which the edges are labelled from the sign group and there are two colours, and the Potts model, in which there are more colours.  Due to this connection we call the colours `spins' and the generalised proper colourisation a totally frustrated state.

 

The number of totally frustrated states is not related to a matroid invariant (as far as I know), except in ordinary graph colouring and a previously known gain-graphic generalisation, but it always satisfies a deletion-contraction law and it has a formula in terms of holonomy groups of subgraphs.

 

Date: Tuesday, July 3, 2007

Time:  11:00-11:50 a.m.

Location: Jeanmarie 380, SMC campus

 

Title: Unit Rectangle Visibility Graphs.

 

Speaker:  Greta Pangborn, Saint Michael's College

 

Abstract:  Over the past twenty years, rectangle visibility graphs have generated considerable interest, in part due to applicability to VLSI chip  design. Here we study unit rectangle visibility graphs, whose fixed  dimension restrictions more closely model gates and other circuit com-  ponents in computer chip applications. A graph G is a unit rectangle  visibility graph (URVG) if its vertices can be represented by closed  unit squares in the plane with sides parallel to the axes and pairwise  disjoint interiors, in such a way that two vertices are adjacent if and  only if there is a non-degenerate horizontal or vertical band of visibility  joining the two rectangles. Our results include necessary and sufficient  conditions for Kn, Km,n, and trees to be URVGs as well as a number  of general edge bounds. 

 

Date: Thursday, July 5, 2007

Time:  11:00-11:50 a.m.

Location: Jeanmarie 380, SMC campus

 

Title: My 4-color flu

 

Speaker:  Dan Archdeacon, University of Vermont

 

Abstract:  An early approach (and one which eventually worked) to the Four Color Problem was to try to recolor subgraphs by exchanging colors along Kempe chains.  Bill Tutte developed a method to formalize such recolorings. When I first learned of his method 15 years ago, I was fascinated and investigated it in some detail. In this talk I will discuss Tutte's application and my attempts to understand it.

 

Date: Friday, July 7, 2007

Time:  11:00-11:50 a.m.

Location: Jeanmarie 380, SMC campus

 

Title: Minimal Tile and Bond-Edge Types for Self-Assembling DNA Graphs

 

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

 

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 tiles 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 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 fastalgorithms for generating the desired set.

 

 

 

 

 

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.