Combinatorics Seminars

Academic year 2003-2004

 

 

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 2003-Spring 2004.

(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 archdeac@emba.uvm.edu ).

 

Overview

For many years the Math and CS departments at UVM have conducted weekly discrete math/combinatorics/computer science seminars.  This year, the seminars will be 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 joellis@emba.uvm.edu or archdeac@emba.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
9/19/03 Dan Archdeacon How to construct self-dual polyhedra
10/1/03 Richard Lundgren Variations on interval graphs
10/22/03 Peter Dukes Constant composition codes.
10/29/03 Alice Dean Bar-visibility Graphs, Generalized and Specialized
11/12/03 Dan Archdeacon A tale of crayons and their consequences: why four colors suffice
11/19/03 Bill Martin The biweight enumerator of a binary code and the Terwilliger algebra of the hypercube
12/8/03 Gennian Ge A new direct construction method for block designs
2/2/04 Jeff Dinitz Generating uniform and perfect one-factorizations from starters
2/9/04 Heather Johnston

Polygonal knot theory and stuck unknots

3/22/04 Sue Whitesides

Rectangle Visibility Graphs:  Characterization, Construction,  and Compaction

 

[Fall 2001 Abstracts]  [Spring 2001 Abstracts] [Spring 2002 Abstracts]

Date:  Friday, September 19.

Time: 3:00 – 3:45 p.m.

Location:  002 Kalkin, UVM campus.

Title:  How to construct self-dual polyhedra.

Speaker:  Dan Archdeacon , UVM

Abstract:   Polyhedra include the classical Platonic solids: the tetrahedron, octahedron, cube, dodecahedron, and the icosohedron. A classical relation between these is duality. The tetrahedron is the only Platonic solid that is identical to its dual. In this talk we present six constructions for self-dual polyhedra, and sketch the proof that these constructions give all self-dual polyhedra.

Date:  Wednesday, October 1, 2003

Time: 2:30 pm

Location: Room 366, Jeanmarie, St. Michaels College Campus.

Title: Variations on Interval Graphs

 

Speaker: Richard Lundgren, Professor

Department of Mathematics

University of Colorado at Denver

 

Abstract:

Interval graphs originated in Benzer's original work on DNA in 1959. Over the years they have been thoroughly investigated and generalized, mostly because of their usefulness in many applications and the nice properties they exhibit. More recently, in 1996, Zhang introduced probe interval graphs as a means of studying various problems associated with physical mapping of DNA. Interval graphs are a special case of probe interval graphs. The definition of probe interval graphs leads naturally to an extension for bipartite graphs called interval bigraphs, and we have recently extended this class to a new class called interval k-graphs.

In this talk we will start by reviewing some of the classical results on interval graphs. We will then look at these new variations and discuss general properties, forbidden substructures, and some new and very new characterizations of these graphs. Some of the talk will cover joint work with my graduate students Dave Brown, Steve Flink, and Cary Miller, but there will also be considerable discussion of the recent work of several other authors on these topics. We will also discuss several open problems and suggestions for future research.

Interval graphs and their variations have applications in many areas including scheduling, computer science, archaeology, psychology, biology, {0,1}-matrix theory, etc. The talk will be understandable by a general math audience.

Date:  Wednesday, October 22                      

Time:  2:30 – 3:30 pm

Location:  UVM Campus, Mathematics Department Conference Room, First Floor, 16 Colchester Ave.

Title: Constant composition codes.

 

Speaker:  Peter Dukes, University of Toronto

 

Abstract:   ( TeX or LaTeX)

A code of length $n$ over the alphabet $\{1,\dots,k\}$ is said to have {\it constant composition} $[n_1,\dots,n_k]$ if every codeword has $n_i$ occurrences of symbol $i$ for $i=1,\dots,k$. Special cases are the constant weight binary codes ($k=2$) and permutation codes ($n_i=1$ for all $i$). In this talk, a recursive construction for constant composition codes will be presented. Also, various direct (algebraic and design-theoretic) constructions will be explored for compositions and distances of particular interest. This is joint work with Wensong Chu and Charles Colbourn .

 

Date:   Wednesday, October 29, 2003

Time:  2:30 - 3:30 p.m.

Location:  SMC campus, St. Edmunds, Room 113.

Title:  Bar-visibility Graphs, Generalized and Specialized

 

Speaker:  Alice Dean , Skidmore College

Abstract:  

Questions arising in the design of printed circuits motivate the study of “bar-visibility layouts,” in which a collection of horizontal bars is placed on a surface, and a connection exists between two bars if and only if there is an unobstructed vertical visibility between them. The class of underlying graphs that can be represented in this way is well understood, and there is a linear-time algorithm to recognize such “bar-visibility graphs” (or BVGs for short). The study of BVGs has been generalized in numerous ways (e.g., using other geometric objects for vertices, multiple visibility directions, 2-dimensional surfaces other than the plane, etc.), and it has been specialized to BVGs with all bars of equal length. This talk is a survey of some of what is known, and some of what remains to be discovered, about several variations of BVGs.  

 

Visibility Beyond The Plane

SPECIAL LECTURE!

 

Dan Archdeacon has been named a 2003 University Scholar (yay Dan!), an award honoring recipients for “sustained excellence in research and scholarly activity”.  Honorees present a University Scholars Lecture, a talk highlighting their research interests that is accessible to a general audience.  Dan will be talking about his favorite topic, playing with crayons, and attendees of the usual Combinatorics Seminar are cordially invited to attend.  There will be refreshments just before and after the talk.

Date: Wednesday November 12, 2003

Time: 4:00 - 5:00

