Conjecture on the clique number in the intermediate regime

From papers

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.

Progress summary

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

Sources & referencesView supporting material

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).

Solutions 0

No solutions have been posted yet.