James B. Shearer - ps abstract

IBM - Personal communication

This web page contains the abstract of my paper:

"On a Problem of Spencer", Combinatorica, 3(1985), p. 241-245.

Abstract: Let X1,...,Xn be events in a probability space. Let pi be the probability that Xi occurs. Let p be the probability that none of the Xi occur. Let G be a graph on [n] so that for 1<=i<=n Xi is independent of {Xj|(i,j) is not an edge in G}. Let f(d) be the sup of those x such that if p1,...,pn<=x and G has maximum degree <=d then p>0. We show f(1)=1/2, f(d)=(d-1)**(d-1)/d**d for d>=2. Hence lim d goes to infinity of [d*f(d)] = 1/e. This answers a question posed by Spencer in [2]. We also find a sharp bound for p in terms of the pi and G.