Felsner–Krawczyk–Micek generalized crossing-vector conjecture

About 14 years old · traced to

For w≥1w\ge 1 and integers 1≤k1≤⋯≤kw1\le k_1\le\cdots\le k_w, say that two vectors A,B∈ZwA,B\in\mathbb{Z}^w are (k1,…,kw)(k_1,\ldots,k_w)-crossing if there are coordinates i,ji,j such that A[i]−B[i]≥kiA[i]-B[i]\ge k_i and B[j]−A[j]≥kjB[j]-A[j]\ge k_j. Let f(k1,…,kw;w)f(k_1,\ldots,k_w;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 (k1,…,kw)(k_1,\ldots,k_w)-crossing. Felsner–Krawczyk–Micek generalized conjecture. For w≥1w\ge 1 and 1≤k1≤⋯≤kw1\le k_1\le\cdots\le k_w,

f(k1,…,kw;w)=k2⋯kw.f(k_1,\ldots,k_w;w)=k_2\cdots k_w.

The paper notes that this apparently more general conjecture is equivalent to the main conjecture, since f(k,w)=f(k,…,k;w)f(k,w)=f(k,\ldots,k;w). The general case remains open in the supplied text.

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.