Annual Program Seminars

During each Annual Thematic Program, several seminars are offered. Talks will include graduate-level lectures as well as seminars covering various topics related to the theme.

• ## Measurable Equidecompositions via Combinatorics and Group Theory

Oleg Pikhurko, University of Warwick
September 18, 2014 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

Let n>2. We show that every two subsets of S^{n-1} (resp. two bounded subsets of R^n) of the same measure and with non-emtpy interior can be equidecomposed using pieces that are measurable. Joint work with Lukasz Grabowski and Andras Mathe.
• ## Infinite Geometric Graphs and Properties of Metrics

Jeannette Janssen, Dalhousie University
September 25, 2014 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

If the random graph model G(n,p) is extended to a countably infinite set, we obtain a unique graph (up to isomorphism), known as the Rado graph R. With my co-author Anthony Bonato, we aimed to take a similar approach in a geometric setting. Given a countable set of points in a metric space (R^n, d), two points are made adjacent with probability p if their distance is at most 1. For certain metrics, this leads to a unique isomorphism type. Moreover, the graph has a deterministic construction. For other metrics, we obtain infinitely many isomorphism types. The dichotomy hangs on a particular rounding property of metrics.
• ## Nordhaus-Gaddum Sum Problems for Tree-width and Colin de Verdière Parameters

Leslie Hogben, Iowa State University
October 9, 2014 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

A Nordhaus-Gaddum sum problem for a graph parameter is to determine a tight lower or upper bound for the sum of the parameter evaluated on a graph and on its complement. This talk will survey Nordhaus-Gaddum sum results and open questions for tree-width, the Colin de Verdière type parameters µ and ν, and related parameters (all of the parameters discussed will be defined).

The tight lower bound for tree-width is tw(G)+tw(Ḡ) ≥ |G|- 2: It has been conjectured that µ(G) + µ(Ḡ) ≥ |G| ≥ - 2 and ν(G) + ν(Ḡ) ≥ |G| - 2: Partial results and other evidence for these conjectures will be discussed.

Upper and lower bounds on the Nordhaus-Gaddum upper multiplier b, where ν(G) + ν(Ḡ) ≤ bν|G| for all G, will also be discussed, together with questions about bounds on upper multipliers for the other parameters.
• ## A Discrete Isodiametric Result: The Erdos-Ko-Rado Theorem for Multisets

Zoltan Furedi, Hungarian Academy of Sciences (MTA)
October 16, 2014 2:00 PM - 3:00 PM
Lind 409 [Map]

### Abstract

There are many generalizations of the EKR theorem. We give new results (and problems) and point out connections to coding theory and geometry.

A joint work with D. Gerbner and M. Vizer.
• ## Fractional Subadditivity of Entropy and Applications

Prasad Tetali, Georgia Institute of Technology
October 23, 2014 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

Subadditivity of Shannon's entropy (of a collection of random variables) is a simple, yet powerful property, perhaps much like the linearity of expectation. This will be an expository lecture on Shearer's (fractional) subadditivity of entropy lemma and its various applications -- enumerative and extremal results -- by various researchers. Some open problems will also be mentioned.
• ## Discrete Morse Theory from A Graph Matching Perspective

Patricia Hersh, North Carolina State University
October 30, 2014 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

Robin Forman introduced a discrete version of Morse theory as a way of studying topological structure (e.g. Betti numbers and homotopy type) of simplicial complexes and of more general finite CW complexes. Chari observed that to construct a discrete Morse function, it suffices to find a certain type of graph theoretic matching on the Hasse diagram of the face poset of the complex of interest. Soon thereafter, numerous applications began to be found by an assortment of people, most (if not all) of which boiled down to finding suitable graph theoretic matchings. I will give an overview of this area, including joint work with Eric Babson regarding order complexes of partially ordered sets. Background in topological combinatorics will not be assumed.
• ## Counting Connected Hypergraphs - Phase Transitions, Martingales and Branching Processes

Béla Bollobás, University of Memphis
November 5, 2014 11:15 AM - 12:15 PM
Lind 305 [Map]

