- You are here:
- GT Home
- Home
- News & Events

Series: Graph Theory Seminar

Many results in asymptotic extremal combinatorics are obtained using just a handful of instruments, such as induction and Cauchy-Schwarz inequality. The ingenuity lies in combining these tools in just the right way. Recently,
Razborov developed a flag calculus which captures many of the available techniques in pure form, and allows one, in particular, to computerize the search for the right combination. In this talk we outline the general approach and describe its application to the conjecture that a digraph with minimum outdegree n/3 contains a directed triangle. This special case of the Caccetta-Haggkvist conjecture has been extensively investigated in the past. We show that a digraph with minimum outdegree a*n contains a directed triangle for a = 0.3465. The proof builds on arguments used to establish previously known bounds, due to Shen from 1998 (a = 0.3542) and Hamburger, Haxell and Kostochka from 2008 (a = 0.3531). It consists of a combination of ~80 computer generated inequalities. Based on joint work with Jan Hladky and Daniel Kral.

Series: PDE Seminar

We discuss the global regularity vs. finite time breakdown in Eulerian dynamics, driven by different models of nonlinear forcing. Finite time breakdown depends on whether the initial configuration crosses intrinsic, O(1) critical thresholds (CT). Our approach is based on spectral dynamics, tracing the eigenvalues of the velocity gradient which determine the boundaries of CT surfaces in configuration space. We demonstrate this critical threshold phenomena with several n-dimensional prototype models. For n=2 we show that when rotational forcing dominates the pressure, it prolongs the life-span of sub-critical 2D shallow-water solutions. We present a stability theory for vanishing viscosity solutions of the 2D nonlinear "pressureless" convection. We revisit the 3D restricted Euler and Euler-Poisson equations, and obtain a surprising global existence result for a large set of sub-critical initial data in the 4D case.

On the theory and applications of the longtime dynamics of 3-dimensional fluid flows on thin domains

Series: CDSNS Colloquium

The current theory of global attractors for the Navier-Stokes equations on thin 3D domains is motivated by the desire to better understand the theory of heat transfer in the oceans of the Earth. (In this context, the thinness refers to the aspect ratio - depth divided by expanse - of the oceans.) The issue of heat transfer is, of course, closely connected with many of the major questions concerning the climate. In order to exploit the tools of modern dynamical systems in this study, one needs to know that the global attractors are "good" in the sense that the nonlinearities are Frechet differentiable on these attractors. About 20 years ago, it was discovered that on certain thin 3D domains, the Navier-Stokes equations did possess good global attractors. This discovery, which was itself a major milestone in the study of the 3D Navier-Stokes equations, left open the matter of extending the theory to cover oceanic-like regions with the appropriate physical boundary behavior. In this lecture, we will review this theory, and the connections with climate modeling, while placing special emphasis on the recent developments for fluid flows with the Navier (or slip) boundary conditions

Series: Stochastics Seminar

We consider Markovian tandem queues with finite intermediate buffers and flexible servers and study how the servers should be assigned dynamically to stations in order to obtain optimal long-run average throughput. We assume that each server can work on only one job at a time, that several servers can work together on a single job, and that the travel times between stations are negligible. Under various server collaboration schemes, we characterize the optimal server assignment policy for these systems.

Series: CDSNS Colloquium

Motivated by Smale's work on smooth dynamical systems, David Ruelle introduced the notion of Smale spaces. These are topological dynamical systems which are hyperbolic in the sense of having local coordinates of contracting and expending directions. These include hyperbolic automorphisms of tori, but typically, the spaces involved have a fractal nature. An important subclass are the shifts of finite type which are symbolic systems described by combinatorial data. These are also precisely the Smale spaces which are totally disconnected. Rufus Bowen showed that every Smale space is the image of shift of finite type under a finite-to-one factor map. In the 1970's, Wolfgang Krieger introduced a beautiful invariant for shifts of finite type. The aim of this talk is to show how a refined version of Bowen's theorem may be used to extend Krieger's invariant to all (irreducible) Smale spaces. The talk will assume no prior knowledge of these topics - we begin with a discussion of Smale spaces and shifts of finite type and then move on to Krieger's invariant and its extension.

