← All problems

Felsner–Krawczyk–Micek generalized crossing-vector conjecture

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
  1. 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.