The uniform-distribution conjecture for temporal-clique label intervals
Statement
Let be an Erdős–Rényi random graph, and construct a temporal instance by assigning labels to the edges of independently and uniformly at random in , and assigning labels to all other edges independently and uniformly at random in . For a vertex set , define its label interval by
Let be the -clique constructed by algorithm on instance . Uniform-distribution conjecture. Then is distributed almost uniformly at random within . This conjecture concerns the distribution of the interval containing the labels of an algorithmically found temporal clique and is proposed as a possible route toward proving the reduction from temporal-clique approximation to maximum-clique approximation in Erdős–Rényi graphs; no proof or resolution is given.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.