Selected papers
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 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.
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.
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.
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.
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).
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.