<p>There are interesting open algorithmic problems in random graphs, which might even lead to nontrivial results about complexity classes.</p>
<p>For the sake of an example, consider the simplest random graph model: take <span class="math-container">$n$</span> vertices, and put in each edge randomly and independently with probability 1/2. This model is often denoted by <span class="math-container">$G(n,1/2)$</span>. It is a known result from the theory of random graphs that the size of a maximum clique in  <span class="math-container">$G(n,1/2)$</span> is asymptotically <span class="math-container">$2\log_2 n$</span>, and the actual size is strongly concentrated on merely two neighboring integers.</p>
<p>That is, the clique number of <span class="math-container">$G(n,1/2)$</span> is (asymptotically) almost exactly determined. But how hard is it to <em><strong>find</strong></em> such a clique? It is unlikely to be NP-hard, because
there are only <span class="math-container">$n^{O(\log n)}$</span> many subsets of this size, so we can do an exhaustive search in   <span class="math-container">$n^{O(\log n)}$</span> time, which is still a sub-exponential algorithm.
At the same time, no polynomial-time algorithm is known, either.</p>
<p>However, good constant factor approximation is possible: about  half of the optimum, i.e. <span class="math-container">$\log_2 n$</span>, can be achieved by a known polynomial-time algorithm, with high probability.
On the other hand, for any fixed <span class="math-container">$\epsilon&gt;0$</span>, no polynomial-time algorithm is known
that would find a clique of size at least <span class="math-container">$(1+\epsilon)\log_2 n$</span> with high probability in <span class="math-container">$G(n,1/2)$</span>.</p>
<p>In general, I could imagine as an interesting research subject, the study of how various random graph algorithms could be reduced to each other. Are there such problems that could be identified as complete for certain appropriately defined classes?</p>

CC BY-SA 4.0
2021-08-27T03:45:15.967Z
2021-08-27T03:45:15.967Z
Andras Farago
<p>One very natural application of random graph theory in computer science comes from the analysis of <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing" rel="nofollow noreferrer">cuckoo hashing</a>. In the most basic form of cuckoo hashing (with one key per cell and two possible cells per key) the state of a cuckoo hash table can be described as a random graph with a vertex for each cell and an edge for each key. The ability to place all keys into their cells hinges on the likelihood that the resulting graph has no connected components with more than one cycle. More detailed analysis of cuckoo hashing and its variants extend to more complex questions about random graphs and random hypergraphs.</p>

CC BY-SA 4.0
2021-08-27T19:09:41.100Z
2021-08-27T19:09:41.100Z
David Eppstein
<p>Phase transitions in NP-complete (and other) problems. See this nice recent survey/intro by Cris Moore: <a href="https://arxiv.org/abs/1702.00467" rel="nofollow noreferrer">https://arxiv.org/abs/1702.00467</a>.</p>
<p>Many constructions in TCS (eg expanders come to mind) can be shown to exist by the probabilistic method. Getting efficient deterministic constructions to do the same is often challenging, interesting, and useful, but the proof of existence is a good start.</p>

CC BY-SA 4.0
2021-08-27T03:32:20.490Z
2021-08-27T03:32:20.490Z
Joshua Grochow
<p>Another interesting connection between random graphs and TCS can be found in the concept of <strong>de-randomization.</strong>
Generally, de-randomization means the approximation of truly random structures by deterministic ones.</p>
<p>In TCS these random structures are often <em>random bit sequences,</em> which play an important role in randomized algorithms.  There is much interest in constructing pseudo-random bit generators, which may lead to the de-randomization of randomized complexity classes, such as BPP, RP, ZPP. It is a major open question whether the complete de-randomization of these complexity classes is possible or not.</p>
<p>In random graph theory there is also significant interest in finding deterministic graph constructions that resemble truly random graphs, see the paper <a href="https://arxiv.org/pdf/math/0503745.pdf" rel="nofollow noreferrer">Pseudo-random graphs</a> by Krivelevich and Sudakov.</p>
<p>It seems that graphs have more structure than bit sequences. As a result, one can perhaps prove nicer results about pseudo-random graphs than about pseudo-random bit sequences. This may be only my personal taste, but if you read the above referenced paper, you might arrive at a similar conclusion.</p>
<p>It seems to me that TCS could still benefit from pseudo-random graph related results in the area of de-randomization. In the other direction, interesting pseudo-random graph constructions may arise from pseudo-random bit generators used in TCS, such as the Nisan-Wigderson generator.</p>

