Vectors in a box

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10125728" target="_blank" >RIV/00216208:11320/12:10125728 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/s10107-011-0474-y" target="_blank" >http://dx.doi.org/10.1007/s10107-011-0474-y</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s10107-011-0474-y" target="_blank" >10.1007/s10107-011-0474-y</a>

Result language
angličtina
Original language name
Vectors in a box
Original language description
For an integer d a parts per thousand yen 1, let tau(d) be the smallest integer with the following property: if v (1), v (2), . . . , v (t) is a sequence of t a parts per thousand yen 2 vectors in [-1, 1] (d) with , then there is a set of indices, 2 a parts per thousand currency sign |S| a parts per thousand currency sign tau(d), such that . The quantity tau(d) was introduced by Dash, Fukasawa, and Gunluk, who showed that tau(2) = 2, tau(3) = 4, and tau(d) = Omega(2 (d) ), and asked whether tau(d) is finite for all d. Using the Steinitz lemma, in a quantitative version due to Grinberg and Sevastyanov, we prove an upper bound of tau(d) a parts per thousand currency sign d (d+o(d)), and based on a construction of Alon and V, whose main idea goes back toHAyenstad, we obtain a lower bound of tau(d) a parts per thousand yen d (d/2-o(d)). These results contribute to understanding the master equality polyhedron with multiple rows defined by Dash et al. which is a "universal" polyhedron encod
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)