Colloquia, Spring 1999

Vanderbilt Mathematics
Spring 1999

April 29.

Ju Wang,
of the
Institute of Software, Academia Sinica, Beijing.
Definabilities and Finite Base Theorems, A research survey.

We investigate the main finite base theorems in
universal algebra proven by R. McKenzie, McKenzie & Freese,
Vaughan-Lee, Willard, Baker and Oates-Powell.
Our intentions are:

  1. Find some common nature of those varieties which
    have a finite base. To be specific, we look into the definabilities
    of principal congruences, something every principal
    congruence in those varieties should have.
  2. Search for a general mothed.
  3. Form some general finite base theorems. For example,the
    following two syntactical theorems are plausible:

    1. If A is finite, V(A) is meet semi-distributive, and
      has a definable SI class, then V(A) is finitely based.
    2. If A is finite and V(A) is congruence-modular with
      a definable SI class, then V(A) is finitely based.

    (I) and (II) would cover the major finite base theorems we

April 27.

Beifang Chen, of the
Hong Kong
University of Science and Technology, Kowloon
Counting Cohesive Geometric Objects.

Mathematics started with counting. Cantor knew how to count an infinite
number of objects, but was finally mad when counting uncountable sets.
Fortunately, Euler and Poincare taught us how to count cohesive objects,
including some of those uncoutable sets. In this talk I will present a
combinatorial theory on geometric measures, a typical connection between
combinatorics and other branches of mathematics from the counting point
of view.


April 26.

John Lavery, of the
Army Research Office
(Research Triangle Park, NC). First, a 10-minute talk about
Applied Analysis Program
at ARO.

The Applied Analysis Program at the Army Research Office supports research
in mathematical analysis for advanced solid materials for structures, armor
and sensors, soil and granular materials, fluid flow for chem/bio defense
and diesel combustion, photonic bandgaps, nonlinear dynamics for chaotic
communication devices, inverse scattering for landmine detection, data
fusion and modeling of irregular surfaces. — Then, a 40- or 50-minute talk on
Nonoscillatory Splines: Shape-preserving, Multiresolution, Piecewise
Polynomial Geometric Modeling.

We discuss a new class of “nonoscillatory” polynomial interpolating and
approximating splines that preserve the shape both of smooth data and of
data with abrupt changes in magnitude or spacing. These splines do not
require constraints, penalties, a posteriori filtering or interaction with
the user. One nonlinear minimization principle with no ad hoc components and
with only discretization and “regularization” needing to be chosen works
for all cases. Univariate and multivariate cases and cubic and higher-degree
splines are treated in one and the same framework. Finally, these splines
can be implemented using efficient interior-point methods for convex
nonlinear optimization.


April 15.

David R. Larson,
Texas A&M University.
Operator Algebras, Wavelets and Frames.
Orthonormal wavelets can be regarded as complete wandering
vectors for a system of bilateral shifts acting on a separable infinite
dimensional Hilbert space. Operator algebraic considerations lead
naturally to certain results for orthonormal wavelets, Riesz wavelets and
their kindred frame wavelets, that might not seem so natural from a purely
function-theoretic point of view. These considerations also yield
alternate derivations of some well-known function-theoretic results.
There are connections between this functional analytic approach to wavelet
theory and the harmonic analysis approach developed by Guido Weiss and his
group over the past five years.


April 8.

Alexander Kostochka,
of the
Russian Academy of Sciences,
Institute of Mathematics,
Novosibirsk, Russia.
On the number of edges in color-critical graphs
and hypergraphs.

Studying color-critical graphs initiated by G. Dirac in the fifties helps
to understand some reasons why the chromatic number of a graph is
high. One of the interesting questions on critical (hyper)graphs is: how small
can the number of edges in a k-critical (hyper)graph be with a given
number of edges?
Basic results are due to Dirac (1957 and 1974) and T. Gallai (1963).
Somehow, between 1974 and 1994, there was little progress in this
direction. But in the last 4 years new interesting bounds were proved.
The aim of the talk is to review the recent progress on the topic.


April 6.

Zeph Grunschlag
of the
University of California
at Berkeley
Connections between word hyperbolic groups and formal

Let G be a group with a finite set X generating G
as a monoid. The word problem for G is the set of words on
X which represent the identity element of G. Thus the
word problem is a certain language (i.e. it is a subset of the free
monoid X*). For example, if G is the cyclic
group Z5 = <x|x5 = 1>
then x5, x10,
x15, … are in the word problem for G.

