# 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:

#### Referees:

Dr. M.I. Kratko (Institute of Mathematics, Ukrainian Academy of Sciences, Kiev).

#### Supporting organization:

### 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
**Q _{n}**. 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

**Q**of cardinality

_{n}**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)2 ^{n}** 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

**Q**with a fixed diameter [e]. For exact statements and more information see the papers [a,c,f,g].

_{n}The second chapter deals with isoperimetric problems for subsets with
special structure. There we presented a solution for the subsets of
**Q _{n}** 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 **Q _{n}** 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 :

*A discrete isoperimetric problem*, in: Applied Mathematics and Computer Software, Moscow University Press, 1982, 40-44.*An isoperimetric problem*, Discrete Analysis, Novosibirsk, vol. 40, 1984, 1-16.*Specification of solutions of the discrete isoperimetric problem which have a critical cardinality*, Soviet Math. Dokl. vol. 289, 1984, No. 3, 520-524.*On minimization of the surrounding of subsets in Hamming space*, Kombinatorno-Algebraic Methods in Applied Mathematics, Gorky University Press, 1985, 45-48.*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.*On the construction of solutions of a discrete isoperimetric problem in Hamming space*, Math. USSR Sbornik, vol. 63, 1989, No. 1, 81-96.*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.