Series: ACO Seminar

We consider the problem of a search engine trying to assign a sequence of search keywords to a set of competing bidders, each with a daily spending limit. The goal is to maximize the revenue generated by these keyword sales, bearing in mind that, as some bidders may eventually exceed their budget, not all keywords should be sold to the highest bidder. We assume that the sequence of keywords (or equivalently, of bids) is revealed on-line. Our concern will be the competitive ratio for this problem versus the off-line optimum.
We extend the current literature on this problem by considering the setting where the keywords arrive in a random order. In this setting we are able to achieve a competitive ratio of 1-\epsilon under some mild, but necessary, assumptions. In contrast, it is already known that when the keywords arrive in an adversarial order, the best competitive ratio is bounded away from 1. Our algorithm is motivated by PAC learning, and proceeds in two parts: a training phase, and an exploitation phase.
Joint work with Tom Hayes, UNM.

Series: Research Horizons Seminar

In this talk, I will present an brief introdution to use partial differential equation (PDE) and variational techniques (including techniques developed in computational fluid dynamics (CFD)) into wavelet transforms and Applications in Image Processing. Two different approaches are used as examples. One is PDE and variational frameworks for image reconstruction. The other one is an adaptive ENO wavelet transform designed by using ideas from Essentially Non-Oscillatory (ENO) schemes for numerical shock capturing.

Series: Combinatorics Seminar

Tolerance graphs were introduced in 1982 by Golumbic and Monma as a generalization of the class of interval graphs. A graph G= (V, E) is an interval graph if each vertex v \in V can be assigned a real interval I_v so that xy \in E(G) iff I_x \cap I_y \neq \emptyset. Interval graphs are important both because they arise in a variety of applications and also because some well-known recognition problems that are NP-complete for general graphs can be solved in polynomial time when restricted to the class of interval graphs. In certain applications it can be useful to allow a representation of a graph using real intervals in which there can be some overlap between the intervals assigned to non-adjacent vertices. This motivates the following definition: a graph G= (V, E) is a tolerance graph if each vertex v \in V can be assigned a real interval I_v and a positive tolerance t_v \in {\bf R} so that xy \in E(G) iff |I_x \cap I_y| \ge \min\{t_x,t_y\}. These topics can also be studied from the perspective of ordered sets, giving rise to the classes of Interval Orders and Tolerance Orders. In this talk we give an overview of work done in tolerance graphs and orders . We use hierarchy diagrams and geometric arguments as unifying themes.

Wednesday, March 11, 2009 - 11:00 ,
Location: Skiles 255 ,
Dirk Brockmann ,
Northwestern University ,
Organizer:

Human Mobility in our globalised world has reached a complexity and volume of unprecedented degree. More than 60 million people travel billions of kilometres on more than 2 million international flights each week. Hundreds of millions of people commute on a complex web of highways and railroads most of which operate at their maximum capacity. Human mobility is responsible for the geographical spread of emergent human infectious diseases and plays a key role in human mediated bioinvasion, the dominant factor in the global biodiversity crisis. I will report on the recent discovery of scaling laws in global human traffic (obtained from online bill-tracking at www.wheresgeorge.com) and mathematical models that can account for it. I will present a complex network perspective on multi-scale human traffic networks, report on their statistical properties and show that they can be used to identify geographically coherent communities that only vaguely resemble administrative ones. The approach provides an operational segmentation of maps into a hierarchical set of effective regions and boundaries based on human behavior. I will briefly talk about European transportation networks, geocaching and trackable items.

Series: PDE Seminar

We consider the the following fourth order degenerate parabolic equation h_t + (hh_xxx)_x = 0. The equation arises in the lubrication approximation regime, describing the spreading of a thin film liquid with height profile h >= 0 on a plate. We consider the equation as free boundary problem, defined on its positivity set. We address existence and regularity of classical solutions in weighted Hölder and Sobolev spaces.