top | item 43746928

(no title)

jlrubin | 10 months ago

> The fraction turned out to be approximately 69%, making the graphs neither common nor rare.

The wording kinda bothers me... Either 31% or 69% is exceedingly common.

Rare would be asymptotically few, or constant but smaller than e.g. 1 in 2^256.

I guess the article covers it's working definition of common, ever so briefly:

> that if you randomly select a graph from a large bucket of possibilities, you can practically guarantee it to be an optimal expander.

So it's not a reliable property, either way.

discuss

order

No comments yet.