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]


    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]


    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]


    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]


    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]


    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]


    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 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]


    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]


    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]


    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).
  • Conditional Ergodicity

    Ramon van Handel, Princeton University
    January 22, 2015 2:00 PM - 3:00 PM
    Lind 305 [Map]


    What probabilistic phenomena can arise when a random system is conditioned on partial information? Such questions are of fundamental interest to the understanding of conditional distributions, and at the same time have implications for applications ranging from GPS navigation to weather forecasting. A general understanding of classical problems of this kind, dating back at least to Blackwell (1957), has only recently been obtained. At the same time, new questions and phenomena that arise in high-dimensional problems, such as conditional phase transitions and decay of correlations, are only beginning to be addressed. I will give an overview of some old and new problems in this area, with emphasis on the behavior of conditional distributions in high dimension and connections with statistical mechanics and multidimensional ergodic theory.
  • An Introduction to the Normalized Laplacian

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


    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.

Previous Annual Seminars

Connect With Us: