On directed analogues of expander and hyperfinite graph sequences

Autor:	Csóka, Endre, Grabowski, Łukasz
Rok vydání:	2020
Předmět:	Mathematics - Combinatorics Computer Science - Computational Complexity Mathematics - Probability
Zdroj:	Combinator. Probab. Comp. 31 (2022) 184-197
Druh dokumentu:	Working Paper
DOI:	10.1017/S0963548321000225
Popis:	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. Comment: 17 pages, no figures, v3: very minor changes compared to v2, final accepted version to appear in Comb. Probab. Comput
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2008.08680 Zobrazit plný text záznamu View this record from Arxiv