Open Questions

The open questions in graph theory are difficult. Currently, many problems are solved through powerful supercomputer simulations. The upper bound of Ramsey R(5,5) was merely decreased by one in the last two decades, see Gil Kalai's blog for this news (2017). Here is a list of questions I am particularly interested in. 

1. Given a better bound for Ramsey R(5,5). Such a problem is assumed to be computationally accessible, but R(6,6) will be totally out of control. The exact solution is believed to be 43 since it has been a long time since searching for a solution. However,  any better tool to get better estimates on other Ramsey numbers would be significant.

2. Upper and lower bounds of Ramsey number (The lower bound of non-diagonal Ramsey numbers has recently been improved, see arXiv:2507.12926 ).

3. The asymptotic expression for R(3, k) as k goes to infinity. This problem was resolved. R(3,k) has the same order as k^2/ln k; however, the constant is not known yet. (current best constant is 1/3).

4. Percolation theory of random graphs.  

5. Meyniel's conjecture about the "Cops and Robbers" problem.

6. Graph Isomorphism in NP-complete or not. [Quasi-polynomial time has been proved in 2015(rev 2017)]

7. Kissing number Problems, including growth rate and the exact values of low dimensions. 

8. Suppose we define the Radon transform on a graph by the shortest path lengths between every pair of vertices in a boundary set. Is it possible to have the boundary set of size O(sqrt(|E|)) when the weights are i.i.d.  non-negative random variables and independent of the graph? It is simple to show that trees are not possible; the minimum boundary set's size is roughly one-half of |E|. 

9. We extend the above idea to the lattice, and then the Radon transform can be defined by the first passage percolation path. Is it possible to find a minimal boundary set to identify the random weights,  or at least as much statistical information as possible on the weights?

10. The irregularity conjecture of  Faudree-Lehel. The result has recently been shown to be almost true for quite dense graphs.

11. Community detection in a random graph. 

12. Triangle finding problem, the current best algorithm (quantum) is O(n^1.25), is it possible to close the gap and make it O(n)? For the classical algorithm, the best bound for a graph of n nodes seems at least O(n^{2 + \epsilon}) according to matrix-multiplication complexity.