Typical outer-string graph edge-density and degree-distribution conjecture

For a graph GG on nn vertices, let XnX_n be the degree of a uniformly random vertex of GG. Let OSGn\mathcal{OSG}_n and OSGnL\mathcal{OSG}^L_n denote the classes of unlabeled and labeled outer-string graphs on nn vertices. Typical outer-string graph edge-density and degree-distribution conjecture. If GnG_n is uniformly random in OSGn\mathcal{OSG}_n, then

e(Gn)(n2)p1118.\frac{e(G_n)}{\binom{n}{2}}\overset{\mathrm{p}}{\longrightarrow}\frac{11}{18}.

Furthermore, Xn/nX_n/n converges in distribution to a random variable YY such that Y{1/2,2/3}Y\in\{1/2,2/3\} almost surely, with

P(Y=1/2)=13,P(Y=2/3)=23.\mathbb{P}(Y=1/2)=\frac13,\qquad \mathbb{P}(Y=2/3)=\frac23.

The same conclusions hold when GnG_n is uniformly random in OSGnL\mathcal{OSG}^L_n. These conjectured limits are the outer-string analogue of the proposed string-graph statistics and predict a bimodal degree distribution; the source states no resolution.

Sources & referencesView supporting material

Primary source

Svante Janson and Andrew J. Uzzell, “On String Graph Limits and the Structure of a Typical String Graph”, arXiv:1403.2911 (2014).

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.