Volume 20, No 3, 2013, P. 65-70

UDC 514.172.45
Seliverstov A. V. 
On monomials in quadratic forms

Abstract:
There are proved some restrictions on the zero-nonzero pattern of entries in a matrix of the real quadratic form which reaches its minimum value on a large set of vertices of the multidimensional cube centered at the origin whose edges are parallel to the coordinate axes. In particular, if the graph of the matrix contains an articulation point then the set of minima of the corresponding quadratic form is not maximal (with respect to set inclusion) among all such sets for various quadratic forms.
Bibliogr. 21.

Keywords: combinatorial optimization, quadratic form, polytope, facet, graph, matrix.

Seliverstov Alexandr Vladislavovichh ¹
1. Kharkevich Institute for Information Transmision Problems RAS,
19 build. 1, Bolshoy Karetny Lane, 127994 Moscow, Russia
e-mail: slvstv@iitp.ru