### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 |

Pages | 813-822 |

Number of pages | 10 |

DOIs | |

State | Published - Dec 30 2008 |

Externally published | Yes |

Event | 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 - Philadelphia, PA, United States Duration: Oct 25 2008 → Oct 28 2008 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

ISSN (Print) | 0272-5428 |

### Other

Other | 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 |
---|---|

Country | United States |

City | Philadelphia, PA |

Period | 10/25/08 → 10/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

*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