Combinatorics Seminars Academic year 20062007 
SMC Math Dept.  SMC Home  Jo EllisMonaghan Home  
UVM Math Dept.  UVM CS Dept.  UVM Home  Dan Archdeacon Home 
SMC/UVM Joint Combinatorics Seminar, Fall 2006Spring 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: jellismonaghan@smcvt.edu or dan.archdeacon@uvm.edu).
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.
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 bookwidth and faulttolerant 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 brainstorming sessions, at the discretion of the individual
speakers. If you are interested in
conducting a session, please contact the organizers at
jellismonaghan@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, midafternoon on Monday, Wednesday or Friday, depending on the speaker's schedule. Check specific abstracts for details.
Links to online slides and other resources from the various talks (if available) are provided at the end of each abstract.
Date 
Speaker 
Title 
Alan Ling 
Asymptotic Existence of Resolvable Graph Designs 

Jo EllisMonaghan 
An introduction to the Potts Model 

Jeff Parker 
Suffix Trees 

Sergi Elizalde 
A bijection between 2triangulations and pairs of noncrossing Dyck paths 

John Schmitt 
Extremal Problems on Bipartite Graphs 

John van Rees 
Finding Transversals in a Rectangle 

Peter Otto 
The Random Cluster Model 

Jeff Dinitz 
The HamiltonWaterloo problem: The case of trianglefactors and Hamilton cycles. 

Tom Zaslavsky 
Topological Hyperplanes 

Tom Zaslavsky 
Totally frustrated states: A physicslike generalisation of graph colouring 

Greta Pangborn 
Unit Rectangle Visibility Graphs 

Dan Archdeacon 
My 4color flu 

Jo EllisMonaghan 
Minimal Tile and BondEdge Types for SelfAssembling DNA Graphs 
[Fall 2001 Abstracts] [Spring 2001 Abstracts] [Spring 2002 Abstracts] [Fall 2003  Spring 2004 Abstracts] [Fall 2004Spring 2005 Abstracts]
[Fall 2005Spring 2006 Abstracts]
Date: Thursday, October 5, 2006
Time: 2:002: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 nonnegative, 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*(v1), 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 EllisMonaghan, Mathematics Department, SMC
Abstract:
This talk will provide a gentle introduction (with pictures) to the Ising and qstate 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 statemodel 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.
(Notedue 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:301:20 pm
Location: Math Department Conference Room, Lord House, UVM Campus
Title: A bijection between 2triangulations and pairs of noncrossing 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 ktriangulation, 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 ktriangulations are enumerated by certain determinants of Catalan numbers, that are also known to count ktuples of noncrossing Dyck paths.
There are several simple bijections between triangulations of a convex ngon 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 2triangulations of a convex ngon and pairs (P,Q) of Dyck paths of semilength n4 so that P never goes below Q. The bijection is obtained by constructing isomorphic generating trees for the sets of 2triangulations and pairs of noncrossing Dyck paths.
Date: Thursday, April 26, 2007
Time: 3:304: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:201: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:0011: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:0011:50 a.m.
Location: Jeanmarie 290, SMC campus
Title: The HamiltonWaterloo problem: The case of trianglefactors and Hamilton
cycles.
Speaker: Jeff Dinitz, University of Vermont
Abstract: The HamiltonWaterloo problem in the case of trianglefactors and
Hamilton cycles asks for a 2factorization of Kn in which exactly r of
the 2factors are trianglefactors and exactly s of the 2factors 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:0011: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:0011:50 a.m.
Location: Jeanmarie 380, SMC campus
Title: Totally frustrated states: A physicslike 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 gaingraphic generalisation, but it always satisfies a deletioncontraction law and it has a formula in terms of holonomy groups of subgraphs.
Date: Tuesday, July 3, 2007
Time: 11:0011: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 nondegenerate 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:0011:50 a.m.
Location: Jeanmarie 380, SMC campus
Title: My 4color 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:0011:50 a.m.
Location: Jeanmarie 380, SMC campus
Title: Minimal Tile and BondEdge Types for SelfAssembling DNA Graphs
Speaker: Jo EllisMonaghan, Saint Michael's College
Abstract: We examine a model for selfassembling 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 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 I89: 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 fourway 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 Scurve and over bridge. Take third lefthand 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.