The sphericity conjecture for dichotomous ordinal complete graphs

From papers

Let pdd(n)\mathrm{pdd}(n) denote the minimum dimension required to realize a dichotomous ordinal complete graph on nn vertices, and let sp(G)\mathrm{sp}(G) be the sphericity of a graph GG, namely the least dimension in which GG has a unit ball representation. Write Ka,bK_{a,b} for the complete bipartite graph with parts of sizes aa and bb. Sphericity conjecture.

pdd(n)=sp(Kn2,n2).\mathrm{pdd}(n)=\mathrm{sp}(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}).

The complete bipartite graph is a dichotomous ordinal graph and therefore gives a lower bound for pdd(n)\mathrm{pdd}(n). The conjecture asserts that the balanced complete bipartite graph is the most difficult such graph to realize, but the source reports no results establishing it.

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

Patrizio Angelini, Sabine Cornelsen, Carolina Haase, Michael Hoffmann, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner and Antonios Symvonis, “Geometric realizations of dichotomous ordinal graphs”, arXiv:2503.07361 (2025).

Solutions 0

No solutions have been posted yet.