We consider a graph property
which contains occurrences of the notation "little oh" \( o(.).\)
For example, we define the following property for a graph \(G\) on \(n\) vertices:
Property \(A\) : \(G\) has \( (1/4 +o(1)) n^2 \) edges.
Suppose we have two properties \(P \) and \(P'\), each with occurances \(o(.).\)
\(
P \rightarrow P' \) means:
-
For any given \(\epsilon\), there is a \(\delta \) such that
\(P(\delta)\) implies \(P'(\epsilon)\).
Note that \(P(\delta)\) means that in the statement of \(P\) each occurrence of \(o(1)\) in \(P\) is replaced by \(\delta\).
-
We consider an infinite sequence of graphs \( G_n\) as \(n\) goes to infinity. In this case, the interpretation of \(o(f(n))\) is just a quantity that goes to
\( 0\) as \(n\) goes to infinity.
Example
We consider the following property for a graph \(G\)
:
Property \(B\) : All but \(o(n)\) vertices have degree \((1/2+o(1))n.\)
Property \(P(s)\) : Every graph on \(s\) vertices occurs in \(G\)
the expected number \( (2^{\binom n 2} \times n^s) \) of times as a random graph
(with edge density \(1/2 \) ).
Clearly \(B \rightarrow A\), but the reverse directions is not true.
Also, \(P(s+1) \rightarrow P(s)\).
Remarks:
-
We can define the equivalence of two graph properties if the implications go both ways.
When
FC and RLG first tried to classify graph properties, we aimed at building several equivalence classes and finding their relations. We found out that one of the equivalence classes is amazingly strong, which we name it quasirandom to
distinquish it from `pseudo random'.
-
The \(o(1)\) terms are used to suppress the negligible portion of the "noise" in order to allow us having a full view of the big picture.
- In the proofs of quasirandomness, in every implications of \(P(\delta) \rightarrow P'(\epsilon)\), the choice for \(\delta\) as a function of \(\epsilon \) was
explicitly specified. Finding the best possible quantitative relations of the respective error bounds remains to be an interesting problem.
-
The second definition leads to a natural way of considering graph limits.
Back to Resources for Quasirandom graphs