高维Ramsey数问题
On High-Dimensional Ramsey Number

作者: 单传辉 :北京工业大学应用数理学院,北京;

关键词: 概率方法高维Ramsey数理论着色Probabilistic Method High-Dimensional Ramsey Number Theory Coloring

摘要:
Paul Erdös和Noga Alon等人给出了一般意义的Ramsey数理论,本文通过概率方法给出了高维情况下的Ramsey数理论及其推广的一般形式。给出了等概率2-着色情况:当k=lRd(k,k)的下界结果;当kl有区分时Rd(l,k)的下界结果。给出了等概率3-着色情况:当k=l=mRd(k,k,k)的下界结果;当k,l,m有区分时Rd(l,k,m)的下界结果。给出了r-着色情况下:当k1=k2=...=krRd(k,k,...k)的下界结果;当k1,k2,...,kr有区分时Rd(k1,k2,...,kr)的下界结果。最后又给出了不等概率时上述各种情况下的相应结果。

Abstract: Paul Erdös and Noga Alon give a general sense of Ramsey Number Theory. This paper presents a general form of Ramsey Number Theory in the dimensional case and its promotion by using probabilistic methods. The paper shows the lower bound of Rd(k,k) in the case of k=l with equal probabilistic 2-coloring situation, and shows the lower bound of Rd(l,k) in the case of k and l distinguishing with equal probabilistic 2-coloring situation. The paper shows the lower bound of Rd(k,k,k) in the case of k=l=m with equal probabilistic 3-coloring situation, and shows the lower bound of Rd(l,k,m) in the case of k, l and m distinguishing with equal probabilistic 3-coloring situation. And the paper shows the lower bound of Rd(k,k,...k) in the case of k1=k2=...=kr with equal probabilistic r-coloring situation, and shows the lower bound of Rd(k1,k2,...,kr) in the case of k1, k2,...,kr distinguishing with equal probabilistic r-coloring situation. Finally, we also give the corresponding results of the variety of situations with unequal probabilities.

文章引用: 单传辉 (2015) 高维Ramsey数问题。 理论数学, 5, 189-206. doi: 10.12677/PM.2015.55028

参考文献

[1] Bona, M. (2011) A walk through combinatorics. World Scientific, Hackensack.
http://dx.doi.org/10.1142/8027

[2] Erdös, P. (1947) Some remarks on the theory of graphs. Bulletin of the American Mathematical Society, 53, 292-294.

[3] Spencer, J. (1994) Ten lectures on the probabilistic method. 2nd Edition, Society for Industrial and Applied Mathematics, Philadelphia.
http://dx.doi.org/10.1137/1.9781611970074

[4] Erdös, P. and Spencer, J. (1974) Probabilistic methods in com-binatorics. Academic Press, Waltham.

[5] Linial, N. and Morgenstern, A. (2013) On high-dimensional acyclic tour-naments. arXiv:1302.1684v1[math.CO].

分享
Top