关于Erdos-Jacobson-Lehel 问题的门槛

设σ(k,n）表示最小的正整数m，使得对于每个n项正可图序列，当其项和至少为m时，有一个实现含k 1个顶点的团作为其子图。Erdos等人猜想：σ(k,n）＝（k-1)(2n-k) 2.Li等人证明了这个猜想对于k≥5，n≥（^k2））＋3是对的，并且提出如下问题：确定最小的整数N（k），使得这个猜想对于n≥N(k）成立。他们同时指出：当k≥5时，[5k-1/2]≤N(k）≤（^k2) 3.Mubayi猜想：当k≥5时，N(k）＝[5k-1/2]。在本文中，我们证明了N（8）＝20，即Mubayi猜想对于k=8是成立的。

On the Threshold in the Erdos Jacobson-Lehel Problem

Let σ(k,n) denote the smallest even integer such that each n-term positive graphic se-quence with term sum at least σ(k,n) can be realized by a simple graph on n vertices containing aclique of k + 1 vertices. Erdos et al. conjectured that σ(k, n) = (k - 1) (2n- k) + 2. Li et al. proved(k2)+ 3, and raised the problem of determining thethat the conjecture istruefor k≥5andn≥smallest integer N ( k ) such that the conjecture holds for n ≥ N ( k ) and pointed out that [ 5k-1/2 ] ≤N(k) ≤ 2 +3 for k≥5. MubayiconjecturedthatN(k)= [5k-1/2] for k≥5. In this paper, we prove that N(8) = 20. In other words, the Mubayi＇s conjecture is true for k = 8.