### Abstract

Abstract available as a PDF here
• ## Poset-free Families of Subset

Jerrold Griggs, University of South Carolina
November 6, 2014 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

Given a finite poset P, we consider the largest size La(n,P) of a family of subsets of [n]:={1,...,n} that contains no (weak) subposet P. Early theorems of Sperner and Katona solve this problem when P is the k-element chain (path poset) P_k, where it is the sum of the middle k-1 binomial coefficients in n. Katona and his collaborators investigated La(n,P) for other posets P. It can be very challenging, even for small posets.

Based on results to date, G. and Lu (2008) conjecture that pi(P), which is the limit as n goes to infinity, of La(n,P)/{n\choose{n/2}}, exists for general posets P. Moreover, it is an integer obtained in a specific way. For k at least 2 let D_k denote the k-diamond poset {A< B_1,...,B_k < C}. Using probabilistic reasoning to bound the average number of times a random full chain meets a P-free family F, called the Lubell function of F, we prove with Li and Lu that pi(D_2)<2.273, if it exists. This is a stubborn open problem, since we expect pi(D_2)=2. Kramer, Martin, and Young have the current best bound, 2.25. It is then surprising that, with appropriate partitions of the set of full chains, we can explicitly determine pi(D_k) for infinitely many values of k, and, moreover, describe the extremal D_k-free families. With Li we develop a theory of poset properties that verifies the conjecture for many more posets, though for most P, it seems that La(n,P) is far more complicated.
• ## Edge Colouring Multigraphs

Penny Haxell, University of Waterloo
November 20, 2014 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

The chromatic index of a multigraph G is the smallest k such that the edges of G can be coloured with k colours so that no two edges of the same colour share a vertex. It is easy to see that the chromatic index of G is at least the maximum degree d, and it can be as large as 3d/2.

An old conjecture due to Goldberg and (independently) Seymour essentially states that if a multigraph has chromatic index d+k > d+1 then it must contain a small odd subset S of vertices that induces too many edges to be coloured with d+k colours. This talk will report on recent joint work with Hal Kierstead proving a weakened version of this statement, and describe an important tool for studying edge colourings (the method of Tashkinov trees).
• ## On the Edit Distance in Graphs

Ryan Martin, Iowa State University
December 4, 2014 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

The edit distance function, a function of a hereditary property $\mathcal{H}$ and of $p$, which measures the maximum proportion of edges in a density-$p$ graph that need to be inserted/deleted in order to transform it into a member of $\mathcal{H}$. We will survey the topic and describe symmetrization, a method that can be used in computing this function and we will give some results that have been attained using it. The edit distance problem has applications in property testing and evolutionary biology and is closely related to well-studied Tur\'an-type problems. Some of the more intriguing results will show a close relationship between the problem of Zarankiewicz as well as strongly regular graphs. This is a survey including joint work with Maria Axenovich (Karlsruhe), J\'ozsef Balogh (Illinois), Andr\'e K\'ezdy (Louisville), Tracy McKay (Dickinson College) and Chelsea Peck (ISU).
• ## Asymptotic Analysis Seminar: How large is the norm of a random matrix?

Ramon van Handel, Princeton University
January 20, 2015 11:00 AM - 12:00 PM
Lind 305 [Map]

### Abstract

Even a problem as simple as estimating the expected spectral norm of a Gaussian random matrix remains surprisingly mysterious. In this informal talk, I will discuss recent results on the norm of random matrices with independent entries that are nearly sharp and that drastically improve on previously known results. More importantly, I will emphasize a number of interesting open problems that arise from this work, whose resolution would appear to require some novel analytic and combinatorial ideas.
• ## Asymptotic Analysis Seminar: How large is the norm of a random matrix? II

Ramon van Handel, Princeton University
January 27, 2015 11:00 AM - 12:00 PM
Lind 305 [Map]

### Abstract

