Department of

# Mathematics

Seminar Calendar
for events the day of Tuesday, March 18, 2014.

.
events for the
events containing

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


Tuesday, March 18, 2014

1:00 pm in Altgeld Hall 243,Tuesday, March 18, 2014

#### Fundamental groups of certain elliptic manifolds

###### Pekka Pankka (University of Jyväskylä)

Abstract: By Varopoulos' theorem, the fundamental group of a closed quasiregularly elliptic n-manifold (i.e. a manifold receiving a quasiregular map from the Euclidean n-space) has polynomial order of growth at most n. Thus, by Gromov's theorem, these groups are virtually nilpotent. The existence of the map can, however, be used to obtain further information on the fundamental group. I will discuss two recent results: (1) a result with Rami Luisto showing that maximal growth of the group implies the group to be virtually abelian; (2) a result with Enrico Le Donne showing that fundamental groups of closed BLD-elliptic manifolds are (in fact) always virtually abelian.

2:00 pm in 241 Altgeld Hall,Tuesday, March 18, 2014

#### Extreme amenability and finite oscillation stability

###### Aristotelis Panagiotopoulos (UIUC Math)

Abstract: A Polish group is called extremely amenable if every continuous action of it on a compact Hausdorff space has a fixed point. Examples include large groups such as the unitary group of a separable Hilbert space and the group of measure-preserving automorphisms of a standard probability space. Following Pestov's "Dynamics of Infinite-dimensional Groups", we will show that extreme amenability is equivalent to a Ramsey-theoretic condition on the group called finite oscillation stability.

2:00 pm in Altgeld Hall 347,Tuesday, March 18, 2014

#### From Large Deviations to Statistical Mechanics: What Is the Most Likely Way for an Unlikely Event To Happen?

###### Richard Ellis (U Mass Amherst)

Abstract: This talk is an introduction to the theory of large deviations, which studies the asymptotic behavior of probabilities of rare events. The talk is accessible to a general audience including graduate students in mathematics and physics. The theory of large deviations has its roots in the work of Ludwig Boltzmann, the founder of statistical mechanics. In 1877 he did the first large deviation calculation in science when he showed that large deviation probabilities of the empirical vector could be expressed in terms of the relative entropy function. In this talk Boltzmann's insight is applied to prove a conditional limit theorem that addresses a basic issue arising in mathematics, statistical mechanics, and other applications. What is the most likely way for an unlikely event to happen? This question is answered in the context of $n$ tosses of a cubic die and other random experiments involving finitely many outcomes. Let $X_i$ denote the outcome of the $i$'th toss and define $S_n = X_1 + \ldots + X_n$. If the die were fair, then one would expect that for large $n$, $S_n/n$ should be close to the theoretical mean of 3.5. Given that $S_n/n$ is close to a number $z$ not equal to 3.5, the problem is to compute, in the limit $n \to \infty$, the distribution of $X_1$; i.e., the probability of obtaining 1, 2, 3, 4, 5, 6 on a single toss. Interestingly, this conditional limit theorem is intimately related to statistical mechanics because it gives a rigorous derivation, for a random ideal gas, of a basic construction due to Gibbs; namely, the form of the canonical ensemble from the microcanonical ensemble. A related conditional limit theorem for the distribution of $X_1$, $X_2$ illustrates the phenomenon of propagation of chaos.

3:00 pm in 241 Altgeld Hall,Tuesday, March 18, 2014

#### Tree Search Problem with Non-uniform Costs

###### Bernard Lidicky   [email] (UIUC Math)

Abstract: In this talk we consider the problem of identifying an initially unknown vertex in a tree by asking edge queries: an edge query $e$ returns the component of $T-e$ containing the vertex sought for, while incurring some known cost $c(e)$. The Tree Search Problem with Non-Uniform Cost is: given a tree $T$ where each edge $e$ has an associated cost $c(e)$, construct a strategy that minimizes the total cost of the identification in the worst case. Finding the strategy guaranteeing the minimum possible cost is an NP-complete problem already for input tree of degree 3 or diameter 6. The best known approximation guarantee is the $O(\log n/(\log \log \log n))$-approximation algorithm by Cicalese et al. We improve upon the above results both from the algorithmic and the computational complexity point of view: We provide a novel algorithm that provides an \$O(\log n/(\log \log n))-approximation of the cost of the optimal strategy. In addition, we show that finding an optimal strategy is NP-complete even when the input tree is a spider, i.e., at most one vertex has degree larger than 2. This is a joint work with Ferdinando Cicalese, Balazs Keszegh, Domotor Palvolgyi and Tomas Valla.