REAL

On directed analogues of expander and hyperfinite graph sequences

Csóka, Endre and Grabowski, Łukasz (2022) On directed analogues of expander and hyperfinite graph sequences. COMBINATORICS PROBABILITY & COMPUTING, Publis. ISSN 0963-5483

[img]
Preview
Text
2008.08680.pdf

Download (225kB) | Preview

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. © The Author(s), 2021. Published by Cambridge University Press.

Item Type: Article
Uncontrolled Keywords: Probability; Computer science; Directed graphs; expander; Directed acyclic graph (DAG); Graph limits; Graph sequences; HYPERFINITE; HYPERFINITE; Extender; Keywords:;
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 04 Nov 2022 12:40
Last Modified: 04 Nov 2022 12:40
URI: http://real.mtak.hu/id/eprint/152910

Actions (login required)

Edit Item Edit Item