Even a problem as simple as estimating the expected spectral norm of a Gaussian random matrix remains surprisingly mysterious. In this informal talk, I will discuss recent results on the norm of random matrices with independent entries that are nearly sharp and that drastically improve on previously known results. More importantly, I will emphasize a number of interesting open problems that arise from this work, whose resolution would appear to require some novel analytic and combinatorial ideas.
• ## An Introduction to the Normalized Laplacian

Steve Butler, Iowa State University
January 29, 2015 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

We can store the data about a graph using a matrix, and an understanding of that matrix can in turn help us to understand the properties of the graph. There are many possible matrices that can be used, each with its own strength and limitations. We will give an overview of the most popular matrices and then focus on some properties of the normalized Laplacian. In particular we will look at edge discrepancy and ways to form cospectral graphs.
• ## Asymptotic Analysis Seminar: Approximation of Convex Bodies

Elisabeth Werner, University of Minnesota, Twin Cities
February 3, 2015 11:00 AM - 12:00 PM
Lind 305 [Map]

### Abstract

How well can a convex body be approximated by a polytope? This is a central question in convex geometry which has been widely studied. We will discuss several aspects of this question and will present in detail two of them: One about approximation of a convex body with a fixed number of vertices. The second about approximation of polytopes by smooth bodies.
• ## Between the Number of Edges and the Adjacency Matrix of a Graph

Eva Czabarka, University of South Carolina
February 5, 2015 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

Havel and Hakimi provided a characterization of graphical degree sequences, i.e. finite sequences of nonnegative integers that can be realized as degree sequences of simple graphs. Their result led to a simple edge-swap operation that keeps the space of the graphs with a given degree sequence connected and thus gives a natural basis for Markov chain on this space. Given a partition of the vertex set of a graph, the corresponding partition adjacency matrix contains in the ij-th position the number of edges that connect vertices of the i-th and j-th partition class (this would be the number of edges and the adjacency matrix for the two trivial partitions). I will present Havel-Hakimi type results and open problems related to partition adjacency matrices.
• ## Asymptotic Analysis Seminar: Approximation of Convex Bodies II

Elisabeth Werner, University of Minnesota, Twin Cities
February 10, 2015 11:00 AM - 12:00 PM
Lind 305 [Map]

### Abstract

How well can a convex body be approximated by a polytope? This is a central question in convex geometry which has been widely studied. We will discuss several aspects of this question and will present in detail two of them: One about approximation of a convex body with a fixed number of vertices. The second about approximation of polytopes by smooth bodies.
• ## Discrete Entropy Power Inequalities and Sperner Theory

February 12, 2015 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

The entropy power inequality provides a sharp lower bound on the entropy of the sum of two independent real-valued random variables, and is an important and basic inequality in information theory and probability. Despite several efforts,only partial results exists for the analogous problem in discrete groups such as the integers. We will describe several analogues of the entropy power inequality for integer-valued random variables, using various notions of symmetrization as well as ideas from Sperner theory (related to large antichains in posets). If time permits, we will also discuss the case of random variables taking values in cyclic groups of prime order. Joint work with Liyao Wang and Jae Oh Woo.
• ## Asymptotic Analysis Seminar: Affine Invariant Points

Carsten Schuett, Christian-Albrechts Universität Kiel
February 17, 2015 11:00 AM - 12:00 PM
Lind 305 [Map]

Abstract forthcoming.

• ## Quantitative Uniform Convexity Bounds and their Application

Eric Carlen, Rutgers, The State University Of New Jersey
February 19, 2015 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

Quantitative uniform convexity bounds for the unit ball in a Banach space have many applications. The sharp 2-uniform convexity bounds for the Schatten trace norms (tracial analogs of the L^p norms) we proven by Ball, Lieb and myself, and were applied by Lieb and myself to prove a conjecture of Gross on hypercontractivity. The sharp form of this inequality has found many applications since then, including in my own more recent work. Certain of these applications, along with open problems, will be discussed.
• ## Asymptotic Analysis Seminar: Optimal Concentration of Information for Log-Concave Distributions

March 3, 2015 11:00 AM - 12:00 PM
Lind 305 [Map]

### Abstract

