ترجمه فارسی مقاله حداکثر خرد شدن

چکیده

A family $\mathcal{F}$ of subsets of $[n]=\{1,2,\ldots,n\}$ shatters a set $A \subseteq [n]$ if for every $A’ \subseteq A$ there is an $F \in \mathcal{F}$ such that $F \cap A=A’$. What is the maximum possible number of subsets of $[n]$ of size $d$ that can be shattered by a family of size $k$? Denote this number by $f(n,k,d)$. We determine $f(n,2^d,d)$ precisely whenever $2^d-1$ divides $n$, showing that this number is $\frac{c_d}{d!}n^d$, where $c_d$ is the probability that $d$ independent uniformly random vectors in $\mathbb{F}_2^d \setminus \{0\}$ are linearly independent. We also show that if $d$ and $n$ grow, with both $d$ and $n-d$ tending to infinity, then $f(n,2^d,d)=(1+o(1))c\binom{n}{d}$, where $c$, roughly $0.289$, is the limit of $c_d$ as $d$ tends to infinity. The case $k>2^d$ is considered as well; for $d \leq 2$ we determine $f(n,k,d)$ precisely for all $n$ and $k$, but the case $d \geq 3$ and $k>2^d$ is much less understood.

چکیده به فارسی (ترجمه ماشینی)

یک خانواده $ \ mathcal {f} $ زیر مجموعه های $ [n] = \ {1،2 ، \ ldots ، n \} $ یک مجموعه $ a \ subseteq [n] $ را خرد می کند اگر برای هر $ a ‘\ subseteq a$ یک $ f \ in \ mathcal {f} $ وجود دارد به گونه ای که $ f \ cap a = a ‘$.حداکثر تعداد ممکن زیر مجموعه های $ [n] $ با اندازه d $ که می تواند توسط خانواده ای با اندازه $ k $ خرد شود چیست؟این شماره را با $ f (n ، k ، d) $ مشخص کنید.ما $ f (n ، 2^d ، d) $ را دقیقاً هر زمان که 2^d-1 $ تقسیم می شود $ n $ تعیین می کنیم ، نشان می دهد که این شماره $ \ frac {c_d} {d!} n^d $ است ، جایی که $ c_d$ این احتمال است که $ d $ بردار یکنواخت تصادفی در $ \ mathbb {f} _2^d \ setminus \ {0 \} $ بطور خطی مستقل باشد.ما همچنین نشان می دهیم که اگر $ d $ و $ n $ رشد کنند ، با هر دو $ d $ و $ n-d $ تمایل به بی نهایت ، سپس $ f (n ، 2^d ، d) = (1+o (1)) c \binom {n} {d} $ ، جایی که $ c $ ، تقریباً 0.289 $ $ ، حد $ c_d $ است زیرا $ d $ تمایل به بی نهایت دارد.مورد $ k> 2^d $ نیز در نظر گرفته شده است.برای $ d \ leq 2 $ ما $ f (n ، k ، d) $ را دقیقاً برای همه $ n $ و $ k $ تعیین می کنیم ، اما مورد $ d \ geq 3 $ و $ k> 2^d $ بسیار کمتر استفهمیده