Felsner–Krawczyk–Micek crossing-vector extremal conjecture

About 14 years old · traced to

For positive integers kk and ww, let f(k,w)f(k,w) be the maximum size of a subset of Zw\mathbb{Z}^w in which every two vectors are 11-crossing but no two vectors are kk-crossing. Felsner–Krawczyk–Micek conjecture. For all k,w≥1k,w\ge 1,

f(k,w)=kw−1.f(k,w)=k^{w-1}.

This is the main extremal problem of the paper. The conjecture is proved for w≤3w\le 3, while weaker upper bounds and constructions of families of the conjectured size are given for larger dimensions; the general case remains open.

References

Primary source

Michał Lasoń, Piotr Micek, Noah Streib, William T. Trotter and Bartosz Walczak, “An extremal problem on crossing vectors”, arXiv:1205.1824 (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.