Lesson plan
Pseudorandom graph
In graph theory, a graph is said to be a pseudorandom graph if it obeys certain properties that random graphs obey with high probability. There is no concrete definition of graph pseudorandomness, but there are many reasonable characterizations of pseudorandomness one can consider. Pseudorandom properties were first formally considered by Andrew Thomason in 1987. He defined a condition called "jumbledness": a graph G=(V,E) is said to be (p,\alpha) -jumbled for real p and \alpha with 0 if : \left|e(U)-p\binom {2}\right|\leq \alpha|U| for every subset U of the vertex set V , where e(U) is the number of edges among U (equivalently, the number of edges in the subgraph induced by the vertex set U ). It can be shown that the Erdős–Rényi random graph G(n,p) is almost surely (p,O(\sqrt{np})) -jumbled. However, graphs with less uniformly distributed edges, for example a graph on 2n vertices consisting of an n -vertex complete graph and n completely independent vertices, are not (p,\alpha) -jumbled for any small \alpha , making jumbledness a reasonable quantifier for "random-like" properties of a graph's edge distribution.
Article summary
In graph theory, a graph is said to be a pseudorandom graph if it obeys certain properties that random graphs obey with high probability. There is no concrete definition of graph pseudorandomness, but there are many reasonable characterizations of pseudorandomness one can consider. Pseudorandom properties were first formally considered by Andrew Thomason in 1987. He defined a condition called "jumbledness": a graph G=(V,E) is said to be (p,\alpha) -jumbled for real p and \alpha with 0 if : \left|e(U)-p\binom {2}\right|\leq \alpha|U| for every subset U of the vertex set V , where e(U) is the number of edges among U (equivalently, the number of edges in the subgraph induced by the vertex set U ). It can be shown that the Erdős–Rényi random graph G(n,p) is almost surely (p,O(\sqrt{np})) -jumbled. However, graphs with less uniformly distributed edges, for example a graph on 2n vertices consisting of an n -vertex complete graph and n completely independent vertices, are not (p,\alpha) -jumbled for any small \alpha , making jumbledness a reasonable quantifier for "random-like" properties of a graph's edge distribution.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.