×

Geometric relationship between parallel hyperplanes, quadrics, and vertices of a hypercube. (English. Russian original) Zbl 1278.52013

Probl. Inf. Transm. 48, No. 2, 185-192 (2012); translation from Probl. Peredachi Inf. 48, No. 2, 113-120 (2012).
Summary: In a space of dimension 30 we find a pair of parallel hyperplanes, uniquely determined by vertices of a unit cube lying on them, such that strictly between the hyperplanes there are no vertices of the cube, though there are integer points. A similar two-sided example is constructed in dimension 37. We consider possible locations of empty quadrics with respect to vertices of the cube, which is a particular case of a discrete optimization problem for a quadratic polynomial on the set of vertices of the cube. We demonstrate existence of a large number of pairs of parallel hyperplanes such that each pair contains a large number of points of a prescribed set.

MSC:

52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
90C10 Integer programming
90C20 Quadratic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beresnev, V.L., Diskretnye zadachi razmeshcheniya i polinomy ot bulevykh peremennykh (Discrete Distribution Problems and Polynomials in Boolean Variables), Novosibirsk: Inst. Mat., 2005.
[2] Billionnet, A. and Elloumi, S., Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0–1 Problem, Math. Program., Ser. A, 2007, vol. 109, no. 1, pp. 55–68. · Zbl 1278.90263 · doi:10.1007/s10107-005-0637-9
[3] Ahlatçioğlu, A., Bussieck, M., Esen, M., Guignard, M., Jagla, J.-H., and Meeraus, A., Combining QCR and CHR for Convex Quadratic Pure 0-1 Programming Problems with Linear Constraints, Ann. Oper. Res. (online publ.), September 30, 2011, DOI:10.1007/s10479-011-0969-1.
[4] Emelichev, V.A. and Korotkov, V.V., On Stability Radius of Effective Solution of Vector Quadratic Boolean Bottleneck Problem, Diskretn. Anal. Issled. Oper., 2011, vol. 18, no. 6, pp. 3–16. · Zbl 1249.90164
[5] Seliverstov, A.V. and Lyubetsky, V.A., On Symmetric Matrices with Indeterminate Leading Diagonals, Probl. Peredachi Inf., 2009, vol. 45, no. 3, pp. 73–78 [Probl. Inf. Trans. (Engl. Transl.), 2009, vol. 45, no. 3, pp. 258–263]. · Zbl 1194.15033
[6] Erdos, P., On a Lemma of Littlewood and Offord, Bull. Amer. Math. Soc., 1945, vol. 51, no. 12, pp. 898–902. · Zbl 0063.01270 · doi:10.1090/S0002-9904-1945-08454-7
[7] Costello, K.P. and Vu, V.H., The Rank of Random Graphs, Random Structures and Algorithms, 2008, vol. 33, no. 3, pp. 269–285. · Zbl 1194.05083 · doi:10.1002/rsa.20219
[8] Shnurnikov, I.N., Cardinality of a Separable Set of Vertices of a Multidimensional Cube, Vestnik Moskov. Univ., Ser. I: Mat. Mekh., 2010, no. 2, pp. 11–17. · Zbl 1304.52014
[9] Seliverstov, A.V. and Lyubetsky, V.A., On Forms Vanishing at Every Vertex of a Cube, Inform. Protsessy, 2011, vol. 11, no. 3, pp. 330–335.
[10] Beresnev, V.L., Goncharov, E.N., and Mel’nikov, A.A., Local Search over a Generalized Neighborhood for a Problem of Optimizing Pseudo-Boolean Functions, Diskretn. Anal. Issled. Oper., 2011, vol. 18, no. 4, pp. 3–16. · Zbl 1249.90137
[11] Alon, N. and Füredi, Z., Covering the Cube by Affine Hyperplanes, European J. Combin., 1993, vol. 14, no. 2, pp. 79–83. · Zbl 0773.52011 · doi:10.1006/eujc.1993.1011
[12] Ibarra, O.H. and Kim, C.E., Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, J. Assoc. Comput. Mach., 1975, vol. 22, no. 4, pp. 463–468. · Zbl 0345.90049 · doi:10.1145/321906.321909
[13] Schrijver, A., Theory of Linear and Integer Programming, Chichester: Wiley, 1986. Translated under the title Teoriya lineinogo i tselochislennogo programmirovaniya, Moscow: Mir, 1991.
[14] Xiao, Q.-F., Hu, X.-Y., and Zhang, L., The Symmetric Minimal Rank Solution of the Matrix Equation AX = B and the Optimal Approximation, Electron. J. Linear Algebra, 2009, vol. 18, pp. 264–273.
[15] Mitra, S.K., Fixed Rank Solutions of Linear Matrix Equations, Sankhyā, Ser. A, 1972, vol. 34, no. 4, pp. 387–392. · Zbl 0261.15008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.