Commits

committed 4656b92

• Participants
• Parent commits e7b3e5b
• Branches default

File posts/2012-08-01-quasirandom-introduction.markdown

• Ignore whitespace
+---
+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.