# 학과 세미나 및 콜로퀴엄

2024-01
Sun Mon Tue Wed Thu Fri Sat
1 2 3 4 5 6
7 8 9 10 11 1 12 13
14 15 16 17 18 19 20
21 22 23 1 24 25 26 27
28 29 30 31
2024-02
Sun Mon Tue Wed Thu Fri Sat
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

로그인 시, 세미나를 이메일로 구독할 수 있습니다.

The Dedekind's Problem asks the number of monotone Boolean functions, a(n), on n variables. Equivalently, a(n) is the number of antichains in the n-dimensional Boolean lattice $^n$. While the exact formula for the Dedekind number a(n) is still unknown, its asymptotic formula has been well-studied. Since any subsets of a middle layer of the Boolean lattice is an antichain, the logarithm of a(n) is trivially bounded below by the size of the middle layer. In the 1960's, Kleitman proved that this trivial lower bound is optimal in the logarithmic scale, and the actual asymptotics was also proved by Korshunov in 1980’s. In this talk, we will discuss recent developments on some variants of Dedekind's Problem. Based on joint works with Matthew Jenssen, Alex Malekshahian, Michail Sarantis, and Prasad Tetali.
Host: Sang-il Oum     영어     2023-11-17 01:04:41
For any finite point set $P \subset \mathbb{R}^d$, we denote by $\text{diam}(P)$ the ratio of the largest to the smallest distances between pairs of points in $P$. Let $c_{d, \alpha}(n)$ be the largest integer $c$ such that any $n$-point set $P \subset \mathbb{R}^d$ in general position, satisfying $\text{diam}(P) < \alpha\sqrt[d]{n}$ (informally speaking, `non-elongated'), contains a convex $c$-polytope. Valtr proved that $c_{2, \alpha}(n) \approx \sqrt{n}$, which is asymptotically tight in the plane. We generalize the results by establishing $c_{d, \alpha}(n) \approx n^{\frac{d-1}{d+1}}$. Along the way we generalize the definitions and analysis of convex cups and caps to higher dimensions, which may be of independent interest. Joint work with Boris Bukh.
Host: Sang-il Oum     영어     2023-11-20 21:47:45