UVM Combinatorics Seminars Spring 2002 |
UVM
Combinatorics Seminar, Spring 2002
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.
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 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 on-line slides and other resources from the various talks (if available) are provided at the end of each abstract.
Date |
Speaker |
Title |
1/22 | Alan Ling | On some weak coloring of $K_{n,n}$ |
1/30 | Dan Archdeacon | List Colourings of Graphs |
2/5 | Darryn Bryant | Completing latin rectangles to symmetric latin squares |
2/12 | Jo Ellis Monaghan | The Potts Model Partition Function as an evaluation of the Tutte polynomial |
3/12 | S. Narayan | Pad assignment and Grid design for the distribution of power in ICs |
3/26 | William Leipold | A Constrained Shapes Problem |
4/2 | Paul Gutwin | Basic Electronics |
4/9 | Jeff Dinitz | On Sets of Orthogonal Steiner Triple Systems, Part I |
4/16 | Jeff Dinitz | On Sets of Orthogonal Steiner Triple Systems, Part II |
4/23 | Marissa Debowsky | Results on Planar Hypergraphs and on Cycle Decompositions |
4/30 | Craig Damon | Reducing Search Space With Approximate Automorphism Groups |
[Fall 2001 Abstracts] [Spring 2001 Abstracts]
Date: January 22, 2002
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: On Some Weak Colorings of K_{n,n}
Speaker: Alan Ling, UVM
Abstract:
In this talk, we consider a problem studied by
Axenovich, F\"uredi, and Mubayi on generalized Ramsey theory.
In one case, they use the existence of Steiner
triple systems, Pippenger and Spencer's theorem on hyperedge coloring,
and the probabilistic method to show that $r^{'}(K_{n,n},C_{4},3)\leq
\frac{3n}{4}(1+o(1))$, where $r^{'}(K_{n,n},C_{4},3)$ denotes the minimum
number of colors to color the edges of $K_{n,n}$ such that every 4-cycle
receives at least either 3 colors or 2 alternating colors.
We review their proof using probabilistic method and then we improve
the result by using techniques from combinatorial design theory.
Date: January 29, 2002
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: List Colouring of Graphs
Speaker: Dan Archdeacon, UVM, Math Department
Abstract:
Suppose that every vertex of a graph is given a list of k colours. When can one
select a colour for each vertex from its list such that adjacent vertices have
different colours? The smallest size list for which this can always be done is
called the choosability chi(G). List colourings have become enormously popular
in recent years, because every question that has ever been asked about graph
colourings can asked again about choosability. In this survey talk I'll ask
many of these questions, answer some of them, and leave the others as open
problems.
[click here for overheads--postscript file]
Date: February 5, 2002
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: Completing latin rectangles to symmetric latin squares
Speaker: Darryn Bryant, University of Queensland, Australia
Abstract:
An n by n (partial) latin square is an n by n array of cells, each
(either empty or) containing a symbol chosen from an n-set such that
each symbol occurs exactly (at most) once in each row and exactly
(at most) once in each column. A partial latin square is said to be
completable to a latin square if its empty cells can be filled so
that a latin square results. An m by n (m at most n) latin rectangle
is a partial latin square in which the first m rows are filled and
the remaining rows are empty. A latin square is symmetric if for i
and j in the range 1 to n, cells (i, j) and (j, i) contain the same
symbol.
It follows from Hall's theorem on systems of distinct
representatives that any m by n latin rectangle can be completed to
an n by n latin square. However, deciding which m by n latin
rectangles are completable to symmetric latin squares is a more
difficult problem in general. Necessary and sufficient conditions
for a 2 by n latin rectangle to be completable to an n by n
symmetric latin square will be presented together with an outline
of the proof and discussion of related results.
Date: February 12, 2002
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: The Potts Model Partition Function as an evaluation of the Tutte polynomial
Speaker: Jo Ellis-Monaghan, UVM
Abstract:
This talk will be an introduction to the Potts Model from statistical mechanics followed by an exploration of its relation to the Tutte polynomial in graph theory. The Potts Model is used across many disciplines to model systems that exhibit states that change behavior as they pass through some kind of phase transition. Examples include the melting away of the magnetism of a heated sheet of metal, cell interactions in biology, gas-to-liquid transitions, binary alloys, beating heart cells, foam drainage, etc. The partition function of the Potts Model turns out to be an evaluation of the Tutte polynomial, which gives some insight into the computational complexity of the Potts Model (and vice-versa!).
[The slides for this talk were a subset of those for the colloquium talk later in the week, which can be found here]
Date: March 12, 2002
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title:
Pad assignment and Grid design for the distribution of power in
ICs
Speaker: S. Narayan, IBM
Abstract:
A semiconductor IC is made up of two parts, the "die" or the "chip",
which contains the logical brains of the IC and the "package",
which contains the interface to the external world,
including the plastic structure and the metallic pins that you
see on the back of every IC. These two parts are connected to
the each other by "pads". Each package can connect to a finite
and fixed number of pads depending upon its size and it is
economical to use a smaller package than a larger one.
For a given chip, there are multiple demands and constraints on
the pads that it can use. One of the primary occupier of these
pads are the "power voltages" that help to supply the energy
required by the circuits in the chip. Within the chip,
these voltages are distributed to different "demand" points,
that need the energy by means of large metallic, resistive
grids. These grids occupy large amounts of metal,
that could otherwise be used by the signals carrying
intelligence within the chip.
We will be describing the problem of assigning the pads and the
design of these power grids for an IC, such that various
electrical and other design conditions are satisfied.
[click here for overheads--pdf file]
Date: March 26, 2002
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: A Constrained Shapes Problem
Speaker: William Leipold, IBM
Abstract:
Given an algorithm for performing a series of operations on a set
of shapes which are subject to a set of constraints, how can a set of test
cases be chosen to maximize coverage of the space of all possible shapes
interactions?
Shapes consist of rectangles and polygons in 2-D Euclidean space.
Operations consist of Boolean operations like union, intersection,
and difference, general operations like expand and shrink, and edge-based
operations which segment existing edges and move the segments more or less
independently.
The constraints are a set of rules which limit the minimum width of
shapes and the space between shapes as well as governing things like
overlap of shapes on different design levels (which end up as different
layers on the chip).
[click here for overheads--pdf file]
Date: April 2, 2002
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: Basic Electronics
Speaker: Paul Gutwin
Abstract: An overview of basic electrical engineering concepts, with plenty of time for questions.
Date: April 9, 2002
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: On Sets of Orthogonal Steiner Triple Systems, Part I
Speaker: Jeff Dintz, UVM
Abstract: Two Steiner triple systems (STS) are said to be orthogonal
if their sets of triples are disjoint, and two disjoint pairs of
points defining intersecting triples in one system fail to do so in
the other. The notion of orthogonal STS (OSTS) was first introduced by
O'Shaughnessey in 1968 and he provided several small examples at that
time. It was not until 1994 that it was proven that a pair of OSTS of
order $v$ exist if and only if $v \equiv 1,3$ (mod 6) with $v \geq 7$
($v \neq 9$), completely settling the existence problem for OSTS.
In this talk we will we consider the quantity $\sigma(v)$, the size of
a maximum collection of pairwise orthogonal STS of order $v$. So the
result mentioned above says that $\sigma(v) \geq 2$ for all $v \equiv
1,3$ (mod 6) with $v \geq 7$ ($v \neq 9$). We will give constructions
in finite fields for improving this lower bound on $\sigma(v) and will
will also discuss hill-climbing algorithms used to improve this bound
for many orders.
Finally we will prove that $\sigma(v) \geq 3$ for all $v \equiv 1,3$
(mod 6) $v \geq 19$ for all but a small number of possible exceptions.
Date: April 16, 2002
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: On Sets of Orthogonal Steiner Triple Systems, Part II
Speaker: Jeff Dintz, UVM
Abstract:
This is a continuation of the April 9 seminar.
Two Steiner triple systems (STS) are said to be orthogonal
if their sets of triples are disjoint, and two disjoint pairs of
points defining intersecting triples in one system fail to do so in
the other. The notion of orthogonal STS (OSTS) was first introduced by
O'Shaughnessey in 1968 and he provided several small examples at that
time. It was not until 1994 that it was proven that a pair of OSTS of
order $v$ exist if and only if $v \equiv 1,3$ (mod 6) with $v \geq 7$
($v \neq 9$), completely settling the existence problem for OSTS.
In this talk we will we consider the quantity $\sigma(v)$, the size of
a maximum collection of pairwise orthogonal STS of order $v$. So the
result mentioned above says that $\sigma(v) \geq 2$ for all $v \equiv
1,3$ (mod 6) with $v \geq 7$ ($v \neq 9$). We will give constructions
in finite fields for improving this lower bound on $\sigma(v) and will
will also discuss hill-climbing algorithms used to improve this bound
for many orders.
Finally we will prove that $\sigma(v) \geq 3$ for all $v \equiv 1,3$
(mod 6) $v \geq 19$ for all but a small number of possible exceptions.
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: Results on Planar Hypergraphs and on Cycle Decompositions
Speaker: Marissa Debowsky, UVM Math dept
Abstract:
A graph $G$ consists of a vertex set $V(G)=\{v_1,v_2,...,v_n\}$, and an
edge set $E(G)=\{e_1,e_2,...,e_m\}$, where edge $e_i=\{u,v\}$ joins two
(possibly equal) vertices $u$ and $v$. One generalization of a graph is a
{\em hypergraph}, in which an edge is a nonempty subset of the
vertices. One fundamental question in graph theory is that of planarity:
which graphs can be drawn in the plane with no edge
crossings? Kuratowski's Theorem gives necessary and sufficient conditions
to draw a graph in the plane with no edge crossings. In the first part of
this talk, we develop an analogue of Kuratowski's Theorem for hypergraphs
and answer the question, ``Which hypergraphs are planar?'' The
characterization is in terms of a related bipartite graph, the incidence
graph $G$ of a hypergraph $H$, formed by considering the incidences of
vertices and hyperedges in $H$. We give an obstruction set to planarity
for bipartite graphs and, consequently, hypergraphs, under several partial
orders.\\
In the second part of the talk, we turn our attention to another question
in graph theory: decomposing a graph into smaller subgraphs. Of particular
interest are cycle decompositions of complete and complete bipartite
graphs. In this chapter, we discuss decompositions of the complete
bipartite graph $K_{n,n}$, where $n$ is odd. Since the degree of each
vertex in $K_{n,n}$ is odd and cycles are regular of degree 2, it is
necessary to remove a 1-factor as well, resulting in a decomposition of
$K_{n,n}$ into cycles and a 1-factor. We present several infinite families
of decompositions.\\
Date: April 30, 2002
Time: 8:30 - 9:20 am
Place: Math Department Conference Room, 16 Colchester Avenue
Title: Reducing Search Space With Approximate Automorphism Groups
Speaker: Craig Damon, UVM CS dept
Abstract:
Many interesting decision problems involve searching immense search
spaces. One possible approach to reducing the search space is
removing elements that are isomorphic to other remaining elements.
Perfect detection of isomorphic elements is itself an exponentially
expensive operation, In this talk, I demonstrate how conservatively
approximate automorphism groups can be used to efficiently reduce the
search space.
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.
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.