(1) A set D of natural numbers is called t-intersective if every positive upper density subset A of natural numbers contains a (t+1)-length arithmetic progression (AP) whose common differences is in…

In 1973 Erdos asked whether there are n-vertex partial Steiner triple systems with arbitrary high girth and quadratically many triples. (Here girth is defined as the smallest integer g \ge 4 for…

The search for the asymptotics of the Ramsey function R(3,k) has a long and fascinating history. It begins in the hill country surrounding Budapest and winding over the decades through Europe,…

Traditional Erdos Magic (a.k.a. The Probabilistic Method) proves the existence of an object with certain properties by showing that a random (appropriately defined) object will have those properties…

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our…