Browse/search for people

Publication - Dr Misha Rudnev

    Minimising the Sum of Projections of a Finite Set

    Citation

    Lev, VF & Rudnev, M, 2018, ‘Minimising the Sum of Projections of a Finite Set’. Discrete and Computational Geometry, vol 60., pp. 493-511

    Abstract

    Consider the projections of a finite set (Formula presented.) onto the coordinate hyperplanes; how small can the sum of the sizes of these projections be, given the size of A? In a different form, this problem has been studied earlier in the context of edge-isoperimetric inequalities on graphs, and it can be derived from the known results that there is a linear order on the set of n-tuples with non-negative integer coordinates, such that the sum in question is minimised for the initial segments with respect to this order. We present a new, self-contained and constructive proof, enabling us to obtain a stability result and establish algebraic properties of the smallest possible projection sum. We also solve the problem of minimising the sum of the sizes of the one-dimensional projections.

    Full details in the University publications repository