2023. 11. 30. 12:15 - 2023. 11. 30. 13:30
Rényi, Nagyterem + Zoom
-
-
-
-
Esemény típusa: szeminárium
Szervezés: Intézeti
-
Extremális halmazrendszerek szeminárium

Leírás

Abstract: Let ${\rm sat}(n,k)$ denote the minimum size of a family in
the Boolean lattice of dimension $n$ with the property that there is
no chain with $k+1$ elements but the addition of one more element to
the family produces such a chain. It is well known that for $n$
sufficiently large, ${\rm sat}(n,k)$ is the same value, which we
denote ${\rm sat}(k)$.

For $k\geq 6$, the best known bounds are
$$ 2^{k/2-1}\leq {\rm sat}(k,n)\leq 2^{(1-0.023)k} , $$
due to Gerbner, Keszegh, Lemons, Palmer, P\'alv\"olgyi, and Patk\'os
and to Morrison, Noel and Scott (based on a construction by Gerbner,
et al.), respectively.

We improve both bounds to
$$ 2^{(k-3)/2+(1/2)\log_2(k-1)}\leq {\rm sat}(k,n)\leq 2^{(1-0.049)k}. $$
The upper bound works for $k\geq 7$ and the lower bound for $k\geq
483$.

This is joint work with Nick Veldt, Iowa State University.

 

The lecture can be followed by zoom if necessary: