论文标题
图形分区和分区可比性上的渐近界限
Asymptotic bounds on graphical partitions and partition comparability
论文作者
论文摘要
如果它是简单图的度序列，则称为图形分区。我们证明，均匀选择的尺寸$ n $分区的概率是图形降低到零比$ n^{ - 。003} $快，回答了pittel的问题。 Erdős和Richmond证明了$ N^{ - 1/2} $的下限，因此这表明概率在多项式上降低。我们参数的关键是pittel表征第一行和均匀随机分区的联合分布的渐近结果，并结合了由于ERDőS和GALLAI引起的图形分区的表征。我们的证明还意味着多项式上限是因为两个随机选择的分区在统治顺序中具有比较的概率。
An integer partition is called graphical if it is the degree sequence of a simple graph. We prove that the probability that a uniformly chosen partition of size $n$ is graphical decreases to zero faster than $n^{-.003}$, answering a question of Pittel. A lower bound of $n^{-1/2}$ was proven by Erdős and Richmond, and so this demonstrates that the probability decreases polynomially. Key to our argument is an asymptotic result of Pittel characterizing the joint distribution of the first rows and columns of a uniformly random partition, combined with a characterization of graphical partitions due to Erdős and Gallai. Our proof also implies a polynomial upper bound for the probability that two randomly chosen partitions are comparable in the dominance order.
