UVM Combinatorics Seminars Fall 2001 
UVM
Combinatorics Seminar, Fall 2001
Tuesdays, 8:30 to 9:20 am.
For
many years the Math and CS departments at UVM have conducted weekly discrete
math/combinatorics/computer science seminars.
This fall, in addition to traditional talks in theoretical combinatorics,
there will also be a focus on the applications of
combinatorics. Last spring, our
goal was 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 organizer at joellis@emba.uvm.edu
with a brief description of what you would like to talk about.
The seminars generally meet in the conference room of the UVM Math Department at 16 Colchester Avenue, Burlington, VT. Check specific abstracts for any possible location/time changes.
Time: 8:30 to 9:20 am on the following Tuesdays (click on the date to go to that day's abstract):
Links to online slides and other resources from the various talks (if available) are provided at the end of each abstract.
Date 
Speaker 
Title 
John Cohn 
Two Layout Problems  

A Walk through the Brambles...  

A Walk through the Trees...  
John Cohn 
Pattern Recognition  

A Characterization of ProjectivePlanar Signed Graphs 

Jo EllisMonaghan  The Tutte polynomial and a (very) small subset of its properties and applications.  
Rosa Orellana  Hecke algebras and Markov traces  
All Participants  Problem workshop  
Heather Gavlas  Hamiltonian Paths in Cartesian Powers of Directed Cycles  
David Pike  Decycling Hypercube Graphs.  
Paul Gutwin  DRC, LVS, OPC and other TLA's; Pattern Matching Problems in Design Automation  
Paul Bonnington  Conjectures about planar graphs 
Date: September 11, 2001
Time: 8:30  9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: Two Layout Problems
Speaker: John Cohn, IBM
Abstract:
A description of two layout problems with combinatorial flavor, Predicting Netlist Congestion and Finding Layout Patterns, will be given.
[PowerPoint slides of the presentation available here]
Date: September 18, 2001
Time: 8:30  9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue. We will adjourn to Mansfield house at 9:30 for any follow up discussion.
Title: Grid minors, brambles, and trees: A measure of connectivity and its
application to circuit layout problems
Speaker: Dan Archdeacon, UVM Math Department
Abstract:
In our seminar last week John Cohn presented a problem on circuit layouts
and asked if there was a way to predict which parts of the circuit create
difficulties. This talk is in response to his plea.
In the first part of this presentation I'll give a mathematical model of
circuit layouts in terms of graphs, grids, and minors, and ways to measure
the efficiency of this layout. In the second part I'll present the bramble
number of a graph: a measure of connectivity that shows a given graph may
be difficult to layout. This can help explain, in part, why crossbar
switches are (in John's words) "difficult to unsnarl". In the third part
I'll present treedecompositions: how to partition the graph into portions
that are each relatively easy to unsnarl.
I promise to go slowly, in part because some of this is exploratory for me too.
I expect that the presentation will continue on September 25th.
Date: September 25, 2001
Time: 8:30  9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue. We will adjourn to Mansfield house at 9:30 for any follow up discussion.
Title: Continuing the stroll through the trees and the brambles.
Speaker: Dan Archdeacon, UVM Math Department
Abstract:
This is a continuation of the previous week's talk.
In our seminar on Sept. 11, John Cohn presented a problem on circuit layouts
and asked if there was a way to predict which parts of the circuit create
difficulties. This talk is in response to his plea.
In the first part of this presentation I'll give a mathematical model of
circuit layouts in terms of graphs, grids, and minors, and ways to measure
the efficiency of this layout. In the second part I'll present the bramble
number of a graph: a measure of connectivity that shows a given graph may
be difficult to layout. This can help explain, in part, why crossbar
switches are (in John's words) "difficult to unsnarl". In the third part
I'll present treedecompositions: how to partition the graph into portions
that are each relatively easy to unsnarl.
Date: October 2, 2001
Time: 8:30  9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: Pattern Recognition
Speaker: John Cohn, IBM
Abstract:
John will return to the second problem he was going to present on 9/11,
but did not for lack of time. Finding geometric interactions in chip
designs is very difficult. Methods exist to find these interactions, but
they are inexact and labor intensive John will describe this problem in
more detail, and touch on some ideas for further exploration.
Date: October 9, 2001
Time: 8:30  9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue.
Title: A Characterization of ProjectivePlanar Signed Graphs
Speaker: Marisa Debowsky, UVM Math
Abstract:
A signed graph has a plus or minus sign on each edge. A cycle is balanced
or unbalanced depending on whether it contains an even or odd number of
negative edges, respectively. We consider embeddings of a signed graph in
the projective plane where a cycle is essential if and only if it is
unbalanced (and contractible otherwise). We characterize those signed
graphs that have such a projective planar embedding. Our characterization
is in terms of balanced a related graph formed by considering the
homeomorphs of K2,3 in the given graph.
(This is joint work with Dan Archdeacon)
Date: October 16, 2001
Time: 8:30  9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue.
Title: The Tutte polynomial and a (very) small subset of its properties and applications.
Speaker: Jo EllisMonaghan, UVM Math
Abstract:
A graph polynomial is a polynomial
associated with a graph such that isomorphic graphs have the same polynomial. The Tutte polynomial is one of the most wellstudied of the
graph polynomials, and encodes a wealth of information such as coloring, flows,
reliability, electron spins (Potts model in physics), etc., etc.
This talk will be a very gentle introduction to the Tutte polynomial, a couple of its properties, perhaps an application or two, and, if time, a little bit concerning an open question about derivatives of the Tutte polynomial counting anticircuits.
Date: October 23, 2001
Time: 8:30  9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue.
Title: Hecke algebras and Markov traces
Speaker: Rosa Orellana, Dartmouth College
Abstract:
The Hecke algebras of type
A arise naturally in the study of knot
theory, quantum groups, and Von Neumann algebras. Their relation to the
symmetric and braid groups allows for their study using combinatorics and low
dimensional topology.
In this talk I will define the Hecke algebras of type A and B and
show their relation to the symmetric group and the braid group (this
groups will be defined in this talk). I will also construct a beautiful
homomorphism from a specialization of the Hecke algebra of type
B onto a reduced Hecke algebra of type A. I will show
how this homomorphism can be used to compute some traces on the
Hecke algebra of type B, called Markov traces. If time permits, I
will give other applications of this homomorphism.
This talk will be accessible to graduate students.
Date: October 30, 2001
Time: 8:30  9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue.
Title: Problem Session Workshop
Speaker: All participants
Abstract:
Today will be a workshop to give participants an opportunity to informally
discuss ongoing problems and concepts. We will start with the two
problems introduced by John Cohn on layout congestion and pattern
recognition, but anyone is welcome to introduce any other ideas. This
will be a good opportunity to get more detailed information not only about
the problems, but also about ideas such as tree width and brambles which
have been introduced in other seminars.
Date: November 6, 2001
Time: 8:30  9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue.
Title: Hamiltonian Paths in Cartesian Powers of Directed Cycles
Speaker: Heather Gavlas, UVM Math
Abstract:
The vertex set of the
k^{th } cartesian power of a directed cycle
of length m can be naturally identified with the
abelian group (Z_{m})^{k} . For any two elements
v
= (v_{1}, v_{2},..., v_{k}) and w=(w_{1},
w_{2},..., w_{k}) of (Z_{m})^{k}, it is
easy to see that if there is a hamiltonian path from v to w, then
v_{1}+ v_{2}+...+ v_{k} is
congruent to w_{1}+ w_{2}+...+ w_{k}
+ 1 (mod m)
We prove the converse, unless k = 2 and m is odd.
This
is joint work with David Austin, Grand Valley State University,
and Dave Witte, Oklahoma State University .
Date: November 13, 2001
Time: 8:30  9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue.
Title: Decycling Hypercube Graphs
Speaker: David Pike, Memorial University of Newfoundland
Abstract:
The decycling number,
L(G), of a graph G is the
least number of vertices of G
whose deletion results in an acyclic graph.
The family of graphs which we consider are the hypercubes:
let Q_{n} be the graph in which each binary string of length n
is a vertex, and where two vertices are adjacent if and only if
they differ in a single coordinate.
Improved bounds are obtained for the decycling number L(Q_{n})
of the hypercube Q_{n}. In so doing, a connection between L(Q_{n})
and the size A(n,4) of a maximum binary code of length n
and minimum distance 4 is established.
Date: November 27, 2001
Time: 8:30  9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue.
Title:
DRC, LVS, OPC and other TLA's; Pattern Matching Problems in Design
Automation
Speaker: Paul Gutwin, IBM
Abstract:
This presentation will follow up John Cohn's "second" problem
with a set of practical pattern matching problems. A brief explanation will
be provided for several pattern matching problems in Design Automation, and
examples will follow each explanation. A list of resources will be provided
at the end.
[click
here for PDF file of the overheads]
Date: December 4, 2001
Time: 8:30  9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue.
Title: Conjectures about planar graphs
Speaker: Paul Bonnington, University of Auckland
Abstract:
We present a number of recent conjectures about really, really, very big planar graphs.
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 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://scripts.uvm.edu/www/map.php3.
Click on the map to zoom in, or use the "locate" button at the bottom to find specific buildings or
parking lots (the Math Department is 16 Colchester, the visitor lot is across College street from Waterman building).
A map of the whole campus with visitor parking colored green is at http://www.uvm.edu/~tpswww/images/oncampus.jpg,
but you need a LARGE monitor to read the labels.
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.