University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Joint Pure Math/C&O Grad ColloquiumExport this event to calendar

Thursday, June 10, 2021 — 4:00 PM EDT

Shayla Redlin, Department of Combinatorics & Optimization, University of Waterloo

"Counting Antichains in the Boolean Lattice"

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. In this talk, we investigate an alternate proof that uses the 'container method'. Although the container method is a graph theoretic technique, a background in graph theory is not assumed.

Zoom link: https://us02web.zoom.us/j/81243444090?pwd=S2NLODVCZHoyRUFqTXpZQ1V6UjNmdz09

Event tags 

S M T W T F S
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
  1. 2021 (43)
    1. June (8)
    2. May (1)
    3. April (4)
    4. March (11)
    5. February (9)
    6. January (10)
  2. 2020 (103)
    1. December (10)
    2. November (12)
    3. October (4)
    4. September (3)
    5. August (1)
    6. July (5)
    7. June (1)
    8. May (3)
    9. March (16)
    10. February (26)
    11. January (22)
  3. 2019 (199)
  4. 2018 (212)
  5. 2017 (281)
  6. 2016 (335)
  7. 2015 (211)
  8. 2014 (235)
  9. 2013 (251)
  10. 2012 (135)