131 problems
Satisfiability threshold conjecture. For each there exists a threshold density , such that for any positive , for all , is almost…
Let be a random symmetric matrix whose upper-diagonal entries are independent Bernoulli random variables taking the values and with probability eac…
Let be the cycle with edges, and let denote its consistency probability. Define … The cycle consistency probability conjecture. The consistency probability of…
For every fixed integer , let be a uniformly random simple -regular graph on an even number of vertices. Let denote the maximum number of edges cr…
For every integer , let be a random -NAE-SAT instance with variables and independently uniformly chosen clauses, and let be a uniformly ran…
Let be a simple undirected graph with . For each vertex independently, choose incident edges uniformly with replacement, and let be the spanning subgraph…
For every integer , the complete graph has a decomposition into perfect matchings such that, for every pair , th…
A graph is called -universally rigid if, for every generic realization , every realization in any dimension satisfying…
For every integer , a nontrivial link-irregular tournament on vertices exists if and only if ; equivalently, a nontrivial link-irregular tournament of…
For fixed and , let be the random subset of obtained by including each integer independently with probability . Determine t…
Let satisfy and . If , then with probability tending to as , the edge set can be partitioned into exactly…
Does there exist an absolute constant such that, for every positive integer and every -connected graph , there is a partition suc…
Let denote the set of intersecting families , and let a family be trivial if all its members contain a common element. Then,…
For every fixed , determine whether the random graph has, with high probability, a fractional triangle decomposition precisely at the conjectured threshold…
There exists a universal constant such that, for every finite graph , the fractional expectation threshold for containing satisfies…
For every finite multigraph of maximum degree at most , and every pair of vertices with graph distance , the number of shortest – pat…
Fix . Let be an i.i.d. initial mass configuration for the divisible sandpile, with mean density , and let…
For an integer and a real number , let be the largest integer such that every graph on vertices satisfying…
This entry tracks El-Zahar–Erdős conjecture. It gives a strong negative answer that persists far beyond triangle-free graphs. Latest development For every g≥4, the construction has…
This entry tracks Divoux–Kelly–Kennedy–Sidhu, Allsop–Morris, McKay–Wanless, Kwan–Sah–Sawhney, and Cameron–Cavenagh–Greenhill–Wanless conjectures. It gives a broad probabilistic des…
This entry tracks Kahn’s matching-concentration conjecture. It advances predicted local behavior of large matchings and has enumeration applications. Latest development An averaged…
This entry tracks Chung's 1988 bandwidth problems for graph structures. It provides a common framework linking geometric-probability thresholds to layout parameters and resolves se…
Let be an alphabet of size , let be fixed, and let . For , define the column Hamming distance by…
For and , let range over independent nonnegative random variables satisfying . Defi…
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…