531 problems
For a graph , let be the unique such that … Define the expectation threshold by … The second Kahn–Kalai conjecture. There is a fixed such that for any…
Erdős–Rényi face conjecture. The expected number of faces is
Let be a random labeled graph on vertices, let denote its two-fold automorphism group, and let denote expectation over…
Random embedding edge-type conjecture. The expected numbers of bad singular edges, good singular edges, and regular edges are respectively
Let denote the edge density in the dense edge–triangle exponential random graph model at its critical parameters . The conjecture asserts that…
For every integer , the complete graph has a decomposition into perfect matchings such that, for every pair , th…
There exists an absolute constant such that, for every and every graphical degree sequence on vertices, writing…
For even and integer degree sequences satisfying and , let be a uniformly random -regular graph on vertices. Let…
Let be an Erdős–Rényi random graph, let denote its number of triangles, and suppose that . For each fixed , determine the large-dev…
Let be the number of Steiner triple systems of order containing no Pasch configuration, and let be the number of Latin squares of order containing no…
Let be a random -regular triangle-free graph on vertices, with . The claimed sharp transition is at : if…
Fix . Let , let be its non-backtracking matrix, and order the eigenvalues by nonincreasing modulus, so that…
Let be a random geometric graph generated by independent uniform points on a high-dimensional sphere, with connection function applied to endpoint inner…
This entry tracks Random generalized triadic-process sharp-threshold conjecture. It gives a first threshold window around the conjectured n^{-1/2} scale for the generalized process…
This entry tracks Second reconstruction transition for random graphs from 2-neighborhoods. It nearly locates the second phase transition for reconstruction from local information.…
Let be a finite graph, let denote the spectral radius of its adjacency matrix, and let be obtained from by retaining each edge independently with probabi…
Let be a fixed connected graph, let be the Erdős–Rényi random graph, and let denote the number of copies of in . Define…
Let be the uniform model of random -regular graphs on the vertex set . A -orientation is an orientation of a -regular graph in wh…
Cohomology-vanishing conjecture. If
Let with , and let the known distances be distributed as in for a parameter . Call a subset reconstructible if every injec…
Connectivity conjecture. If
Let be the random graph on vertices, let denote its th power, and write and for the chromatic and independence numbers of a graph…
Triangle-free graph discontinuity conjecture. The function
Let be a graph, and write and for its numbers of vertices and edges. For a subgraph , define to be the smallest such that … for every…
Bollobás–Pebody–Riordan conjecture. For the model with , the chromatic polynomial is almost complete.