HOME    »    PROGRAMS/ACTIVITIES    »    
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

    Mokshay Madiman, University of Delaware
    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

    Mokshay Madiman, University of Delaware
    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

    Gennadiy Chystyakov, Universität Bielefeld
    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.

Previous Annual Seminars

Connect With Us:
Go