Department of

Mathematics

Seminar Calendar
for events the day of Monday, February 3, 2014.

.
events for the
events containing

More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
     January 2014          February 2014            March 2014
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
1  2  3  4                      1                      1
5  6  7  8  9 10 11    2  3  4  5  6  7  8    2  3  4  5  6  7  8
12 13 14 15 16 17 18    9 10 11 12 13 14 15    9 10 11 12 13 14 15
19 20 21 22 23 24 25   16 17 18 19 20 21 22   16 17 18 19 20 21 22
26 27 28 29 30 31      23 24 25 26 27 28      23 24 25 26 27 28 29
30 31


Monday, February 3, 2014

2:00 pm in 147 Altgeld Hall,Monday, February 3, 2014

Approximation Algorithms for Euler Genus and Related Problems

Chandra Chekuri (UIUC CS)

Abstract: The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard [Thomassen 1989, 1993], and it is known to be fixed-parameter tractable; that is, for each fixed constant g, there is a polynomial time algorithm that decides whether a given graph G has Euler genus at most g. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O(sqrt(n))-approximation is known [Chen, Kanchi, and Kanevsky, 1997] even in bounded degree graphs. In this paper we give a polynomial-time algorithm which on input a bounded-degree graph of Euler genus g, computes a drawing into a surface of Euler genus g^O(1) * log^O(1) n. Combined with the upper bound from [Chen, Kanchi, and Kanevsky, 1997], our result also implies a O(n^(1/2 - alpha)-approximation, for some constant alpha>0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a unified fashion, algorithms with approximation ratios of the form OPT^O(1) * log^O(1) n for several related problems on bounded degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion problems. The talk will focus on the high-level tools for the genus computation coming from the seminal work on graph minors by Robertson and Seymour. Joint work with Anastasios Sidiropoulos.

3:00 pm in 145 Altgeld Hall,Monday, February 3, 2014

Imaginary time flow in geometric quantization and in Kahler geometry, degeneration to real polarizations and tropicalization

Jose Mourao (Instituto Superior Técnico)

Abstract: We will recall the problem of dependence of quantization of a symplectic manifold on the choice of polarization and study its relation with geodesics in the space Kahler metrics. Complex one parameter subgroups of the "group" of complexified hamiltonian symplectmorphisms appear naturally in this context. For some classes of symplectic manifolds we will describe geodesic rays of Kahler structures degenerating to real polarizations and study the associated metric collapse. Each such ray selects a basis of holomorphic sections which converge to distributional sections supported on Bohr-Sommerfeld fibers as the geodesic time goes to infinity. The same geodesic rays lead to tropicalization of toric varieties and of hypersurfaces on toric varieties.

4:00 pm in 245 Altgeld Hall,Monday, February 3, 2014

The minimum number of nonnegative edges in hypergraphs

Hao Huang (Institute for Advanced Study and DIMACS)

Abstract: Extremal combinatorics studies the maximum or minimum possible size of a combinatorial structure satisfying certain properties. In this talk I will review some results and recent developments in this field and their connections with other areas, and then focus on the following extremal problem. A hypergraph H is said to have the MMS property if for every assignment of weights to its vertices with nonnegative sum, the number of edges whose total weight is nonnegative is at least the minimum degree of H. We show that all sufficiently large hypergraphs with equal codegrees have the MMS property, and prove a long-standing conjecture by Manickam, Miklos, and Singhi as a corollary.

5:00 pm in 241 Altgeld,Monday, February 3, 2014