The London–Paris conjecture for cocircuit paths on topes

About 6 years old · traced to

Let M⁡\operatorname{\mathcal{M}} be a uniform oriented matroid. Let C⁡∗(M⁡)\operatorname{\mathcal{C}}^*(\operatorname{\mathcal{M}}) denote its cocircuits, and let X,Y∈C⁡∗(M⁡)X,Y\in\operatorname{\mathcal{C}}^*(\operatorname{\mathcal{M}}) be cocircuits that are vertices of at least one tope of M⁡\operatorname{\mathcal{M}}. For a tope T⁡\operatorname{\mathcal{T}}, write dT⁡(X,Y)d_{\operatorname{\mathcal{T}}}(X,Y) for the shortest-path distance between XX and YY in the subgraph induced by the vertices of T⁡\operatorname{\mathcal{T}}.

London–Paris conjecture. There exists a tope T⁡\operatorname{\mathcal{T}} in M⁡\operatorname{\mathcal{M}} such that X,Y∈T⁡X,Y\in\operatorname{\mathcal{T}} and

dM⁡(X,Y)=dT⁡(X,Y).d_{\operatorname{\mathcal{M}}}(X,Y)=d_{\operatorname{\mathcal{T}}}(X,Y).

If true, this would imply a quadratic upper bound on the diameter of polytopes via the improved quadratic bound for cocircuit graphs. The conjecture has been verified computationally for oriented matroids with up to nine elements, but remains open in general.

References

Primary source

Ilan Adler, Jesús A. De Loera, Steven Klee and Zhenyang Zhang, “Diameters of Cocircuit Graphs of Oriented Matroids: An Update”, arXiv:2006.08922 (2020).

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.