  Combinatorial Levy processes evolve on general state spaces of countable
combinatorial structures. In this setting, the usual Levy process properties of
stationary, independent increments are defined in an unconventional way in
terms of the symmetric difference operation on sets. In discrete time, the
description of combinatorial Levy processes gives rise to the notion of
combinatorial random walks. These processes behave differently than random
walks and Levy processes on other state spaces. Standard examples include
processes on sets, graphs, and n-ary relations, but the framework permits far
more general possibilities. The main theorems characterize both finite and
infinite state space combinatorial Levy processes by a unique sigma-finite
measure. Under the additional assumption of exchangeability, we obtain a more
explicit characterization by which every exchangeable combinatorial Levy
process corresponds to a Poisson point process on the same state space.
Associated behavior of the projection into a space of limiting objects reflects
certain structural features of the covering process.
