  We study the k-wise independent relaxation of the usual model G(N,p) of
random graphs where, as in this model, N labeled vertices are fixed and each
edge is drawn with probability p, however, it is only required that the
distribution of any subset of k edges is independent. This relaxation can be
relevant in modeling phenomena where only k-wise independence is assumed to
hold, and is also useful when the relevant graphs are so huge that handling
G(N,p) graphs becomes infeasible, and cheaper random-looking distributions
(such as k-wise independent ones) must be used instead. Unfortunately, many
well-known properties of random graphs in G(N,p) are global, and it is thus not
clear if they are guaranteed to hold in the k-wise independent case. We explore
the properties of k-wise independent graphs by providing upper-bounds and
lower-bounds on the amount of independence, k, required for maintaining the
main properties of G(N,p) graphs: connectivity, Hamiltonicity, the
connectivity-number, clique-number and chromatic-number and the appearance of
fixed subgraphs. Most of these properties are shown to be captured by either
constant k or by some k= poly(log(N)) for a wide range of values of p, implying
that random looking graphs on N vertices can be generated by a seed of size
poly(log(N)). The proofs combine combinatorial, probabilistic and spectral
techniques.
