A note on the relation between two properties of random graphs

Shohei Satake

Published 2019-01-30Version 1

The t-existentially closed (t-e.c.) property and pseudo-random property are properties which random graphs asymptotically almost surely satisfy. In this note, by constructing explicit infinite families of graphs without probabilistic arguments, we show that the t-e.c. property does not necessarily imply the best possible pseudo-random property. We also discuss the relation between t-e.c. graphs and expander graphs.