UVM Combinatorics Seminars

Spring 2002

 

 

Overview Schedule and Abstracts Participating Directions and Parking

UVM        IBM

UVM CS Dept.

UVM Math Dept. UVM Home Jo E-M Home

 

UVM  Combinatorics Seminar, Spring 2002

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.  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 spring'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 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.

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.

Date: April 23, 2002

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. 

 

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.

 

UVM CS Dept.

UVM Math Dept. UVM Home Jo E-M Home