HN Reader

> 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.

Expander graphs are cool.

Consider the following computer sciency problem: construct an acyclic network of "sorting gates" (which take x and y as input and output min(x,y) and max(x,y)) so that it sorts n inputs.

A merge-sort like algorithm had been known that worked in O(n(logn)^2) gates. It was an open problem for a while if it could be done with O(nlogn) gates (which would be the best possible). This was settled in the affirmative via a construction using expander graphs.

The article reads as written by someone who just learned about graphs, it focuses so much on the bet and so less on explaining Ramanujan expanders

Might be fruitful to apply this on p2p mesh networks. I suppose you should be able to make a model describing how the relationship between the fraction of byzantine nodes affects the probability distribution of connectedness. Then you could figure out what algorithm parameters would put you within desired bounds for tolerated ratios of byzantine.

69% looks surprising like the answer to this puzzle:

> The numbers 1–n are randomly placed into n boxes in a line. There are n people who are each able to look into half the boxes. While they are allowed to coordinate who looks into which boxes beforehand, they are taken out one at a time to choose which half of the boxes they will peek at. The goal is for the first person to find the number one, the second person to find the number two, and so on. If any of them fail to find their number, the whole group loses. What is the probability they lose if they use the optimal strategy?

I wonder if there's a connection to regular graphs here.

Ah, I knew I recognized these from somewhere! There was another paper released a while ago about Hamiltonian cycles in expander graphs: https://news.ycombinator.com/item?id=40609753

Also see a quite unrelated paper about a property of expander graphs: https://news.ycombinator.com/item?id=36856881

These are certainly popular objects!

Coming to a leetcode interview soon near you!