Events by date

Title: Enumerating hereditary classes of chord diagrams

Speaker: Lukas Nabergall Affiliation: University of Waterloo Zoom: Contact Stephen Melczer

Abstract:

A class of combinatorial structures is hereditary if membership in the class is closed under taking substructures. Hereditary classes have been extensively studied for a variety of objects, notably graphs and permutations. A central problem is to determine the number of objects of size n in a given hereditary class. We discuss this problem for chord diagrams, perfect matchings of [2n].

Title: Counting Antichains in the Boolean Lattice

Speaker: Shayla Redlin Affiliation: University of Waterloo Zoom: Contact Maxwell Levit

Abstract:

How many antichains are there in the Boolean lattice P(n)? Sperner's theorem (1928) tells us that the largest antichain in P(n) has size A = (n choose n/2). A subset of an antichain is an antichain, so there are at least 2^A antichains in P(n). Interestingly, it turns out that this is close to the total, as Kleitman (1969) showed that the number of antichains is 2^(A(1+x)) where x goes to zero as n goes to infinity.