K-wise independent random graphs

Noga Alon, Asaf Nussboim

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
Pages813-822
Number of pages10
DOIs
StatePublished - Dec 30 2008
Externally publishedYes
Event49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 - Philadelphia, PA, United States
Duration: Oct 25 2008Oct 28 2008

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
CountryUnited States
CityPhiladelphia, PA
Period10/25/0810/28/08

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'K-wise independent random graphs'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., & Nussboim, A. (2008). K-wise independent random graphs. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 (pp. 813-822). [4691013] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2008.61