The uniform-distribution conjecture for temporal-clique label intervals
The uniform-distribution conjecture for temporal-clique label intervals
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.
Sources & referencesView supporting material
Primary source
George B. Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos and Paul G. Spirakis, “On the existence of δ-temporal cliques in random simple temporal graphs”, arXiv:2404.07147 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.