Combinatorics Seminars Academic year 2003-2004 |
SMC Math 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 ).
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.
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.
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.
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.
T
Location: 002 Kalkin, UVM campus.
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:
Location:
UVM Campus, Mathematics Department
Conference Room, First Floor,
Title: Constant composition codes.
Speaker:
Peter Dukes,
Abstract:
(
Date:
Time:
Location: SMC campus, St. Edmunds, Room 113.
Title:
Bar-visibility Graphs, Generalized
and Specialized
Speaker:
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.
SPECIAL
LECTURE!
Date:
Time:
Location:
Memorial Lounge,
Title:
A tale of crayons and their consequences: why four colors suffice
Speaker:
Abstract:
In
1852 Francis Guthrie noticed that the counties of
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:
Time:
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:
Time:
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:
Time:
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
Date:
Time:
Location: Science 111, St. Michaels campus
Title:
Polygonal
knot theory and stuck unknots
Speaker:
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:
Time:
Location: Science 111, St. Michaels campus
Title:
Rectangle
Visibility Graphs: Characterization,
Construction, and Compaction
Speaker:
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 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 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.
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.