Selected papers

A sum packing problem of Erdos and the Conway-Guy sequence

Here I prove a conjecture of John Conway and Richard Guy related to an old sum packing problem of Erdos (this may have been the first conjecture of Erdos). We say that a set S of n positive integers has distinct subset sums if the sums over nonempty subsets of S yield 2^n-1 different integers. For example, the sets {1,2,4,8} and {3,5,6,7} have distinct subset sums. Let f(n) be the minimum value of max(S) for sets S of n positive integers that have distinct subset sums. Note, for example, that f(4) = 7. Erdos conjectured that there exists a constant c such that f(n) > c2^n for all n. Conway and Guy introduced a sequence of sets of integers and showed that the first 21 sets in the sequence have distinct subset sums. The 21st set in this sequence establishes f(n)< 2^{n-2} for n>20. Conway and Guy conjectured that all sets from their sequence have distinct subset sums. In this paper, I prove this conjecture and give a generalization of the construction. This generalization gives the best known upper bound on f(n).

Proceedings of the AMS, 124 (1996) 3627-3636.

Discrete threshold growth is omnivorous for box neighborhoods

Discrete threshold growth is a special case of bootstrap percolation. Let G be a r-regular graph and t< r be an integer. Bootstrap percolation on G with threshold t begins with some initial set of occupied vertices A_0 (this set is sometimes chosen at random). An increasing sequence of sets of vertices is then deterministically generated by the following rule: x is in A_{i+1} if x is in A_i or at least t neighbors of x are in A_i.
Here we consider bootstrap percolation on graphs of the following form: the vertex set is the 2-dimensional integer lattice and the neighborhood of a given vertex is the set of all vertices inside a box of some arbitrary fixed radius. Janko Gravner and David Griffeath asked the following question: Does there exist a initial configuration A_0 such that A_{i+1} and A_i are different for all i but the union of the A_i's is not the full plane? In this paper, I answer this question, showing that no such initial configuration exists. This result has implications for the limiting shape of the occupied set when A_0 is finite.

Transactions of the AMS, 351 (1999) 947-983.

A nontrivial lower bound on the Shannon capacities of the complements of odd cycles (with Ron Holzman)

The Shannon capacity of a graph G is determined the independence numbers of the powers of G and gives a measure of the zero-error capacity of a communication channel associated with G. If G is a perfect graph then the Shannon capacity of G is equal to the independence number of G. So it follows from the strong perfect graph theorem that the odd cycles on 5 or more vertices and their complements are, in a certain sense, the simplest graphs for which the Shannon capacity is not known. The Shannon capacity of the 5-cycle (which is self-complementary) was established in a famous paper of Lovasz.
In this paper we construct independent sets in the powers of the complements of odd cycles that give the only known non-trivial lower bound on the Shannon capacities of the complements of odd cycles.

IEEE Transactions on Information Theory, 49 (2003) 721-722.

Linear versus hereditary discrepancy (with Ron Holzman)

The discrepancy of a hypergraph H on vertex set V is the minimum, taken over all red/blue colorings of V, of the maximum, taken over all edges e in H, of the difference between the number of blue vertices in e and the number of red vertices in e. So, a coloring of V that achieves the discrepancy is as balanced as possible on all edges. Since the discrepancy of H can be small for somewhat arbitrary global reasons, refined notions of discrepancy have be introduced with the goal of better capturing the inherent balance throughout H. Two of these notions are linear discrepancy and hereditary discrepancy.
Laszlo Lovasz, Joel Spencer and Katalin Vesztergombi proved that the linear discrepancy of H is bounded above by the hereditary discrepancy and conjectured a sharper bound that depends in the number of vertices in H. Here we prove this conjecture for hypergraphs with hereditary discrepancy 1. (This was proved independently by Benjamin Doerr).

Combinatorica, 25 (2005) 39-47.

Creating a giant component (with David Kravitz)

Consider the following variation on the classical random graph. Let e_1,f_1, e_2,f_2, ... be a sequence of pairs of random edges. At step i we choose either e_i or f_i to be an edge in the graph. For example, we could take e_i if it is isolated from all other edges taken so far and otherwise take f_i. Does a giant component suddenly emerge in this evolution as it does in the traditional Erdos-Renyi random graph? If so, when does it appear?
Here we prove a conjecture of Joel Spencer by analyzing the evolution of the sum of the squares of the component sizes (i.e. the susceptibility) for a class of processes of this form using the so-called differential equations method for random graph processes. It turns out the emergence of the giant component corresponds to a blow-up point in the associated differential equation. (This was established independently by Spencer and Nick Wormald using different methods.)

Combinatorics, Probability and Computing, 15 (2006) 489-511.

Karp-Sipser on random graphs with a fixed degree sequence (with Alan Frieze)

The Karp-Sipser algorithm is a randomized algorithm for finding a large matching in a graph. We iteratively choose random edges one at a time. When an edge e is chosen it is added to the matching and all edges that are incident with e are deleted from the graph. The choice of random edge is always uniform with the following caveat: preference is given to edges that contain vertices of degree one (so-called pendant edges). If there are pendant edges in the graph then the algorithm chooses one of them uniformly at random. We give such edges priority as the vertices of degree 1 are in danger of not being included in an edge in the matching.
In this paper we analyze the Karp-Sisper algorithm on random graphs with fixed degree distributions via the differential equations method for random graph processes. It turns out the associated ordinary differential equation has an invariant set S, that is, a set with the property that any solution to the differential equation with initial point in S remains in S throughout the evolution. It follows from this fact about the differential equation that the Karp-Sipser algorithm is very likely to succeed in finding a nearly prefect matching for random graphs with degree sequences within the invariant set S.

Hamilton cycles in 3-out (with Alan Frieze)

Consider the following random graph. We begin with a set of n vertices. Each vertex x chooses three other vertices x_1, x_2, x_3 uniformly at random. The edge set is then the set of all edges of the form {x, x_i}. Note that this graph, which is known as 3-out, has average degree 6 and minimum degree 3.
Here we show that with high probability 3-out has a Hamilton cycle. This result is sharp as it is very unlikely for 2-out to have a Hamilton cycle (as there will likely be three vertices of degree 2 that have a common neighbor, a so-called spider).

The triangle-free process

Consider the following random graph process. We begin with the empty graph on n vertices and iteratively add edges chosen at random one at a time. Each edge is chosen uniformly at random from the collection of pairs do not form triangles when added as edges to the existing graph. Jeong-Han Kim used a semi-random variation on the triangle-free process to prove that the Ramsey number R(3,t) is bounded below by a constant times t^2/(log t).
In this paper I give an analysis of the triangle-free process using the differential equations method for random graph processes. This yields the likely order of magnitude of the number of edges in the final graph and the order of magnitude of the independence number of the final graph. The former proves a conjecture of Joel Spencer while the latter establishes that the triangle-free process produces a Ramsey R(3,t) graph (i.e. a triangle free graph whose independence number is within a multiplicative constant factor of the smallest possible). This analysis extends to the K_4-free process thereby producing an improvement on the best known lower bound on R(4,t).

Advances in Mathematics, 221 (2009) 1653-1677.