<abstract xmlns="http://www.w3.org/1999/xhtml"><p>In the last decades many results have been proved on pseudo-randomness of binary sequences. In this series our goal is to show that using many of these results one can also construct large families of quasi-random, pseudo-random and strongly pseudo-random graphs. Indeed, it will be proved that if the first row of the adjacency matrix of a circulant graph forms a binary sequence which possesses certain pseudorandom properties (and there are many large families of binary sequences known with these properties), then the graph is quasi-random, pseudo-random or strongly pseudo-random, respectively. In particular, here in Part I we will construct large families of quasi-random graphs along these lines. (In Parts II and III we will present and study constructions for pseudo-random and <italic>strongly</italic> pseudo-random graphs, respectively.)</p></abstract>

In the last decades many results have been proved on pseudo-randomness of binary sequences. In this series our goal is to show that using many of these results one can also construct large families of quasi-random, pseudo-random and strongly pseudo-random graphs. Indeed, it will be proved that if the first row of the adjacency matrix of a circulant graph forms a binary sequence which possesses certain pseudorandom properties (and there are many large families of binary sequences known with these properties), then the graph is quasi-random, pseudo-random or strongly pseudo-random, respectively. In particular, here in Part I we will construct large families of quasi-random graphs along these lines. (In Parts II and III we will present and study constructions for pseudo-random and strongly pseudo-random graphs, respectively.)

Quasi-Random Graphs, Pseudo-Random Graphs and Pseudorandom Binary Sequences, I. (Quasi-Random Graphs)

Uniform distribution theory

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

In the last decades many results have been proved on pseudo-randomness of binary sequences. In this series our goal is to show that using many of these results...

Quasi-Random Graphs, Pseudo-Random Graphs and Pseudorandom Binary Sequences, I. (Quasi-Random Graphs)

Publié en ligne: 27 mars 2020

Pages: 103 - 126

Reçu: 08 juil. 2019

Accepté: 25 oct. 2019

DOI: https://doi.org/10.2478/udt-2019-0017

Mots clés
quasi-random graph, pseudo-random graph, pseudorandom binary sequence. Research partially supported by Hungarian National Research Development and Innovation Fund K119528

© 2019 József Borbély et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Quasi-Random Graphs, Pseudo-Random Graphs and Pseudorandom Binary Sequences, I. (Quasi-Random Graphs)

Publié en ligne: 27 mars 2020

Pages: 103 - 126

Reçu: 08 juil. 2019

Accepté: 25 oct. 2019

DOI: https://doi.org/10.2478/udt-2019-0017

Mots clésquasi-random graph, pseudo-random graph, pseudorandom binary sequence. Research partially supported by Hungarian National Research Development and Innovation Fund K119528

© 2019 József Borbély et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Mots clés
quasi-random graph, pseudo-random graph, pseudorandom binary sequence. Research partially supported by Hungarian National Research Development and Innovation Fund K119528