+title: Introduction to Quasirandom Graphs

+tags: quasirandom, graph, research

+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.