There are well known characterizations of certain classes of groups in
terms of the word problem. Indeed, G has a regular word problem if and
only if it is finite, and a context free word problem if and only if it is
virtually free. It is also possible to classify word hyperbolic groups in
this manner.
In a different direction, one can define a notion of regularity for
subsets of word hyperbolic groups. The problem of computing the
Gersten-Stallings angle between subgroups of a hyperbolic group can often
be reduced to the membership problem of a certain regular subset. This
implies the following theorem:

Let A and B be subgroups of a word hyperbolic group G.
Suppose that A, B and the join
AvB are quasiconvex.
Then the angle between A and B is computible.

I will attempt to define as many of the above concepts as possible.
For example, word hyperbolic groups, regular languages,
context free languages, the Gersten-Stallings angle, etc.,
will all be defined.


March 25.

Heinz-Juergen Voss, of the
University of Dresden
Light subgraphs of multigraphs embedded
in compact 2-manifolds.
This is joint work with
Stanislaw Jendrol, P.J.Safárik University Kosice, Slovakia.

Fabrici and Jendrol’ proved that each 3-connected plane graph with a
k-path (a path of k vertices), contains a
k-path such that each vertex
has a degree at most 5k.
Further they showed that each 3-connected plane graph with at least k
vertices contains a connected subgraph on k vertices such that each vertex
has a degree at most 4k+3 for each k>3. Both bounds are sharp.
We generalized these results to compact 2-manifolds M of Euler
characteristic x(M)<0. Three of our results are: each polyhedral
map of M with a k-path contains a k-path such that each vertex
has a degree at most
[image]. Equality for
even k>2. If G is a 3-connected multigraph on M without
loops and 2-faces then the degree
bound is (6k-2e)(1+|x(M)|/3),
where e=0
if k is even,
and e=1 if k is odd.
If G is a 3-connected graph on M, then the degree bound is
[image] for
k>4, x(M)<0 and for k>2, x(M)<-3. All the bounds
for G are the best possible.


March 23.

Joachim Stöckler, of the
University of Missouri at St. Louis.
On Wavelet Frames Generated by Multiresolution Analysis.

Several approaches to wavelet frames generated from
multiresolution analysis were proposed in the literature. Let us
recall that a family
Y={yi; i=1,…,n}
is said to generate a wavelet frame if the dilates and translates
of all functions yi, defined by
satisfy the relation


Here, A and B are positive constants, the frame bounds.
— The study of tight frames (where A=B) has recently received much
attention, partly due to work by A. Ron and Z. Shen. The
understanding of non-tight frames is far less developed. Two major
analytical problems are the search for good estimates of the frame
bounds, and the development of a reconstruction formula which is
similar to the decomposition formula using biorthogonal wavelet
bases. A new technique making use of the underlying
multiresolution analysis relates the frame operator with a
generalized Laurent operator. We present consequences of this
approach with regard to both problems mentioned above.


March 19.

Boris Okun, of
Ohio State University.
l2-homology of Coxeter groups.

