4
$\begingroup$

My question is somehow concerning terminology on extremal graph theory.

Is there any difference concerning the notion of quasi-random graph and the notion of pseudo-random graph? My feeling is that they refer at the end (in a very general sense) to given graphs that behave that random, but of course there may be some subtility that I do not know.

For instance, Quasi-randomness (as far as I know) was started (as far as I know) on the paper of Chung-Graham-Wilson (showing that several conditions are equivalent, and happening in the $G(n,p)$ random model).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Someone else will probably have a better answer, but I can't leave a comment. In my experience "quasi-random graph" (almost?) always refers to the Chung Graham Wilson type graphs you referred to.

"pseudo-random graph" is much more context specific (varies from paper to paper). You are right that it usually entails taking some property that random graphs have (almost regular, right number of edges between pairs of large sets, etc) and then considering all graphs which satisfy that property and calling them pseudo-random.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .