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

February 17, 2015 11:00 AM - 12:00 PM
Lind 305 [Map]

Abstract

Carsten Schuett, University of Kiel
• 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.
 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