论文标题
关于集合痕迹的极端问题
On extremal problems concerning the traces of sets
论文作者
论文摘要
给定两个非负整数$ n $和$ s $，定义$ m（n，s）$是最大数字，以至于每一个$ n $ dertices上的每个hypergraph $ \ nathcal {h} $中，最多都带有$ m（n，s）$ edges $ x $ x $ x $ x $ x $ x $ | \ m nathcalcal ge | E（\ Mathcal {H}）| -s $，其中$ \ Mathcal {h} _x = \ {h \ setMinus \ {x \}：h \ in E（\ Mathcal {h}）\} $。 Füredi和Pach以及Frankl和Tokushige提出了这个问题。虽然第一个结果仅适用于$ s $的特定小值，但Frankl确定了$ m（n，2^{d-1} -1）$，用于所有$ d \ in \ mathbb {n} $，带有$ d \ d \ mid n $。随后，目标成为确定$ m（n，2^{d-1} -c）$的$ c $。 Frankl和Watanabe确定$ M（N，2^{D-1} -c）$ for $ c \ in \ {0,2 \} $。到目前为止，其他一般结果尚不清楚。 我们的主要结果阐明了距离两个功率更远的地方：我们证明$ m（n，2^{d-1} -c）= \ frac {n} {n} {d} {d}（2^d-c）（2^d-c）$ for $ d \ geq 4c 4c $ and $ d \ geq 4c $ and $ d \ d \ d \ mid n $，并给出一个示例，并给出一个示例，显示了$ c = d $ c = d $。关于此问题的另一个研究线是确定$ M（n，s）$的$ S $。在这一行中，我们的第二个结果确定$ m（n，2^{d-1} -c）$ in \ {3,4 \} $。这解决了小$ S $的更多问题，尤其是解决了弗兰克尔和渡边的猜想。
Given two non-negative integers $n$ and $s$, define $m(n,s)$ to be the maximal number such that in every hypergraph $\mathcal{H}$ on $n$ vertices and with at most $ m(n,s)$ edges there is a vertex $x$ such that $|\mathcal{H}_x|\geq | E(\mathcal{H})| -s$, where $\mathcal{H}_x=\{H\setminus\{x\}:H\in E(\mathcal{H})\}$. This problem has been posed by Füredi and Pach and by Frankl and Tokushige. While the first results were only for specific small values of $s$, Frankl determined $m(n,2^{d-1}-1)$ for all $d\in\mathbb{N}$ with $d\mid n$. Subsequently, the goal became to determine $m(n,2^{d-1}-c)$ for larger $c$. Frankl and Watanabe determined $m(n,2^{d-1}-c)$ for $c\in\{0,2\}$. Other general results were not known so far. Our main result sheds light on what happens further away from powers of two: We prove that $m(n,2^{d-1}-c)=\frac{n}{d}(2^d-c)$ for $d\geq 4c$ and $d\mid n$ and give an example showing that this equality does not hold for $c=d$. The other line of research on this problem is to determine $m(n,s)$ for small values of $s$. In this line, our second result determines $m(n,2^{d-1}-c)$ for $c\in\{3,4\}$. This solves more instances of the problem for small $s$ and in particular solves a conjecture by Frankl and Watanabe.
