The no-product-structure conjecture below the independent-crossing threshold

At least 1 year old · documented by

Let nn be a positive integer, let s(n)s(n) be the threshold defined in the paper, and let α\alpha be a parameter. Consider the class of intersection graphs of α\alpha-free homothetic regular nn-gons.

The no-product-structure conjecture. For every α<s(n)\alpha < s(n), the class of intersection graphs of α\alpha-free homothetic regular nn-gons does not have product structure.

The paper determines that arbitrarily many independent edges can cross a single edge in canonical drawings when α<s(n)\alpha<s(n), but the required construction ruling out product structure is known only in some cases and an alternative construction is suspected for the remaining cases.

References

Primary source

Laura Merker, Lena Scherzer, Samuel Schneider and Torsten Ueckerdt, “Intersection Graphs with and without Product Structure”, arXiv:2409.01732 (2024).

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.