The uniform-distribution conjecture for temporal-clique label intervals

Let Gn,δG_{n,\delta} be an Erdős–Rényi random graph, and construct a temporal instance I(Gn,δ){\cal I}(G_{n,\delta}) by assigning labels to the edges of Gn,δG_{n,\delta} independently and uniformly at random in [0,δ][0,\delta], and assigning labels to all other edges independently and uniformly at random in [δ,1][\delta,1]. For a vertex set QQ, define its label interval by

Δ(Q)=[min(λ(e):eQ),max(λ(e):eQ)].\Delta(Q)=\left[\min(\lambda(e):e\in Q),\max(\lambda(e):e\in Q)\right].

Let QQ^* be the δ\delta-clique constructed by algorithm ASRT{\cal A}_{SRT} on instance I(Gn,δ){\cal I}(G_{n,\delta}). Uniform-distribution conjecture. Then Δ(Q)\Delta(Q^*) is distributed almost uniformly at random within [0,1][0,1]. 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.