Algebraic Graph Theory Seminar - Qianqian YangExport this event to calendar

Monday, September 19, 2022 — 11:30 AM EDT

Title: Essential Covers of the Cube by Hyperplanes

Speaker: Igor Araujo
Affiliation: University of Illinois Urbana-Champaign
Location: contact Sabrina Lato for Zoom link

Abstract:  An essential cover of the vertices of the n-cube $\{0,1\}^n$ by hyperplanes is a minimal covering where no hyperplane is redundant, and every variable appears in the equation of at least one hyperplane. Linial and Radhakrishnan gave a construction of an essential cover with $\lceil \frac{n}{2} \rceil + 1$ hyperplanes and showed that $\Omega(\sqrt{n})$ hyperplanes are required. Recently, Yehuda and Yehudayoff improved the lower bound by showing that any essential cover of the $n$-cube contains at least $\Omega(n^{0.52})$ hyperplanes. Building on the method of Yehuda and Yehudayoff, we prove that $\Omega \left( \frac{n^{5/9}}{(\log n)^{4/9}} \right)$ hyperplanes are needed.

This is joint work with József Balogh and Letícia Mattos.

Event tags 

S M T W T F S
29
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
1
2
3
4
  1. 2023 (13)
    1. February (5)
    2. January (8)
  2. 2022 (150)
    1. December (8)
    2. November (18)
    3. October (15)
    4. September (11)
    5. August (2)
    6. July (17)
    7. June (17)
    8. May (10)
    9. April (12)
    10. March (18)
    11. February (10)
    12. January (13)
  3. 2021 (103)
  4. 2020 (119)
  5. 2019 (167)
  6. 2018 (136)
  7. 2017 (103)
  8. 2016 (137)
  9. 2015 (136)
  10. 2014 (88)
  11. 2013 (48)
  12. 2012 (39)
  13. 2011 (36)
  14. 2010 (40)
  15. 2009 (40)
  16. 2008 (39)
  17. 2007 (15)