# Habilitation Thesis

To have a scientific career at a German University, two dissertations are needed: the Ph.D. thesis and the "Habilitation" thesis. There is no American equivalent to the German Habilitation, as the academic certification is awarded to an individual who already has a Ph.D. Habilitation is the highest scientific distinction in Germany.

## Discrete Extremal Problems on Graphs and Posets

University of Paderborn, Department of Mathematics and Computer Science, 1996.

#### Referees :

### Brief summary :

The Thesis consists of five main chapters (excluding the introductory chapter) and is devoted to various discrete extremal problems on graphs and posets (partially ordered sets) and their applications.

The first chapter is devoted to isoperimetric problems on graphs. This
results concerning the vertex version of the problem for the
**n**-dimensional unit cube can be considered as a continuation of
research on this subject [d] started in the
Ph.D. Thesis. A classification of
all solutions is proposed and some new solutions are constructed [k].
The main part of the chapter is devoted to the edge version of the
problem consisting in constructing a set of **m** vertices in a graph
(**m** is fixed) with minimal cut. A new approach to the problem is
proposed for the cartesian products of graphs [p]. The approach is based on an
equivalence relation and allows to solve the problem for a class
of graphs if it is solved for a representative of this class. Deep relations
of this problem and the problem of minimization of shadows in posets are
described and applications for maximization of more general functions on
cartesian products of graphs are presented (see [r]).

The second chapter deals with the shadow minimization problem in posets.
For a ranked poset **P** and its **k**-th level **P _{k}** the
problem is to find an

**m**-element subset

**A**of

**P**with minimal shadow (i.e. the number of elements of

_{k}**P**, which are less in the partial order than the elements of

_{k-1}**A**). This problem is solved for some concrete posets such as the star poset [b], the binary subword poset [g] and the linear lattice [o]. Moreover, a class of posets is considered and a two-parametrical family of posets of this class is found for which the problem has a nested structure of solutions [s].

The problems studied in the first two chapters are applied in the third
chapter to a number of related extremal problems. Among them are problem of
specification of all subsets of the **n**-cube with a fixed diameter which
have maximal cardinality [a], scheduling problems which involve constructing
optimal in a sense edge numberings of graphs [i], a problem arising in
encoding of analog signals [c] and constructing ideals in posets
with maximal weight [e]. The last problem has direct relations with
minimization of the edge-cut in graphs [p].

The fourth chapter is devoted to embedding of trees into the **n**-cube.
We deal with a hypothesis of Havel concerning embedding binary trees into
the **n**-cube as subgraphs and present new technique for embedding
caterpillars [q]. The approach is based on embedding of ladders, covers
all but one known results on caterpillars and provides embedding of many new
types of them. Furthermore, we study embedding complete **t**-ary trees as
subgraphs into the **n**-cube of minimal dimension. Our constructions [m]
improve known bounds for **n**. Preserving orientation embedding of binary
oriented trees into oriented **n**-cube are studied as well [l].

Solution of four more particular discrete extremal problems is presented in the fifth chapter (see [f,h,j,n]).

#### References :

*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.*Minimization of the shadows in the partial mappings semilattice*, Discrete Analysis, Novosibirsk, vol. 46, 1988, 3-16.*Encoding of analog signals for discrete binary channel*, in: Proceedings Int. Conf. Algebraic and Combinatorial Coding Theory, Varna 1988, 12-16.*On the construction of solutions of a discrete isoperimetric problem in Hamming space*, Math. USSR Sbornik, vol. 63, 1989, No. 1, 81-96.*Extremal ideals of the lattice of multisets with respect to symmetric functionals*, (with Voronin V.P.), Discretnaya Matematika, vol. 2, 1990, No. 1 50-58.*On superspherical graphs*, (with Sali A.), Colloq. Math. Soc. Janos Bolyai, vol. 60, 1991, 89-95.*A Kruskal-Katona type theorem*, (with Gronau H.-D.), Rostock Math. Kolloq., vol. 46, 1992, 71-80.*Two extremal problems for oriented trellises*, Problems of Information Transmission, vol. 28, 1992, No. 2, 109-111.*On edge numberings of the n-cube graph*, (with Weber K., Grünwald N.), Discr. Appl. Math., vol. 46, 1993, No. 2, 99-116.*On partitioning the n-cube into sets with mutual distance 1*, (with Ahlswede R., Blokhuis A., Metsch K., Moorhouse E.), Appl. Math. Lett., vol. 6, 1993, 17-19.*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.*On oriented embedding of the dichotomic tree into the hypercube*, Combinatorics, Probability and Computing, Cambridge, vol. 3, 1994, 27-38.*Embedding complete trees into the hypercube*, Discrete Appl. Math., vol. 110, 2001, no. 2-3, 101-119.*Properties of graded posets preserved by some operations*, (with Engel K.), in: Mathematics of Paul Erdös (ed. R.L. Graham, J. Nesetril), Springer Verlag, 1996, 79-85.*A Kruskal-Katona theorem for the linear lattice*, (with Blokhuis A.), Europ. J. Combin., vol. 20, 1999, no. 2, 123-130.*On an equivalence in discrete extremal problems*, Discr. Math., vol. 203, 1999, no. 1, 9-22.*Embedding ladders and caterpillars into the hypercube*, (with Monien B., Unger W., Wechsung G.), Discrete Appl. Math., vol. 82, No. 1-3 (1998), 19-27.*Edge isoperimetric problems of graphs*, in: Graph Theory and Combinatorial Biology, Bolyai Soc. Math. Stud. 7, L. Lovasz, A. Gyarfas, G.O.H. Katona, A. Recski, L. Szekely eds., Budapest 1999, 157-197.*On posets whose products are Macaulay*, J. Combin. Theory, vol. A-84, 1998, No. 2, 157-170.