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).
• Ramon van Handel, Princeton University
January 22, 2015 2:00 PM - 3:00 PM
Lind 305 [Map]

Abstract forthcoming.

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

Abstract forthcoming.

 Connect With Us: Go
 © 2014 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