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.
TBA
Jerrold Griggs, University of South Carolina
November 6, 2014 2:00 PM - 3:00 PM
Lind 305 [Map]Abstract forthcoming.
TBA
Penny Haxell, University of Waterloo
November 20, 2014 2:00 PM - 3:00 PM
Lind 305 [Map]Abstract forthcoming.
TBA
Ryan Martin, Iowa State University
December 4, 2014 2:00 PM - 3:00 PM
Lind 305 [Map]Abstract forthcoming.
Previous Annual Seminars