A famous conjecture of Hopf states that the Euler characteristic of a
closed aspherical manifold of even dimension satisfies the inequality
(-1)nx(M2n> 0.
In recent work with Mike Davis, we
calculated the l2-homology groups of
(some) right-angled Coxeter
groups. This calculation implies the Hopf conjecture for non-positively
curved cubical manifolds of dimension 4 and also leads to a new
obstruction for graph embedding problems.


March 17.

Jonathan Corbett, of the
of Washington in Saint Louis
A Brief Introduction to Spatio-Temporal Wavelets.

A function is called an orthonormal wavelet in a Hilbert Space, H, if the
family of integer translations of its dyadic dilations forms an
orthonormal basis for H. A family of orthonormal wavelets is actually a
discretization of a family of continuous wavelets which is the orbit of a
single “mother wavelet” under the action of the affine, or “ax + b,”
group. This family is tuned to the translations and dilations of the
affine group and can identify these features in signals. We may construct
wavelets on other physical groups wavelet families tuned to the actions of
those groups. Previously, such wavelets had been created for the Galilei
group of constant velocity motions. We shall extend these constructions
to Newtonian groups, which add arbitrary levels of acceleration to the
Galilei group, and to Rotational motion groups. We shall also propose an
algorithm for estimating such motion in digital image sequences and
consider simultaneously estimating translational and rotational motion


March 5.

Alexander Dranishnikov,
of the
University of Florida.
Alexandroff’s Problem and the Novikov Conjecture.

In late 20s P.S. Alexandroff came with a definition of
the cohomological dimension and he posed the natural problem:
Does the cohomological dimension agree with the standard
(covering) dimension for compact metric spaces?
This problem has a long history. It was finally
solved only in late 80s. Recently a shadow of
the Alexandroff problem appeared in the coarse
approach to the
higher signatures conjecture


March 4.

, of the
University of Missouri
at Columbia
The Modern Theory of Frames.

Frames in Hilbert spaces play a major role in many areas
such as signal processing, image and data compression etc.
We will survey many of the uses (both
concrete and abstract) of modern frame theory. In the
process, we will look at some recent advances in the area
as well as some of the important open questions.


February 25.

Ervin Gyori,
of the
Renyi Institute of Mathematics,
in the
Hungarian Academy of Sciences,
Applications of Graph Theory to Analysis and Number Theory.

Have you seen a monotone increasing real function with a
discontinuity at every rational number? As you probably know, it is a
non-trivial problem to construct such a function. In this talk, a function
will be presented what was not constructed but was discovered in graph
theory. It (hopefully) describes the behaviour of a numerical invariant of
graphs depending on their minimum degree.

How many numbers can we choose from among the integers 1,2,…,n so that
no six of them have a square number as their product. Why is six in the
question? What is the answer? And how does graph theory come into the
picture? We will answer these questions in the second part of the


February 18.

Robert Carr, of
Sandia National Laboratories.
A New Bound for the 2-Edge Connected Subgraph Problem.
Given a complete undirected graph with
nonnegative costs on the edges, the 2-Edge Connected Subgraph
consists in finding the minimum cost spanning
2-edge connected subgraph (where multiedges are allowed in the
solution). A lower bound for the minimum cost 2-edge connected
subgraph is obtained by solving the linear programming relaxation
for this problem, which coincides with the subtour relaxation
of the traveling salesman problem with the costs satisfy the triangle
inequality. … The simplest fractional solutions to the subtour
relaxation are the half-integral solutions in which
every edge variable has a value which is a multiple of 1/2.
We show that the minimum cost of a 2-edge connectes subgraph is
at most 4/3 the cost of the minimum cost half-integral solution
of the subtour relaxation. This Hamilton cycle which is
within 4/3 the cost of the optimal subtour relaxation solution
when the costs satisfy the triangle inequality. …
This is a joint work with R. Ravi.


February 16.

Bin Han,
of Oklahoma State University.
Analysis and Construction of Optimal Multivariate Wavelets.

In this talk, we shall talk about some basic concepts and
some developments in wavelet theory. Refinable functions play an important
role in wavelet theory since wavelets are built from them. The success of
wavelet theory lies in the three most important properties of refinable
functions: short support, high approximation order and reasonably high

First of all, we shall talk about how to measure and characterize the
smoothness of a refinable function. It is known that short support, high
approximation order and high smoothness of a wavelet function are
competing objectives in design of wavelets. Next, we shall talk about
optimal wavelets and investigate the highest possible approximation order
and highest possible smoothness order of a refinable function with respect
to its support.

Finally, a newly developed TCBC algorithm to construct biorthogonal
wavelets will be presented.


February 9.

Bojan Popov, of the
University of South Carolina.
Conservation Laws and Transport Equations.

We are interested in the analytical properties and numerical
approximations of the entropy solution operator to scalar convex
conservation laws. In this context, by duality, one encounters
linear equations with discontinuous transport velocities.
We discuss our new results on existence, uniqueness and
regularity of solutions to linear transport equations.
We use these regularity results to describe a new contractivity
space for conservation laws. We discuss the applications of these
results in proving error estimates for adaptive numerical methods
for conservation laws.
(Refreshments afterward in SC-1425.)


February 2.

Guergana Petrova, of the University of South Carolina
(Columbia, South Carolina)
. Transport Equations and
Velocity Averages.



January 14.
Catherine H. Yan, of
New York University
(Courant Institute).
A Recurrence Associated with Extremal Problems.

In this talk we study sequences of integers {g(n)} defined by
recurrence relations of the following form:

g(n+1)= [[(1+ (k/(n-a))g(n)]]

where k>0 and [[x]] denotes the largest integer not greater than x.
Such recurrences often arise in the study of extremal combinatorial
structures, for example, the Turan number for hypergraphs
and the distribution of values of angles determined by coplanar points.
We discuss the asymptotic properties of such recurrences,
focusing in particular on the cases k=2,3.
For any k>0, the limit g(n)/nk exists.
If we start with the initial condition g(b)=c,
we let G(k,a,b,c) denote that limit.
We give the general solution of g(n)
for k=2, and prove that in this
case, the limit g(n)/n2 is always rational.
The case of k=3 is more complicated.
We give some sufficient conditions on the initial values
which guarantee that the limit G(3,a,b,c)
is rational. At the end of this talk we apply
our results to various extremal combinatorial problems.

Back Home