# HG changeset patch
# User John Lenz
# Date 1343861688 18000
# Node ID 4656b923066e10e3e33040147c9e4fb4cf99d1aa
# Parent e7b3e5ba998396bbfc1520645cce2db1fc03af56
Add intro to quasirandom post
diff --git a/posts/2012-08-01-quasirandom-introduction.markdown b/posts/2012-08-01-quasirandom-introduction.markdown
new file mode 100644
--- /dev/null
+++ b/posts/2012-08-01-quasirandom-introduction.markdown
@@ -0,0 +1,60 @@
+---
+title: Introduction to Quasirandom Graphs
+author: John Lenz
+tags: quasirandom, graph, research
+date: August 1, 2012
+math: true
+---
+
+Currently, my academic research focuses on quasirandom or pseudorandom hypergraphs. Professor
+Mubayi and I are releasing two big papers soon, and this post is the start of a series of posts
+attempting to describe my research to a wider audience. Note that in combinatorics we usually study
+a wide range of topics, so quasirandom hypergraphs are just one of our current focuses, but since we
+are releasing these papers I will attempt to describe the research.
+
+Random graphs are one of the most important and fruitful concepts in combinatorics and theoretical
+computer science, and it is almost impossible to overstate their importance. The Random Graph^[We call it
+*the* Random Graph, even though technically it is a probability distribution over the class of
+$n$-vertex graphs.] is the [graph](http://en.wikipedia.org/wiki/Graph_%28mathematics%29) where each
+pair of vertices becomes an edge with probability $\frac{1}{2}$ independently of any other choices. One can
+think of flipping a coin for each pair of vertices, and making it an edge if the coin comes up
+heads. More generally, the Random Graph $G(n,p)$ is formed by flipping a coin for each edge that
+comes up heads with probability $p$ and tails with probability $1-p$.
+
+Besides being interesting objects of study in their own right, Random Graphs provide essential
+examples of graphs answering many questions in combinatorics and computer science. In computer
+science, we might be searching for an example input to a computer program which causes the program
+to run really slowly or in combinatorics we look for constructions of mathematical objects. In
+many cases, the Random Graph (or extensions or variations on it) is an important example to test our
+algorithms or to construct.
+
+For example, what is the largest number of people at a party before either there are $3$ people who
+all mutually know each other or $3$ people who do not mutually know each other? A detailed answer is
+on [wikipedia](http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Example:_R.283.2C3.29_.3D_6), but for
+our current discussion the important point is that lower bounds on the number of people at the party
+come from a collection of people together with who they know and who they don't know. Recall that
+the question asks for the largest number of people at a party before there are forced to be cliques
+(mutual friends) or anti-cliques (mutual strangers), so a lower bound is a party where there are no
+cliques or no anti-cliques. One can consider the question where $3$ is replaced with $4$, $5$, and
+so on. For these larger clique sizes, the best known party is the Random Graph. The fact that the
+random party (where people decide if the know each other by flipping a coin) is a good [lower
+bound](http://en.wikibooks.org/wiki/Combinatorics/Bounds_for_Ramsey_numbers#Lower_bound) was proved
+by ErdÅ‘s in 1947 and was one of the early uses of the Random Graph. Since that time, no better
+construction has been found despite much attention; this is the best construction known!
+
+The tremendous success of Random Graphs motives the following questions. What are the essential
+properties of random graphs? Can we build graphs which are not quite random but still behave
+randomly? What does it mean for a graph to look random-like? Can one deterministically (without
+randomness) determine if a graph looks random? Could some uses of the Random Graph be replaced with
+deterministically constructed graphs which look random? Which uses?
+
+These last two questions are the most fascinating and (perhaps unexpectedly) lead to many deep and
+open questions in mathematics and theoretical computer science. It is possible to explicitly
+construct (without randomness) graphs which look random, and these graphs are called *quasirandom*
+or *pseudorandom*.^[I have seen both quasirandom and pseudorandom terms used, and as far as I can
+tell they mean the same thing.] What is fascinating is that some of the applications of Random
+Graphs can be replaced with quasirandom graphs and some can not.
+
+In a future post, I will attempt to describe some of these applications of quasirandom
+graphs, which include the famous [P vs NP](http://en.wikipedia.org/wiki/P_vs_NP) problem with its
+$1,000,000 prize and questions on arithmetic progressions.