Location:  Memorial Lounge, Waterman Building , UVM Campus.

 

Title: A tale of crayons and their consequences: why four colors suffice

 

Speaker:  Dan Archdeacon , UVM

 

Abstract: 

In 1852 Francis Guthrie noticed that the counties of England could be

colored with only four colors so that any two counties sharing a border

were colored differently. He asked his professor, Augustus De Morgan, if

this "quaternion of colors" was enough for every map, either real or

fictional. The problem was widely considered just a simple puzzle, and only

slowly unveiled itself as a fundamental problem in mathematics. This

lecture will trace the history of the four-color problem and how it is now

used in storage problems, computer architecture, and even for assigning

faculty to university committees.

 

Designed for a general audience, the lecture is guaranteed to be colorful.

 

Date: Wednesday November 19, 2003

Time:   4:00 pm, with refreshments immediately before (this is also a UVM colloquium talk).

Location:   Kalkin 001, UVM Campus.

 

Title: The biweight enumerator of a binary code and the Terwilliger algebra of the hypercube

 

Speaker:  Bill Martin, Department of Mathematical Sciences and Department of Computer Science, Worcester Polytechnic Institute

 

Abstract: 

The linear programming (LP) bound of Delsarte is the most

powerful known general purpose non-existence technique for digital

error-correcting codes. It is easily derived using the Bose-Mesner

algebra of the $n$-cube and the same technique can be used in any

symmetric association scheme.

 

Nevertheless, a recent result of Samorodnitsky suggests that the LP

bound is not strong enough to determine the asymptotic optimal rate of

a binary error-correcting code. Moreover, the LP approach applies to a

wide variety of other problems in coding theory and design theory, but

not always in an effective manner. This challenge motivates us to look

beyond the Bose-Mesner algebra to a larger matrix algebra introduced by

Terwilliger in 1992 which encodes finer combinatorial information.

 

After briefly surveying some recent developments in coding theory, I

will prove Delsarte's LP bound, introduce the Terwilliger algebra of

the $n$-cube, describe a connection between it and the biweight

enumerator of a binary code, and report on my progress to date in

developing a new extension of the LP bound based on this algebra. As it

turns out, we will need to use some elementary representation theory of

the symmetric group.

 

Date: Monday, December 8, 2003

Time:  2:30 – 3:30

Location:  Cheray 111, SMC campus

 

Title:  A new direct construction method for block designs

 

Speaker:  Gennian Ge

 

Abstract: 

In this talk, we introduce a new direct construction method for block designs. Several examples for non-uniform group divisible designs, resolvable  group divisible designs and optimal packings are illustrated to show the advantage of the construction method.

 

Date: Monday, February 2, 2004          

Time:  2:30 - 3:30 p.m.  

Location:  Science 111, St. Michaels campus

 

Title: Generating uniform and perfect one-factorizations from starters

 

Speaker:  Jeff Dinitz, department of mathematics, UVM

 

Abstract:   A one-factorization is uniform if the union of any two

one-factors give isomorphic 2-regular graphs.  It is perfect if this

union is always a Hamiltonian circuit.  In this talk we will discuss

how to construct such one-factorizations using elementary properties

of finite fields.  This is joint work with Peter Dukes at the

University of Toronto and is a current work in progress.  

Talk Overheads

Date: Monday, February 9, 2004          

Time:  2:30 - 3:30 p.m.  

Location:  Science 111, St. Michaels campus

 

Title: Polygonal knot theory and stuck unknots

 

Speaker: Heather Johnston , department of mathematics, Vassar College

 

Abstract:   Although knot theory has been studied for over 100 years,

polygonal knot theory and its combinatorial approach began in the

1990's.  We fix the length and number of edges of a polygon in

three-space and model each configuration as a set of rigid sticks

joined by very flexible hinges.   Those configurations that cannot be

moved into a convex planar configuration are called stuck.  We are

interested in those stuck polygons that are stuck only due to the

rigidity of the sticks.  For a stuck unknot the same configuration

could be unravelled if it were made of string rather than sticks.  We

will prove the existence of stuck unknots and discuss their

classification, which is still a work in progress.

Date: Monday, March 22, 2004           

Time:  2:30 - 3:30 p.m.  

Location:  Science 111, St. Michaels campus

 

Title: Rectangle Visibility Graphs:  Characterization,

     Construction,  and Compaction

 

Speaker: Sue Whitesides , department of computer science, McGill University

 

Abstract:  Non-overlapping axis-aligned rectangles in the plane define

  visibility graphs in which vertices are associated with

  rectangles and edges are associated with visibility in either

  the horizontal or vertical direction. The recognition problem

  for such graphs is known to be NP-complete.

 

  This talk introduces the notion of a “topological rectangle

  visibility graph”.  This notion is designed to capture more

  precise visibility information from sets of axis-aligned

  rectangles than does the usual notion of a rectangle visibility

  graph.  We give a combinatorial characterization of topological

  rectangle visibility graphs that are indeed realizable as sets

  of axis-aligned rectangles.  Our characterization gives rise to

  a polynomial time algorithm for recognizing topological

  visibility graphs that are realizable, and in the case of

  realizable graphs, for constructing a realizing set of

  rectangles on the unit grid.  The bounding box of these

  rectangles has optimum length in each dimension.

 

  Our algorithm provides a rectangle compaction tool: given a set

  of rectangles, one computes the associated topological

  rectangle visibility graph, and then runs the algorithm to get

  an optimally compact set of rectangles with the same visibility

  properties.

 

(This is joint work with Ileana Streinu.)  

 

Rectangle Visibility Graphs-power point slides of the talk.

 

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