Ph. D. Thesis

Isoperimetric Type Problems on the Unit Cube

Moscow State University, Faculty of Computational Mathematics and Cybernetics, Department of Mathematical Cybernetics, 1984.

Advisor:

Prof. A.A. Sapozhenko (Moscow State University).

Referees:

Dr. L.A. Bassalygo ( Institute for Problems of Information Transmission, Russian Academy of Sciences, Moscow)
Dr. M.I. Kratko (Institute of Mathematics, Ukrainian Academy of Sciences, Kiev).

Supporting organization:

Mathematical Institute, West-Siberian Branch of the Russian Academy of Sciences, Novosibirsk, (Dr. A.V. Kostochka).

Brief summary :

The Thesis is devoted to the study of certain discrete extremal problems on the n-dimensional unit cube. The considered problems are variations of the vertex isoperimetric problem. Such problems arise very often in various extremal problems. Many of its applications can be found in the survey paper [g].

Let A be a subset of vertices of the n-cube Qn. A vertex x of A is called boundary vertex of A if some vertex of the ball of radius 1 (in Hamming metric) centered in x is not in A. The vertex isoperimetric problem consists in finding subsets of vertices of Qn of cardinality m (m and n are fixed) with minimum number of the boundary vertices among all the subsets of the same cardinality. Such subsets are called optimal. One of the optimal subsets is known for more since the mid of 60's due to L.H. Harper.

The thesis consists of 3 main chapters. The first chapter is devoted to specification of all optimal subsets. We obtained for each n a complete characterization of all optimal subsets for asymptotically (3/4)2n values of cardinality m in terms of algorithmic constructions. A number of general properties of all optimal subsets are derived which also can be considered as a kind of their characterization. Some results of this section were used later for specification of all maximal subsets of Qn with a fixed diameter [e]. For exact statements and more information see the papers [a,c,f,g].

The second chapter deals with isoperimetric problems for subsets with special structure. There we presented a solution for the subsets of Qn consisting of the vertices with the number of ones of the same parity. This result was used by A.A. Sapozhenko for computing the asymptotic number of binary codes with distance 2. We also studied isoperimetric problem for a sphere in Hamming space and obtained some particular results towards its solution. The results of this chapter can be found in papers [b,d].

In the third chapter of the Thesis we studied the vertex isoperimetric problems for various definitions of the boundary operator (see [d]). In particular, what happens if one replaces the balls of radius 1 in the definition of the boundary vertices with balls of radius k with k > 1? We call the corresponding optimal subsets k-optimal. It turns out that if a set A of Qn is k-optimal then it is l-optimal for any l > k (cf. [f]). This results has deep corollaries for the Kruskal-Katona type problems [f].

References :

  1. A discrete isoperimetric problem, in: Applied Mathematics and Computer Software, Moscow University Press, 1982, 40-44.
  2. An isoperimetric problem, Discrete Analysis, Novosibirsk, vol. 40, 1984, 1-16.
  3. Specification of solutions of the discrete isoperimetric problem which have a critical cardinality, Soviet Math. Dokl. vol. 289, 1984, No. 3, 520-524.
  4. On minimization of the surrounding of subsets in Hamming space, Kombinatorno-Algebraic Methods in Applied Mathematics, Gorky University Press, 1985, 45-48.
  5. Specification of the maximal sized subsets of the unit cube with respect to given diameter, Problems of Information Transmission, vol. XXIII, 1987, No. 1, 106-109.
  6. On the construction of solutions of a discrete isoperimetric problem in Hamming space, Math. USSR Sbornik, vol. 63, 1989, No. 1, 81-96.
  7. Isoperimetric problems in discrete spaces, in: Extremal Problems for Finite Sets. Bolyai Soc. Math. Stud. 3, P. Frankl, Z. Füredi, G. Katona, D. Miklos eds., Budapest 1994, 59-91.