CC BY-SA 4.0
2021-08-27T23:40:52.087Z
2021-08-27T23:40:52.087Z
Andras Farago
<p>One famous connection of random graphs to TCS is network connectivity.</p>
<p>Random graphs such as the Erdős–Rényi model - <a href="https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model</a>
have the property that they are “well connected” - with high probability,         most subsets of vertices have many edges across them.</p>
<p>See here: <a href="https://www.math.cmu.edu/%7Eaf1p/BOOK.pdf" rel="nofollow noreferrer">https://www.math.cmu.edu/~af1p/BOOK.pdf</a> (p 69) for more precise information.</p>

CC BY-SA 4.0
2021-08-25T19:45:17.120Z
Yes I know this result about ER graph. Since I am math student, could you please explain more about the network connectivity and how it is studied in TCS using random graph models? Directly using ER graphs to model it?
MikeG
CC BY-SA 4.0
2021-08-25T20:06:30.280Z
I mentioned ER graphs as an example of a random graph model. So, by modeling network (such as social or physical network) as a random graph , you are likely to get good connectivity.
Avi Tal
CC BY-SA 4.0
2021-08-26T01:37:31.250Z
I see! That's an interesting viewpoint! So on what field will the theoretical scientists work if they have something to do with this? Network models? (I don't know what exact academic term I should look for when checking their homepages...)
MikeG
CC BY-SA 4.0
2021-08-25T05:14:29.680Z
2021-08-25T05:37:05.050Z
2021-08-25T05:37:05.050Z
Avi Tal
<p>Sorry for this large and vague question. I am a new grad probability student recently interested in random graph theory(RG). I heard from someone in math department that RG has close relationship to TCS, but he don't know what exactly is the relation. I am currently thinking about turning to a theoretical computer scientist in CS department to read something relative to RG, but since I don't know where RG is used in studying TCS, which is also a quite large field, I don't know who I should ask.</p>
<p>If possible, could you please explain a little bit about how RG is used in TCS? Like, in studying what problem, what link can be made between the original problem and random graph models, and what properties TCSers will look into for that random graph?</p>

<pr.probability><random-graphs>
Relationship between Random Graph Theory and TCS
MikeG
# Relationship between Random Graph Theory and TCS

(Asked by: username_0 on 2021-08-24)

Sorry for this large and vague question. I am a new grad probability student recently interested in random graph theory(RG). I heard from someone in math department that RG has close relationship to TCS, but he don't know what exactly is the relation. I am currently thinking about turning to a theoretical computer scientist in CS department to read something relative to RG, but since I don't know where RG is used in studying TCS, which is also a quite large field, I don't know who I should ask.

If possible, could you please explain a little bit about how RG is used in TCS? Like, in studying what problem, what link can be made between the original problem and random graph models, and what properties TCSers will look into for that random graph?

**Tags:** pr.probability, random-graphs


---

## 5 answers

### Answer by username_1 on 2021-08-27. Score: 5 | Accepted answer

There are interesting open algorithmic problems in random graphs, which might even lead to nontrivial results about complexity classes.

For the sake of an example, consider the simplest random graph model: take $n$ vertices, and put in each edge randomly and independently with probability 1/2. This model is often denoted by $G(n,1/2)$. It is a known result from the theory of random graphs that the size of a maximum clique in $G(n,1/2)$ is asymptotically $2\log\_2 n$, and the actual size is strongly concentrated on merely two neighboring integers.

