The disjoint-edge lower bound for dense geometric graphs

About 5 years old · traced to

Let GG be a geometric graph with 2∣E(G)∣≥∣V(G)∣2|E(G)|\geq |V(G)|. The disjoint-edge lower-bound conjecture. Then

∣DJ(G)∣≥n2⋅(d(G)3).|DJ(G)|\geq \frac{n}{2}\cdot \binom{d(G)}{3}.

This conjecture gives a lower bound for the number of disjoint edge pairs in a sufficiently edge-dense geometric graph. The source gives no resolution, so the claim remains open.

References

Primary source

Nikita Chernega, Alexandr Polyanskii and Rinat Sadykov, “Disjoint edges in geometric graphs”, arXiv:2111.05425 (2022).

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.