On directed analogues of expander and hyperfinite graph sequences
arXiv:2008.08680 · doi:10.1017/S0963548321000225
Abstract
We introduce and study analogues of expander and hyperfinite graph sequences in the context of directed acyclic graphs, which we call "extender" and "hypershallow" graph sequences, respectively. Our main result is a probabilistic construction of non-hypershallow graph sequences.
17 pages, no figures, v3: very minor changes compared to v2, final accepted version to appear in Comb. Probab. Comput