That is, the clique number of $G(n,1/2)$ is (asymptotically) almost exactly determined. But how hard is it to ***find*** such a clique? It is unlikely to be NP-hard, because
there are only $n^{O(\log n)}$ many subsets of this size, so we can do an exhaustive search in $n^{O(\log n)}$ time, which is still a sub-exponential algorithm.
At the same time, no polynomial-time algorithm is known, either.

However, good constant factor approximation is possible: about half of the optimum, i.e. $\log\_2 n$, can be achieved by a known polynomial-time algorithm, with high probability.
On the other hand, for any fixed $\epsilon>0$, no polynomial-time algorithm is known
that would find a clique of size at least $(1+\epsilon)\log\_2 n$ with high probability in $G(n,1/2)$.

In general, I could imagine as an interesting research subject, the study of how various random graph algorithms could be reduced to each other. Are there such problems that could be identified as complete for certain appropriately defined classes?


---

### Answer by username_2 on 2021-08-27. Score: 3

One very natural application of random graph theory in computer science comes from the analysis of [cuckoo hashing](https://en.wikipedia.org/wiki/Cuckoo_hashing). In the most basic form of cuckoo hashing (with one key per cell and two possible cells per key) the state of a cuckoo hash table can be described as a random graph with a vertex for each cell and an edge for each key. The ability to place all keys into their cells hinges on the likelihood that the resulting graph has no connected components with more than one cycle. More detailed analysis of cuckoo hashing and its variants extend to more complex questions about random graphs and random hypergraphs.


---

### Answer by username_3 on 2021-08-27. Score: 3

Phase transitions in NP-complete (and other) problems. See this nice recent survey/intro by Cris Moore: <https://arxiv.org/abs/1702.00467>.

Many constructions in TCS (eg expanders come to mind) can be shown to exist by the probabilistic method. Getting efficient deterministic constructions to do the same is often challenging, interesting, and useful, but the proof of existence is a good start.


---

### Answer by username_1 on 2021-08-27. Score: 2

Another interesting connection between random graphs and TCS can be found in the concept of **de-randomization.**
Generally, de-randomization means the approximation of truly random structures by deterministic ones.

In TCS these random structures are often *random bit sequences,* which play an important role in randomized algorithms. There is much interest in constructing pseudo-random bit generators, which may lead to the de-randomization of randomized complexity classes, such as BPP, RP, ZPP. It is a major open question whether the complete de-randomization of these complexity classes is possible or not.

In random graph theory there is also significant interest in finding deterministic graph constructions that resemble truly random graphs, see the paper [Pseudo-random graphs](https://arxiv.org/pdf/math/0503745.pdf) by Krivelevich and Sudakov.

It seems that graphs have more structure than bit sequences. As a result, one can perhaps prove nicer results about pseudo-random graphs than about pseudo-random bit sequences. This may be only my personal taste, but if you read the above referenced paper, you might arrive at a similar conclusion.

It seems to me that TCS could still benefit from pseudo-random graph related results in the area of de-randomization. In the other direction, interesting pseudo-random graph constructions may arise from pseudo-random bit generators used in TCS, such as the Nisan-Wigderson generator.


---

### Answer by username_4 on 2021-08-25. Score: 2

One famous connection of random graphs to TCS is network connectivity.

Random graphs such as the Erdős–Rényi model - <https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model>
have the property that they are “well connected” - with high probability, most subsets of vertices have many edges across them.

See here: [https://www.math.cmu.edu/~af1p/BOOK.pdf](https://www.math.cmu.edu/%7Eaf1p/BOOK.pdf) (p 69) for more precise information.

> **Comments:**
> **username_0**: Yes I know this result about ER graph. Since I am math student, could you please explain more about the network connectivity and how it is studied in TCS using random graph models? Directly using ER graphs to model it?  
> **username_4**: I mentioned ER graphs as an example of a random graph model. So, by modeling network (such as social or physical network) as a random graph , you are likely to get good connectivity.  
> **username_0**: I see! That's an interesting viewpoint! So on what field will the theoretical scientists work if they have something to do with this? Network models? (I don't know what exact academic term I should look for when checking their homepages...)  

---

