Better Expanders and Superconcentrators by Kolmogorov Complexity.
Uwe Schöning · 1997
We show the existence of various versions of expander graphs using Kolmogorov complexity. This method seems superior to the usual “probabilistic construction”. Also, the best known bounds on the size of expanders and superconcentrators can be obtained this way. In the case of (acyclic) superconcentrators we obtain the density 34. Also, we review related graph properties, like magnification, edge-magnification, isolation, and develop bounds based on the Kolmogorov approach.