UVM  Combinatorics Seminar, Fall 2001

Tuesdays, 8:30 to 9:20 am.

Overview

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.  This fall's seminar series will continue and build on the foundations laid last spring.

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 organizer at joellis@emba.uvm.edu with a brief description of what you would like to talk about.

Schedule and Abstracts

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 on-line slides and other resources from the various talks (if available) are provided at the end of each abstract.

[Spring 2001 Abstracts]

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 cross-bar

switches are (in John's words)  "difficult to unsnarl". In the third part       

I'll present tree-decompositions: 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 cross-bar

switches are (in John's words)  "difficult to unsnarl". In the third part       

I'll present tree-decompositions: 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 Projective-Planar 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 Ellis-Monaghan, 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 well-studied 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₁, v₂,..., v_k) and w=(w₁, w₂,..., w_k) of (Z_m)^k, it is
easy to see that if there is a hamiltonian path from v to w, then
v₁+ v₂+...+ v_k is congruent to  w₁+ w₂+...+ 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. 

Directions and Parking

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 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://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.

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.