IMA Postdoc Seminars are given weekly throughout the fall and spring semesters. Postdocs present on a variety of mathematical topics that may be unrelated to the current annual program theme. IMA visitors and University of Minnesota faculty are also invited to present on subjects of interest.
Zach Hamaker of the University of Minnesota will be organizing the 2014-2015 seminar series.
Titles, abstracts, and speakers for each seminar will be posted as available.
All seminars are from 2:00pm -
3:00pm unless otherwise noted.
The Unconditional Case of the S-Inequality for Exponential Measure
Piotr Nayar, University of Minnesota Twin Cities
September 23, 2014
Lind 305 [Map]Abstract
Let m be the exponential distribution, i.e., the density of m is equal to 1/2^n exp(-(|x_1|+...+|x_n|)). Let K be an unconditional convex set and let P be a strip of the form [-p,p] times R^{n-1} with m(K)=m(P). We prove that m(tK) geq m(tP) for t>1.
This is a joint work with Tomasz Tkocz (University of Warwick).
Three Coloring the Discrete Torus
or
3-States Anti-Ferromagnetic Potts Model in Zero Temperature
Ohad Feldheim, University of Minnesota Twin Cities
October 7, 2014
Lind 305 [Map]Abstract
We prove that a uniformly chosen proper three coloring of Z_{2n}^d has a very rigid structure when the dimension d is sufficiently high.
In particular the coloring asymptotically almost surely takes one color on almost all of either the even or the odd sub-lattice.
This implies for example that one color appears on nearly half of the lattice sites.
This model is the zero temperature case of the 3-states anti-ferromagnetic Potts model, which has been studied extensively in statistical mechanics.
The result improves an independent bound due to Galvin, Kahn, Randall and Sorkin. The proof, however, is quite different:
using combinatorial methods which follow an algebraic-topological intuition, results of Peled about homomorphism height functions are extended to a new setting.
Joint work with Ron Peled.
Perfect Matchings in Dense Uniform Hypergraphs
Jie Han, Georgia State University
October 14, 2014
Lind 409 [Map]Abstract
In graph/hypergraph theory, perfect matchings are fundamental objects of study. Unlike the graph case, perfect matchings in hypergraphs have not been well understood yet. It is quite natural and desirable to extend the classical theory on perfect matchings from graphs to hypergraphs, as many important problems can be phrased in this framework, such as Ryser's conjecture on transversals in Latin squares and the Existence Conjecture for block designs. I will focus on Dirac-type conditions (minimum degree conditions) in uniform hypergraphs and discuss some recent progresses. In particular, we determine the minimum codegree threshold for the existence of a near perfect matching in hypergraphs, which confirms a conjecture of Rödl, Ruciński and Szemerédi, and we show that there is a polynomial-time algorithm that can determine whether a k-uniform hypergraph with minimum codegree n/k has a perfect matching, which solves a problem of Karpiński, Ruciński and Szymańska completely.
Finite Point Configurations and Fourier Analysis
Krystal Taylor, University of Minnesota Twin Cities
October 21, 2014
Lind 305 [Map]Abstract
We study the existence of certain geometric congurations in sub-
sets of Euclidean space. In particular, we establish that a set with
sufficient structure" contains an arbitrarily long chain with vertices
in the set and preassigned admissible gaps. A \(k\)-chain in \(E \subset \mathbb{R}^d\) with
gaps \( \left\{ t_i \right\}^k_{i=1} \) is a sequence
$$ \left\{ x^1, x^2, \dots, x^{k+1}, x^j, \subset E ; \left| x^{i+1} - x^{i} \right| = t_i; 1 \leq i \leq k \right\} . $$
In order to prove this result, we establish \( L^p(\mu) \rightarrow L^q(\nu) \) mapping
properties of the convolution operator \( T_\lambda f(x) = \lambda * (f\mu)(x) \); where \(\lambda\)
is a tempered distribution, and \(\mu\) and \(\nu\) are compactly supported measures satisfying the
growth bounds \( \mu(B(x, r)) \leq Cr^{s_\mu} \) and \( \nu(B(x,r)) \leq Cr^{s_\nu} \)
The Brunn-Minkowski Inequality - Its Refinements and Extensions
Arnaud Marsiglietti, University of Minnesota, Twin Cities
October 28, 2014
Abstract
The Brunn-Minkowski inequality, which states that for every non-empty
compact sets $A,B$ in $\R^n$ and every $\lambda \in [0,1]$ one has
$$ |(1-\lambda)A + \lambda B|^{1/n} \geq (1-\lambda)|A|^{1/n} + \lambda
|B|^{1/n}, $$
where $|.|$ denotes the volume (Lebesgue measure), is a fundamental
inequality in mathematics.
The aim of this talk is to present this inequality together with its
consequences, refinements and extensions.
Frozen Random Walk
Laura Florescu, New York University
November 4, 2014
Lind 305 [Map]Abstract
We explore a variant of the symmetric random walk on $\mathbb{Z}$ where particles are frozen if they are on the extreme quarter on any of the two sides. The motivation of this process arises from a theoretical computer science result related to the algorithm giving a 2 coloring of an $n$ set with all discrepancies less than $6 \sqrt{n}$. We are interested in the maximum of the process and the mass distribution. Related to this is a deterministic process where we start with mass $1$ at the origin, and at each step we freeze $1/2$ of the extremal mass and we split the remaining mass at each discrete point equally among its neighbors. Under the assumption that the scaled distribution converges, we determine the distribution, and the maximum $q\sqrt{t}$ where $q$ satisfies $\frac{1}{2}q^2=\frac{qe^{-q^2/2}}{\sqrt{2\pi}(\Phi(q)-\Phi(-q))}$. We present various simulation results supporting the claims of the existence of a scaling limit as well as the connection between the random and the deterministic process. We emphasize that in the deterministic case, the limit shape of the mass distribution is not a truncated Gaussian at the expected endpoints.
Joint work with Shirshendu Ganguly, Yuval Peres and Joel Spencer.
Bijections for Reduced Decompositions
Zachary Hamaker, University of Minnesota, Twin Cities
November 18, 2014
Lind 305 [Map]Abstract
We discuss enumerative theory for reduced decompositions of permutations and signed permutations. Particular focus will be paid to the Little map and insertion algorithms. These bijections allow for a refined study of combinatorial statistics for reduced decompositions.
Zykov's Symmetrization for Multiple Graphs with an Application to Erdos' Conjecture on Pentagonal Edges
Zeinab Maleki, Isfahan University of Technology
December 2, 2014
Lind 305 [Map]Abstract
Erd\H{o}s, Faudree, and Rousseau (1992) showed that a graph on $n$ vertices and at least $\lfloor n^2/4\rfloor+1$ edges has at least \lfloor n/2\rfloor+1$ edges on triangles. This result is sharp, just add an extra edge to the complete bipartite graph. In this talk, we give an asymptotic formula for the minimum number of edges contained on triangles in a graph having $n$ vertices and $e$ edges. The main tool of the proof is a generalization of Zykov's symmetrization that can be applied for several graphs simultaneously. We apply our weighted symmetrization method to tackle Erd\H{o}s' conjecture concerning the minimum number of edges on 5-cycles. Many problems remain open.
This is a joint work with Zolt\'{a}n F\"{u}redi.
Biclique Decomposition of Random Graphs
Hao Huang, University of Minnesota, Twin Cities
December 9, 2014
Lind 305 [Map]Abstract
The biclique partition number bp(G) is the minimum number of complete bipartite graphs needed to partition the edges of a graph G. It is not hard to see that bp(G) <= n-\alpha(G), where \alpha(G) is the independence number. Erdős conjectured that for the random graph G=G(n, 0.5), bp(G)=n-\alpha(G) with high probability. In this talk I will discuss some recent progress and and remaining challenges in this area, and show that actually there exists an absolute constant c>0 such that for G=G(n, 0.5), bp(G) <= n-(1+c)\alpha(G) with high probability. Joint work with Noga Alon and Tom Bohman.
Previous Postdoc Seminars