Paul Erdős

From GM-RKB
Jump to: navigation, search

Paul Erdős was a person.



References

2014

1989

  • (Erdös et al., 1989) ⇒ Paul Erdős, Pavol Hell and Peter Winkler. (1989). “Bandwidth Versus Bandsize.” In: Annals of Discrete Math. doi:10.1016/S0167-5060(08)70455-2
    • QUOTE: The bandwidth (bandsize) of a graph G is the minimum, over all bijections u: V(G) → {1,2,…,|V(G)|}, of the greatest difference (respectively the number of distinct differences) |u(v) — u(w)| for vw ɛE(G).

      We show that a graph on n vertices with bandsize k has bandwidth between k and cn1-1/n, and that this is best possible. In the process we obtain best possible asymptotic bounds on the bandwidth of circulant graphs.

      The bandwidth and bandsize of random graphs are also compared, the former turning out to be n — C1 log n and the latter at least n — c2 (logn)2.

1976

1960

  • (Erdős & Rényi, 1960) ⇒ Paul Erdős, and A. Rényi (1960). “On the evolution of random graphs". Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5.

1951

1935