San Francisco State University Department of Mathematics

ABSTRACT: Many real-life technical problems such as greyscale or color printing, scheduling or production planning demand a continuous-to-discrete transformation, a coding of data which by nature are analog, but must be stored or transmitted in a digital version (decision making). Such transformation or representation or quantization is erroneous by nature, but if lucky, the cumulative error is bounded.
We are interested in an on-line quantization, that is in producing digitized outputs knowing only the inputs up to a given moment.
One of the methods to code is to split a space of data into disjoint parts. Another is to follow not the data, but the data modified by the accumulated error and then to use the partition.
I will talk about a model of such procedure when the partition is generated by a polytope, its elements are the Voronoi regions of the corners. The errors are the vectors from the modified data to the chosen corner and the next modified data point are translations of the previous ones.

_______________________________________________________________________________________

ABSTRACT: Let BA denote the set of real numbers with bounded continued fraction coefficients. This is a set of zero Lebesgue which is also meager (small in the sense of category). Nevertheless it was shown by W. Schmidt in 1966 that for any sequence a_1, a_2, ... of reals, the countable intersection of BA + a_i is nonempty. In proving this result Schmidt introduced a powerful (yet amusing) method based on a game for two players, which can be played on any complete metric space. In recent work with Dmitry Kleinbock we describe variants of Schmidt's game which make it possible to show that certain dynamically defined sets have nonempty intersection. As a consequence we verify a conjecture of Margulis from 1990.

_______________________________________________________________________________________

ABSTRACT: A positive affine monoid M is a finitely generated submonoid of a free abelian group of finite rank whose only invertible element is 0. It is called normal if every x in gp(M) (the group generated by M) for which a positive integer multiple kx lies in M belongs to M itself. The Hilbert basis of M is the subset of those elements that can not be decomposed as a sum of two nonzero elements of M. Hilb(M) is in fact the unique minimal system of generators of M.
One says that M has unimodular Hilbert covering (UHC) if it is the union of those submonoids that are generated by a basis of gp(M) contained in Hilb(M), and M has the integral Carathéodory property (ICP) if it is the union of those submonoids that are generated by subsets of Hilb(M) of cardinality at most rank M. The terminology is motivated by Carathéodory's theorem on cones: every point in the cone generated by a set $X \subset \mathbb{R}^d$ is in one of the subcones generated by a subset $X'\subset X$ of cardinality $\le d$.
Clearly, (UHC) implies (ICP), and as proved by Bruns and Gubeladze, (ICP) implies normality. In dimension $\le 3$ every monoid has (UHC) as shown by Sebö, but in 1998 B&G found a rank 6 normal monoid that has neither (UHC) nor (ICP). It remained an open problem whether (ICP) implies (UHC) until recently when we discovered a rank 6 monoid that is (ICP) but not (UHC). We will discuss the truly experimental approach to the discovery of the (counter)examples which have been as hard to find as needles in a haystack.
Though the relationship between normality, (UHC) and (ICP) is clarified in general, there remain tantalizing open problems. For example, the situation in dimensions 4 and 5 is completely open. However, our experimental data suggest that in these dimensions all normal monoids have (UHC).

_______________________________________________________________________________________

ABSTRACT: In 1980, Kazhdan and Lusztig introduced an interesting basis for the Hecke algebra of a Weyl group. The transition matrix from the Kazhdan-Lusztig basis to the usual basis is given by the Kazhdan-Lusztig polynomials. These polynomials are related to rational smoothness of Schubert varieties and to Verma modules in representation theory. Because of their geometrical interpretation, Kazhdan and Lusztig have shown that these polynomials have non-negative integer coefficients. However, it is a long standing open problem to find a combinatorial interpretation for these coefficients. There are some special cases where both the Kazhdan-Lusztig basis elements and polynomials are particularly easy to compute using an all positive formula, which we call the Deodhar elements. We will give an efficient characterization of the Deodhar elements using a new type of pattern avoidance based on the two-sided weak Bruhat order.
We will begin the talk with the basic definitions and an expository survey of several recent interesting theorems in this area. Then we will present our main theorems using embedded factors. Finally, we will conclude with some open problems and future directions.
This talk is based on joint work with Brant Jones at the University of Washington.

_______________________________________________________________________________________

ABSTRACT: In this talk, I will give an overview of the random knot problem: the various models used to study random knotting phenomena, topological and geometrical problems arising in the study of random knots, some theoretical results as well as a brief introduction of the numerical methods used.

_______________________________________________________________________________________

ABSTRACT: In the race to develop new treatments for currently incurable diseases, quantitative methods are gaining prominence. Mathematical modeling has been used to show the superiority of combination therapy for HIV+ patients and to predict therapies that are most likely to help leukemia patients. I will share examples that used undergraduate calculus and statistics to yield these results.

_______________________________________________________________________________________

ABSTRACT: Combinatorics, in particular graph theory, has a rich history of being a domain of successful applications of tools from other areas of mathematics, including topological methods. In this talk I will survey the study of the Hom-complexes, and the ways these can be used to obtain lower bounds for the chromatic numbers of graphs. The structural theory will be developed and put in the historical context, encompassing in particular the Lovasz Conjecture, which can be stated as follows: For a graph $G$, such that the complex $Hom(C_{2r+1},G)$ is $k$-connected for some integers $r$ and $k$, $r>0$, $k>-2$, we know that the chromatic number of $G$ is at least $k+4$. Beyond the, more customary in this area, cohomology groups, the algebro-topological concepts involved are spectral sequences and Stiefel-Whitney characteristic classes. The latter are used to state the more general Babson-Kozlov conjecture which says: For any graph $G$, we have $\chi(G)\geq h(Hom(C_{2r+1},G))+3$. Here, for a ${\mathbb Z}_2$-space $X$, $h(X)$ denotes the maximal exponent of the non-zero power of the Stiefel-Whitney characteristic class of the associated line bundle. I shall give an extremely short combinatorial proof of the Babson-Kozlov conjecture. Furthermore, I shall describe how to use the spectral sequences to perform a complete calculation of the cohomology groups of the colorings of cycles. If time permits, I will also say a few words about homological tests for graph colorings based on our theoretical results. (part of the talk is based on joint work with Eric Babson and with Sonja Cukic)

_______________________________________________________________________________________

ABSTRACT: The background of this work is the standard problem of minimization of some total energy functional, but with specific choices of the internal energy density functions g(x). Our interest in this study is motivated by the search of effective solutions to certain inverse problems, particularly for real-time image noise removal for digital cameras. In general, depending on the objectives of the inverse problems under investigation, such as curve fitting, image noise removal, and feature extraction, the internal energy in our study is governed by g(|Lu|); with (Lu)(x) = u''(x), (Lu)(x,y) = (Grad u)(x,y), and Lu being some wavelet transform of u in any dimension. For digital image noise removal, in particular, a suitable choice of g(x) leads to the anisotropic diffusion model, the discretization of which, in turn, is relevant to the design of certain content-dependent filters, notably the bilateral filters. A natural generalization of this approach also gives rise to the notions of diffusion maps and geometric harmonics that constitute the foundation for the recent research investigations in diffusion wavelets for analyzing complex data in high dimensions.

_______________________________________________________________________________________