Fetching the paper…

Reading the bibliography…

2008

k-Wise Independent Random Graphs

Alon, Noga, Nussboim, Asaf

Original
PDF
Post on X

Understand

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.

k-Wise Independent Random Graphs · Around

Built on

E. Wigner
1958
Earlier work this paper cites.
P. Erdös, A. Rényi
1959
Earlier work this paper cites.
P. Erdös, A. Rényi
1960
Earlier work this paper cites.
P. Erdös, A. Rényi
1964
Earlier work this paper cites.
P. Erdös, A. Rényi
1966
Earlier work this paper cites.
P. Erdös, A. Rényi
1968
Earlier work this paper cites.
R. Fagin
1969
Earlier work this paper cites.
A. Joffe
1974
Earlier work this paper cites.
R. M. Wilson
1975
Earlier work this paper cites.
B. Bollobás, P. Erdös
1976
Earlier work this paper cites.
Y. V. Glebskii, D. I. Kogan, M. I. Liagonkii, V. A. Talanov
1976
Earlier work this paper cites.
A.D. Kors̆unov
1976
Earlier work this paper cites.
D.W. Matula
1976
Earlier work this paper cites.

Similar

B. Bollobás
1981
Cited alongside, same era.
Z. Füredi , J. Komlos
1981
Cited alongside, same era.
J. Komlós, E. Szemerédi
1983
Cited alongside, same era.
B. Bollobás
1985
Cited alongside, same era.
N. Alon, L. Babai, A. Itai
1986
Cited alongside, same era.
N. Alon , F. R. K. Chung
1986
Cited alongside, same era.
B. Bollobás, A. Thomason
1986
Cited alongside, same era.
A. Rucinski, A. Vince
1986
Cited alongside, same era.

Then

A. Frieze
1990
Later among the works it cites.
T. Łuczak
1991
Later among the works it cites.
N. Alon, J. Spencer
1992
Later among the works it cites.
Nikolai N. Kuzjurin
1995
Later among the works it cites.
E. Friedgut, G. Kalai
1996
Later among the works it cites.
N. Alon, M. Krivelevich, B. Sudakov
1999
Later among the works it cites.
N. Alon, M. Krivelevich, B. Sudakov
1999
Later among the works it cites.
S. Janson, T. Łuczak, A. Rucinski
2000

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

A. Thomason

1987

Cited alongside, same era.

B. Bollobás

1988

Cited alongside, same era.

S. Shelah, J. H. Spencer

1988

Cited alongside, same era.

B. Chor, O. Goldreich

1989

Cited alongside, same era.

Later among the works it cites.

O. Goldreich, S. Goldwasser, A. Nussboim

2003

Later among the works it cites.

A. Nussboim

2003

Later among the works it cites.

M. Naor, A. Nussboim, E. Tromer

2005

Later among the works it cites.

V. H. Vu

2005

Later among the works it cites.

M. Krivelevich , B. Sudakov

2006

Later among the works it cites.