Recently it was shown by Bobkov and the speaker that for a random vector X in R^n drawn from a log-concave density e^{-V}, the information content per coordinate, namely V(X)/n, is highly concentrated about its mean. Their argument was nontrivial, involving the localization technique, and also gave suboptimal exponents, but it was sufficient to demonstrate that high-dimensional log-concave measures are in a sense close to uniform distributions on the annulus between 2 nested convex sets. We will show that one can obtain an optimal concentration bound in this setting (optimal even in the constant terms, not just the exponent), using very simple techniques, and give a complete proof. We will also mention some applications, including to random matrix theory. This is joint work with Matthieu Fradelizi and Liyao Wang.
• ## Kantorovitch Duality for General Transport Costs and Applications

Cyril Roberto, Université Paris Ouest
March 5, 2015 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

We will introduce a general notion of transport cost that encompasses many costs used in the literature (including the classical one and weak transport costs introduced by Talagrand and Marton in the 90’s), and present (without proof) a Kantorovich type duality theorem. Such a duality has many applications. We may present one of them related to the equivalence between some transport-entropy inequality and the log-Sobolev inequality restricted to convex functions. Joint work with Nathael Gozlan, Paul-Marie Samson, Yan Shu and Prasad Tetali.
• ## Asymptotic Analysis Seminar: Approximation Complexity of Convex Bodies

Mark Rudelson, University of Michigan
March 10, 2015 11:00 AM - 12:00 PM
Lind 305 [Map]

### Abstract

Consider the approximation of an n-dimensional convex body by a projection of a section of an N-dimensional simplex, and call the minimal N for which such approximation exists the approximation complexity of the body. The reason for such strange definition lies in computer science. A projection of a section of a simplex is the feasible set of a linear programming problem, and so it can be efficiently generated. We will discuss how large the approximation complexity of different classes of convex bodies can be.
• ## Asymptotic Approximations for Symmetric Functions and the Central Limit Theorem for Densities

Friedrich Götze, Universität Bielefeld
March 12, 2015 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

We discuss a general principle of deriving asymptotic approximations for sequences of symmetric functions. We illustrate this general scheme of Edgeworth-type expansions by examples involving densities in classical as well as free Probability. This is joint work with G. Chistyakov, A. Naumov, A. Reshetenko and V. Ulyanov.
• ## Asymptotic Analysis Seminar: On a Loomis-Whitney Type Inequality for Permutationally Invariant Unconditional Convex Bodies

Piotr Nayar, University of Minnesota, Twin Cities
March 24, 2015 11:00 AM - 12:00 PM
Lind 305 [Map]

### Abstract

For a permutationally invariant unconditional convex body K in R^n we define a finite sequence (K_j) of projections of the body K to the space spanned by first j vectors of the standard basis of R^n. We prove that the sequence of volumes (|K_j|) is log-concave, i.e., |K_j|^2 \geq |K_{j-1}||K_{j+1}|. Joint work with Tomasz Tkocz.
• ## Perfect Matchings and Random Determinants

Mark Rudelson, University of Michigan
March 26, 2015 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

Consider a graph with an even number of vertices. A perfect matching is a splitting of the set of vertices into pairs such that each pair is connected by an edge. The only known polynomial time estimator for the number of perfect matchings was constructed by Barvinok. It estimates this number via the determinant of the random matrix associated to the graph. Barvinok proved that the multiplicative error of this estimator is at most exponential, and this result cannot be improved for general graphs. We provide conditions on the graph, under which the Barvinok estimator yields a subexponential error. Joint work with Alex Samorodnitsky and Ofer Zeitouni.
• ## Asymptotic Analysis Seminar: Random Walks on High Dimensional Spheres: Spectral Gaps and Entropy Production

Eric Carlen, Rutgers, The State University Of New Jersey
March 31, 2015 11:00 AM - 12:00 PM
Lind 305 [Map]

### Abstract

We discuss random walks on high dimensional sphere and related spaces such as SO(N) for large N, and geometric inequalities governing the rates of equilbriation.
• ## Limit Theorems in Free Probability Theory

