k-Wise Independent Random Graphs
| dc.creator | Alon, Noga | |
| dc.creator | Nussboim, Asaf | |
| dc.date | 2008-04-08 | |
| dc.date.accessioned | 2026-07-07T09:31:03Z | |
| dc.date.available | 2026-07-07T09:31:03Z | |
| dc.description | 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. | |
| dc.description | 23 pages | |
| dc.identifier | https://arxiv.org/abs/0804.1268 | |
| dc.identifier | http://arxiv.org/abs/0804.1268 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/158325 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C80 | |
| dc.title | k-Wise Independent Random Graphs | |
| dc.type | text |