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.
翻译:我们介绍和研究在定向环形图背景下的扩张器和超无限图形序列的类比,我们分别称之为“extender”和“Hepershallow”图形序列。 我们的主要结果是非超级图形序列的概率构建。