April 2, 2015 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

Based on an analytical approach to the definition of additive free convolution on probability measures on the real line we prove free analogs of limit theorems for sums of independent random variables in classical probability theory. We prove as well free analog of bounds for approximation of n-fold convolutions of probability measures with infinitely divisible probability measures.
• ## Asymptotic Analysis Seminar: Algebraic Structures on the Family of Convex Sets

Liran Rotem, Tel Aviv University
April 7, 2015 11:00 AM - 12:00 PM
Lind 305 [Map]

### Abstract

In the first part of the talk we will discuss different addition operations between convex sets. The main goal of this part would be to understand which properties of the Minkowski addition characterize it uniquely. In the second part we will present a new construction for the geometric mean of two convex bodies, and prove some of its properties. We will also explain the relationship between this construction and the log-Brunn-Minkowski conjecture, and discuss some open problems. Based on joint works with Vitali Milman.
• ## Stein Couplings, Log Concavity and Concentration of Measure

Larry Goldstein, University of Southern California
April 9, 2015 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

For a nonnegative random variable Y with finite nonzero mean \mu, we say that Y^s has the Y-size bias distribution if E[Yf(Y)] = \mu E[f(Y^s)] for all bounded, measurable f. If Y can be coupled to Y^s having the Y-size bias distribution such that for some constant c we have Y^s <= Y + c almost surely, then Y satisfies a `Poisson tail' concentration of measure inequality. These methods yield concentration results for examples including urn occupancy statistics for multinomial allocation models and Germ-Grain models in stochastic geometry, which are members of a class of models with log concave marginals for which size bias couplings may be constructed more generally. Similarly, concentration bounds can be shown when one can construct a bounded zero bias coupling of a mean zero random variable Y with finite nonzero variance \sigma^2 to a Y^* satisfying E[Yf(Y)] = \sigma^2 E[f'(Y^*)] for all smooth f. These couplings can be used to demonstrate concentration in Hoeffding's combinatorial central limit theorem under diverse assumptions on the permutation distribution. The bounds produced by these couplings, which have their origin in Stein's method, offer improvements over those obtained by using other methods available in the literature. This work is joint with Jay Bartroff and Umit Islak.
• ## Asymptotic Analysis Seminar: Smoothing and Ergodicity of Markov Semigroups in Infinite Dimensions

Boguslaw Zegarlinski, Imperial College London
April 21, 2015 11:00 AM - 12:00 PM
Lind 305 [Map]

### Abstract

This talk will be about applications of techniques based on generalized gradient bounds.
• ## Borell's Formula for a Riemannian Manifold

Joseph Lehec, Université de Paris IX (Paris-Dauphine)
April 23, 2015 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

Borell's formula is a stochastic variational formula for the log-Laplace transform of a function of a Gaussian vector. We shall present an extension of this to the Riemannian setting. As an application we will give a new proof of the Brascamp-Lieb inequality on the sphere (due to Carlen, Lieb and Loss).
• ## Vertex Index of Symmetric Convex Bodies

Alexander Litvak, University of Alberta
May 7, 2015 2:00 PM - 3:00 PM
Lind 305 [Map]

### Abstract

We discuss several results on the vertex index of a given $d$-dimensional centrally symmetric convex body, which, in a sense, measures how well the body can be inscribed into a convex polytope with small number of vertices. This index is closely connected to the illumination parameter of a body, introduced earlier by Karoly Bezdek, and, thus, related to the famous conjecture in Convex Geometry about covering of a $d$-dimensional body by $2^d$ smaller positively homothetic copies. We provide estimates of this index and relate the lower bound with the outer volume ratio. We also discuss sharpness of the bounds, providing examples. The talk is based on joint works with K.Bezdek and E.D.Gluskin.
 Connect With Us: Go
 © 2015 Regents of the University of Minnesota. All rights reserved. The University of Minnesota is an equal opportunity educator and employer Last modified on October 06, 2011 Twin Cities Campus:   Parking & Transportation   Maps & Directions Directories   Contact U of M   Privacy