Conjecture on the clique number in the intermediate regime

About 9 years old · traced to

Let Gn,rnG_{n,r_n} be the split-and-drift random graph, let n_n denote its parameter, and let κn\kappa_n be its clique number. In the intermediate regime, rn→+∞r_n \to +\infty and rn=o(n)r_n=o(n). Clique-number conjecture. There exist constants α,β>0\alpha,\beta>0 such that

P(αnrn≤κn≤βnrn)→n→∞(1.\mathbb{P}\left(\alpha\frac{n}{r_n}\leq \kappa_n\leq\beta\frac{n}{r_n}\right)\xrightarrow[n\to\infty]{\mathstrut}1.

The conjecture predicts that the clique number is of order n/rnn/r_n, matching the approximate degree scale of a typical vertex in the intermediate regime. The source provides no resolution, so the conjecture remains open.

References

Primary source

François Bienvenu, Florence Débarre and Amaury Lambert, “The split-and-drift random graph, a null model for speciation”, arXiv:1706.01015 (2018).

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.