论文标题
一组随机整数的完美分区
Perfect partitions of a random set of integers
论文作者
论文摘要
令$ x_1，\ dots，x_n $为独立的整数，在$ \ {1，\ dots，m \} $，$ m = m（n）\ to \ infty $上均匀分布。 $ [n] $ of $ n $ s $ s $ s $ s $ nonepty子集成$ s_1，\ dots，s_ν$，如果所有$ν$ values $ \ sum_ {j \ in S _ {\ a}} x_j $相等。为了使一个完美的分区存在，$ \ sum_j x_j $必须由$ν$除外。对于$ν= 2 $，Borgs等人。除其他结果外，还以$ \ sum_j x_j $为条件，如果$κ：= \ lim \ tfrac {n} {\ log m} {\ log m}> \ tfrac {1} {\ log log 2} {\ log 2} $，并且该W.H.P.如果$κ<\ tfrac {1} {\ log 2} $，则不存在完美的分区。我们证明了W.H.P.如果$ν\ ge 3 $和$κ<\ tfrac {2} {\logν} $，则不存在完美的分区。我们确定了$κ$的范围，其中预期的完美分区数量指数高。我们表明，对于$κ> \ tfrac {2（ν-1）} {\ log [（1-2ν^{ - 2}）^{ - 1}]} $完美分区的总数呈近来高，概率为$ \ gtrsim（1+ν^2）^{ - 1} $。
Let $X_1,\dots, X_n$ be independent integers distributed uniformly on $\{1,\dots, M\}$, $M=M(n)\to\infty$ however slow. A partition $S$ of $[n]$ into $ν$ non-empty subsets $S_1,\dots, S_ν$ is called perfect, if all $ν$ values $\sum_{j\in S_{\a}}X_j$ are equal. For a perfect partition to exist, $\sum_j X_j$ has to be divisible by $ν$. For $ν=2$, Borgs et al. proved, among other results, that, conditioned on $\sum_j X_j$ being even, with high probability a perfect partition exists if $κ:=\lim \tfrac{n}{\log M}>\tfrac{1}{\log 2}$, and that w.h.p. no perfect partition exists if $κ<\tfrac{1}{\log 2}$. We prove that w.h.p. no perfect partition exists if $ν\ge 3$ and $κ<\tfrac{2}{\log ν}$. We identify the range of $κ$ in which the expected number of perfect partitions is exponentially high. We show that for $κ> \tfrac{2(ν-1)}{\log[(1-2ν^{-2})^{-1}]}$ the total number of perfect partitions is exponentially high with probability $\gtrsim (1+ν^2)^{-1}$.
