Seminars and Colloquia by Series

Some Results on Linear Discrepancy for Partially Ordered Sets

Series
Dissertation Defense
Time
Thursday, October 1, 2009 - 14:00 for 2 hours
Location
Skiles 255
Speaker
Mitch Keller – School of Mathematics, Georgia Tech
Tanenbaum, Trenk, and Fishburn introduced the concept of linear discrepancy in 2001, proposing it as a way to measure a partially ordered set's distance from being a linear order. In addition to proving a number of results about linear discrepancy, they posed eight challenges and questions for future work. This dissertation completely resolves one of those challenges and makes contributions on two others. This dissertation has three principal components: 3-discrepancy irreducible posets of width 3, degree bounds, and online algorithms for linear discrepancy. The first principal component of this dissertation provides a forbidden subposet characterization of the posets with linear discrepancy equal to 2 by completing the determination of the posets that are 3-irreducible with respect to linear discrepancy. The second principal component concerns degree bounds for linear discrepancy and weak discrepancy, a parameter similar to linear discrepancy. Specifically, if every point of a poset is incomparable to at most \Delta other points of the poset, we prove three bounds: the linear discrepancy of an interval order is at most \Delta, with equality if and only if it contains an antichain of size \Delta+1; the linear discrepancy of a disconnected poset is at most \lfloor(3\Delta-1)/2\rfloor; and the weak discrepancy of a poset is at most \Delta-1. The third principal component of this dissertation incorporates another large area of research, that of online algorithms. We show that no online algorithm for linear discrepancy can be better than 3-competitive, even for the class of interval orders. We also give a 2-competitive online algorithm for linear discrepancy on semiorders and show that this algorithm is optimal.

Parabolic systems and an underlying Lagrangian

Series
Dissertation Defense
Time
Thursday, July 2, 2009 - 13:30 for 2.5 hours
Location
Skiles 255
Speaker
Turkay Yolcu – School of Mathematics, Georgia Tech
In this thesis, we extend De Giorgi's interpolation method to a class of parabolic equations which are not gradient flows but possess an entropy functional and an underlying Lagrangian. The new fact in the study is that not only the Lagrangian may depend on spatial variables, but also it does not induce a metric. Assuming the initial condition is a density function, not necessarily smooth, but solely of bounded first moments and finite entropy, we use a variational scheme to discretize the equation in time and construct approximate solutions. Moreover, De Giorgi's interpolation method reveals to be a powerful tool for proving convergence of our algorithm. Finally, we analyze uniqueness and stability of our solution in L^1.

Digital Chaotic Communications

Series
Dissertation Defense
Time
Wednesday, July 1, 2009 - 15:30 for 3 hours
Location
Skiles 255
Speaker
Alan J. Michaels – School of Electrical and Computer Engineering, Georgia Tech
This disseratation provides the conceptual development, modeling and simulation, physical implementation and measured hardware results for a procticable digital coherent chaotic communication system.

Some problems in the theory of open dynamical systemsand deterministic walks in random environments

Series
Dissertation Defense
Time
Monday, November 3, 2008 - 13:30 for 2 hours
Location
Skiles 114
Speaker
Alex Yurchenko – School of Mathematics, Georgia Tech
The first part of this work deals with open dynamical systems. A natural question of how the survival probability depends upon a position of a hole was seemingly never addresses in the theory of open dynamical systems. We found that this dependency could be very essential. The main results are related to the holes with equal sizes (measure) in the phase space of strongly chaotic maps. Take in each hole a periodic point of minimal period. Then the faster escape occurs through the hole where this minimal period assumes its maximal value. The results are valid for all finite times (starting with the minimal period), which is unusual in dynamical systems theory where typically statements are asymptotic when time tends to infinity. It seems obvious that the bigger the hole is the bigger is the escape through that hole. Our results demonstrate that generally it is not true, and that specific features of the dynamics may play a role comparable to the size of the hole. In the second part we consider some classes of cellular automata called Deterministic Walks in Random Environments on \mathbb Z^1. At first we deal with the system with constant rigidity and Markovian distribution of scatterers on \mathbb Z^1. It is shown that these systems have essentially the same properties as DWRE on \mathbb Z^1 with constant rigidity and independently distributed scatterers. Lastly, we consider a system with non-constant rigidity (so called process of aging) and independent distribution of scatterers. Asymptotic laws for the dynamics of perturbations propagating in such environments with aging are obtained.

Pages